Worksheet

Motivation

Wir hatten 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 ähnliche Probleme ($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.

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)$

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...