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]

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