Der Satz von Euler-Fermat

Aussage

Für alle [math] k, n \in \mathbb{Z}_{\gt 0}[/math] mit ggt[math](k,n) = 1 [/math] gilt \[ k^{\varphi(n)} \equiv 1 \ (\text{mod} \ n) \]

Für [math] k^{\varphi(n)}[/math] gilt also [math] [k^{\varphi(n)}] = [1] [/math].

ggT

ggT steht für größter gemeinsamer Teiler und liefert die größte ganze Zahl, die alle angegebenen Zahlen ohne Rest teilt.
Also ist eine Zahl [math]g=[/math] ggT([math]z_1, \dots , z_n)[/math], falls gilt:

[math] (i) \ z_i\text{ mod } g = 0 \ \forall 1 \leq i \leq n [/math]

[math] (ii)\ \text{Für alle } h \in \mathbb{Z} \text{ mit } z_i \text{ mod } h = 0 \ \forall 1 \leq i \leq n \text{ gilt: } h \leq g [/math]

Beispiel

Betrachten wir ggT(8,12).

• Die Zahl 9 wird ganzzahlig von den Zahlen [math] \{1, 2, 4, 8\}[/math] geteilt.
• Die Zahl 12 wird ganzzahlig von den Zahlen [math] \{1, 2, 3, 4, 6, 12\} [/math] geteilt.
• Die gemeinsamen Teiler sind also [math] \{1, 2, 4\} [/math].
• Somit ist der größte gemeinsame Teiler 4.

Also: [math]\text{ggT}(8,12) = 4[/math].

Sonderfall

Gilt [math] \varphi(p) = p-1 [/math] für eine Zahl [math] p [/math], so ist [math]p[/math] eine Primzahl. Dies folgt daraus, dass in diesem Fall jede Zahl, die kleiner als [math]p[/math] ist, nur 1 als größten gemeinsamen Teiler hat.

Die Eulersche [math] \varphi [/math]-Funktion

Die Eulersche [math] \varphi [/math]-Funktion ordnet einer positiven ganzen Zahl [math]m[/math] die Anzahl der ganzen positiven Zahlen zu, für die gilt:

• Die Zahl ist kleiner oder gleich [math]m[/math].
• Der größte gemeinsame Teiler von [math]m[/math] und der Zahl ist 1.

Also: \[ \varphi: \ \mathbb{Z}_{>0} \longrightarrow \mathbb{C}\] \[ m \mapsto |\{d \in \mathbb{Z} | 1 \leq d \leq m \text{ und ggT}(d,m) = 1\}|\]

Beispiel

Wir betrachten [math] \varphi(6)[/math].

• Es werden alle Zahlen betrachtet, die kleiner oder gleich 6 sind.
• Zuerst wird der [math]\text{ggT}(h,6) \ \forall 1\leq h \leq 6[/math] betrachtet.

[math]h[/math]	1	2	3	4	5	6
[math]\text{ggT}(h,6)[/math]	1	2	3	2	1	2

• Für die [math]\varphi[/math]-Funktion werden nur die Zahlen betrachtet, für die der größte gemeinsame Teiler von 6 und der Zahl 1 ist. Also bleiben [math]\{1,5\}[/math].
• Da gilt [math]|\{1,5\}| = 2[/math] ist [math] \varphi(6) = 2 [/math]

Beweis des Satzes von Euler-Fermat

Es gibt verschiedene Beweise für den Satz von Euler-Fermat. In diesem Beweis wird der Satz von Euler-Fermat als Anwendung des Satzes von Lagrange betrachtet.

Betrachtet man den Ring [math] \mathbb{Z}/n\mathbb{Z} [/math], so existiert für [math] [k] [/math] ein inverses Element [math] [k^{-1}] [/math], Da [math] \text{ggT}(k,n) = 1[/math].

Beispiele zum inversen Element

Fall 1: [math] n = 3, \ k = 2 [/math] ,also [math] \text{ggT}(2,3) = 1 [/math]
In diesem Fall hat 2 ein inverses Element, denn [math] 2 * 2 = [4] = [1] [/math]

Fall 2: [math] n = 4, \ k = 2 [/math] ,also [math] \text{ggT}(4,2) = 2 [/math]
Damit 2 ein inverses Element hat, muss ein Element [math] i [/math] in [math] \mathbb{Z}/4\mathbb{Z} [/math] existieren, sodass [math] 2 * i = [1][/math], also [math] 2 * i \in \{1, 5, 9, 13, \dots\}[/math]
Aber:

• [math] 2*0 = 0 \not = [1] [/math]
• [math] 2*1 = 2 \not = [1] [/math]
• [math] 2*2 = 4 \not = [1] [/math]
• [math] 2*3 = 5 \not = [1] [/math]

Es gibt also kein inverses Element im Ring [math] \mathbb{Z}/4\mathbb{Z} [/math].

Spezialfall

Ein Spezialfall des Satzes ist der kleine Fermatsche Satz.

Anwendungen

Der Satz von Euler-Fermat findet unter anderem in der Kryptographie anwendung. Beispielsweise beim RSA-Verfahren.

Quellen

Lassueur, Dr. Caroline(2017): Elementare Zahlentheorie – Kurzskript zur Vorlesung