Worksheet

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Motivation

Im Laufe der Veranstaltung hatten wir uns einmal mit Aufgaben der Form a^e\equiv b mod   m befasst, beispielsweise bei der Frage, was die letzte Dezimalstelle einer Potenz ist (3^{160} mod 10=...)oder welchen Rest eine Zahl beispielsweise bei der Division durch 8 lässt(3^{160} mod 8). Der Trick dabei war, dass man versucht hat die Potenz derart in a^{(e_1\cdot e_2)}=(a^{e_1})^{e_2} zu zerlegen, dass a^{e_1}\equiv 1 mod m (oder z.B. alternativ a^{e_1}\equiv -1 mod m... halt was einfaches). Die Zerlegung ist aber gar nicht immer leicht (Bsp: 11^{182} mod 19=...). In diesem Abschnitt werden wir ein paar Tricks kennen lernen, wie man in bestimmten Fällen herausfindet, welche Potenzen kongruent 1 mod m sind. An dieser Stelle bietet sich eine kleine Wiederholung an.

Bestimme...

3^{160} mod 10

3^{161} mod 10

3^{160} mod 8

Wiederholung

  1. Zwei Zahlen a und b heißen teilerfremd genau dann, wenn ggT(a,b)=1
  2. Wenn ac\equiv bc mod m und ggT(c,m)=1, dann gilt auch a\equiv b mod m

Die Eulersche Phi-Funktion

Wir definieren die Eulersche Phi-Funktion folgendermaßen: \varphi(m)=|\{x\in\mathbb{N}|1\leq x\leq m \wedge ggT(x,m)=1\}|

Beispiele:

  • \varphi(8)=...
  • \varphi(12)=...
  • \varphi(17)=...

Satz von Euler

ggT(a,m)=1\Rightarrow a^{\varphi(m)}\equiv 1 mod m

Beweis:




Im Allgemeinen ist natürlich jetzt interessant: Wie bekommt man denn nun \varphi(m) einfach heraus?

Für eine Primzahl p ist es noch einfach: \varphi(p)=p-1. Aber was, wenn m keine Primzahl ist? Bevor wir uns das überlegen, können wir aber schnell mal den Kleinen Satz von Fermat hinschreiben. Der ergibt sich nämlich als Spezialfall direkt aus dem Satz von Euler:

Kleiner Satz von Fermat

Für a\in\mathbb{N} und Primzahlen p mit p\not| a gilt: a^{p-1}\equiv 1 mod p

Sätze zur Eulerschen Phi-Funktion

So, jetzt aber... wir bestimmen \varphi(m) für verschiedene Fälle:

  1. Wenn p prim, dann \varphi(p^n)=p^n-p^{n-1}
  2. ggT(m,n)=1\Rightarrow \varphi(m\cdot n) = \varphi(m)\cdot\varphi(n)
  3. Fehler beim Parsen(PNG-Konvertierung fehlgeschlagen. Bitte die korrekte Installation von LaTeX und dvipng überprüfen (oder dvips + gs + convert)): n=\prod_{i=1}^r p_i^k_i
und k_i\geq 1 \Rightarrow \varphi(n)=n\prod_{i=1}^r(1-\frac{1}{p_i})
  1. \sum_{d|n} \varphi(d)=n

Beweis:

Noch ein Satz

Für a\in\mathbb{N} und p Primzahl gilt: a^p\equiv a mod p

Beweis: Mmh... hier brauchen wir jetzt aber eine Fallunterscheidung...