Satz von Euler-Fermat
Welche Ziffer steht am Ende von 7^{20} ? Die Zahl hat 17 Stellen – ausrechnen will das keiner. Schauen wir auf die letzten Ziffern der Potenzen: | k | 1 | 2 | 3 | 4 | 5 | 6 | |---|---|---|---|---|---|---| | 7^k | 7 | 49 | 343 | 2401 | 16807 | 117649 | | letzte Ziffer | 7 | 9 | 3 | 1 | 7 | 9 | Nach 4 Schritten kommt die 1 , danach wiederholt sich alles. Ist das Zufall? Nein! Der Satz von Euler-Fermat sagt vorher, wann spätestens die 1 kommt – ohne Probieren. Er ist das Herzstück der RSA-Verschlüsselung, mit der z. B. Online-Banking gesichert wird. Satz von Euler-Fermat Ist n eine natürliche Zahl und a eine ganze Zahl mit text{ggT}(a, n) = 1 , dann gilt a^{ varphi(n)} equiv 1 pmod{n} Dabei ist varphi die Euler'sche Phi-Funktion . In Worten: a^{ varphi(n)} lässt beim Teilen durch n den Rest 1 . Im Beispiel oben: varphi(10) = 4 , also 7^4 equiv 1 pmod{10} ✓ Sonderfall (kleiner Satz von Fermat): Ist n = p eine Primzahl und p nmid a , dann ist varphi(p) = p - 1 und a^{p - 1} equiv 1 pmod{p} Bedingung nicht vergessen: a und n müssen Teilerfremdheit|teilerfremd sein. Für a = 2 , n = 4 klappt es nicht: 2^{ varphi(4)} = 2^2 = 4 equiv 0 pmod 4 . So rechnet man große Potenzen aus Prüfe den kleinen Satz von Fermat für a = 2 und p = 5 . 2^{5 - 1} = 2^4 = 16 = 3 cdot 5 + 1 qquad Rightarrow qquad 2^4 equiv 1 pmod{5} ✓ Letzte Ziffer von 7^{20} Plan: Letzte Ziffer = Rest modulo 10 . - text{ggT}(7, 10) = 1 ✓ - varphi(10) = 4 - 20 = 5 cdot 4 + 0 7^{20} = left(7^4 right)^5 equiv 1^5 = 1 pmod{10}
Worum geht's?
Formel mit Erklärung
- 1Prüfen, ob ggT(a, n) = 1 ist.
- 2φ(n) berechnen.
- 3Die Hochzahl k durch φ(n) teilen: k = q · φ(n) + r.
- 4
- 5Die kleine Potenz a^r ausrechnen und mod n nehmen.
Beispiele
Zusammenfassung
Jetzt üben
Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff:
