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: Video

Hinweis des Studenten Flo1860: Zusätzlicher Beweisteil - der im Video fehlt (zu: PH Heidelberg/Zahlentheorie/Sätze von Euler und Fermat - SoSe2012) - fehlt das wirklich? Die Diskussion sei eröffnet! :-)

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$

Beweise: Video

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

Der große Satz von Fermat

An dieser Stelle sollten wir vielleicht ein paar Worte über den "großen Satz von Fermat" verlieren, der besagt:

Es gibt keine $a,b,c\in\mathbb{Z}\setminus\{0\}$, welche die Gleichung $a^n+b^n=c^n$ mit $n\geq 3$ lösen.

Für $n=2$ gibt es neben der allseits bekannten Lösung $a=3,b=4,c=5$ auch unendlich viele weitere Lösungen in den natürlichen Zahlen (sogenannten Pythagoreische Zahlentripel), wie man leicht nachweisen kann, wenn man die Zahlen für $x,y\in\mathbb{N}$ mit $x>y$ folgendermaßen konstruiert: $a=x^2-y^2$, $b=2xy$, $c=x^2+y^2$

Aber zu beweisen, dass es für $n\geq 3$ keine Lösung zu der Gleichung $a^n+b^n=c^n$ gibt, ist nicht ganz so einfach, wie die Geschichte der Mathematik gezeigt hat...

• Großer Satz von Fermat auf Wikipedia
• Der große Satz von Fermat - die Lösung eines 300 Jahre alten Problems von Jürg Kramer
• Andrew Wiles
• Wolfskehl-Preis