Antworten
⇒Der Satz von Euler verallgemeinert den kleinen Fermatschen Satz und wird deshalb auch Satz von Euler-Fermat genannt. Zur Erinnerung – der kleine Fermat besagt: ap-1mod p = 1
Der Satz von Euler:
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 = 1für n und m prima(n-1) (m-1) mod n.m = 1 (a teilerfremd zu m und n)
Der Satz des Euler ist eine Erweiterung des Satzes von Femant und beschäftigt sich mit den Potenzen von ganzen rationalen Zahlen.
