Satz von Euler
Table of contents |
2 Anwendungen 3 Beweis des Satzes von Euler 4 Verwandte Einträge 5 Literatur |
Überblick
Der Satz von Euler, auch als "Satz von Euler-Fermat" bekannt, stellt eine Verallgemeinerung des kleinen Fermatschen Satzes auf nichtprime, beliebige Moduln dar. Er lautet:
unter der Bedingung ggT(a,n) = 1, wobei φ(n) die Eulersche φ-Funktion bezeichnet. Da für prime Moduln p gilt φ(p) = p-1, geht für diese der Satz von Euler in den kleinen Satz von Fermat über.
Der Satz von Euler dient der Reduktion großer Exponenten modulo n. Praktische Anwendung findet er in dieser Eigenschaft in der computergestützten Kryptographie, beispielsweise im RSA-Verschlüsselungsverfahren.
Was ist die letzte Dezimalstelle von 7222, also welcher Zahl ist 7222 kongruent modulo 10?
Zunächst bemerken wir, dass ggT(7,10) = 1 und dass φ(10) = 4. Also liefert der Satz von Euler
und wir erhalten
Sei r1,r2,...,rφ(n) ein primes Restsytem modulo n. Dann ist auch für jedes a mit ggT(a,n) = 1 ar1,ar2,...,arφ(n) ein primes Restsystem. Da von
auf
geschlossen werden kann, ergibt sich, dass
denn die ar1,ar2,...,arφ(n) müssen, weil sie auch ein primes Restsystem modulo n bilden, in einer gewissen Reihenfolge kongruent zu den r1,r2,...,rφ(n) sein.
Da aber zu jedem ri wegen
für alle i mit 1 ≤ i ≤ φ(n) ein multiplikatives Inverses modulo n existiert, können wir auf beiden Seiten des Kongruenzzeichens jedes der ri mit seinem Inversen multplizieren und erhalten
also den Satz von Euler.
Anwendungen
Beispiel
Beweis des Satzes von Euler
Verwandte Einträge
Literatur