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) \]

[math] k^{\varphi(n)}[/math] ist also

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: \[ (i) \ z_i \text{mod} g = 0 \ \forall 1 \leq i \leq n \] \[ (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 \]

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\}|\]

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