Satz von Euler

Der Satz von Euler verallgemeinert den kleinen Fermatschen Satz und wird deshalb auch Satz von Euler-Fermat genannt. Zur Erinnerung - der kleine Fermat besagt: a^p-1 mod p = 1

Satz: Sind a und n zwei natürliche teilerfremde Zahlen, dann gilt:
a^φ(n) mod n = 1

φ(n) ist die Anzahl der zu n teilerfremden natürlichen Zahlen (die Anzahl aller Zahlen ≤ n, deren größter gemeinsamer Teiler mit n gleich 1 ist).
Beispiele:
φ(12) = 4, teilerfremde Zahlen sind {1, 5, 7, 11}

φ(13) = 12, alle Zahlen von 1 bis 12 sind teilerfremd, da 13 eine Primzahl ist

φ(14) = 6, teilerfremde Zahlen sind {1, 3, 5, 9, 11, 13}
Zu einer Primzahl p sind alle Zahlen von 1 bis (p - 1) teilerfremd - daraus folgt: φ(p) = p - 1.
Für prime Moduln p geht der Satz von Euler daher in den kleinen Satz von Fermat über.
Für das Produkt zweier Primzahlen p und q gilt weiters:
φ(p q) = (p - 1) ^. (q - 1)
Somit:
a^{φ(n)^.φ(m)} mod n^.m = 1

für n und m prim

a^{(n-1) (m-1)} mod n^.m = 1 (a teilerfremd zu m und n)

Beispiel:

Was ist die letzte Dezimalstelle von 7³³³ ?

Die Frage kann umgedeutet werden zu: 7³³³ mod 10 = x (gefragt ist der Rest bei Division durch 10).

Wir wissen: φ(10) = 4 und damit 7⁴ mod 10 = 1 und zerlegen daher 333 geschickt:

333 = 4 * 83 + 1

7³³³ = 7^{(4^.83+1)}

((7⁴)⁸³ ^. 7) mod 10 = (1⁸³ ^. 7) mod 10 = 7

Die Antwort - die letzte Stelle lautet 7.

Kontrolle mit DERIVE: Euler1