- Satz von Euler-Fermat
-
Der Satz von Euler, auch als Satz von Euler-Fermat bekannt nach Leonhard Euler und Pierre de Fermat, stellt eine Verallgemeinerung des kleinen fermatschen Satzes auf nichtprime, beliebige Moduli dar. Er lautet:
unter der Bedingung ggT(a,n) = 1, wobei φ(n) die Eulersche φ-Funktion bezeichnet, nämlich die Anzahl der zu n teilerfremden Reste modulo n. Da für prime Moduli p gilt φ(p) = p-1, geht für diese der Satz von Euler in den kleinen Satz von Fermat über.
Inhaltsverzeichnis
Anwendungen
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.
Beispiel
Was ist die letzte Ziffer im Dezimalsystem von 7222, also welche 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
Allgemein gilt:
Beweis des Satzes von Euler
Sei die Menge der multiplikativ modulo n invertierbaren Elemente. Für jedes a mit ist dann eine Permutation von , denn aus folgt .
Weil die Multiplikation kommutativ ist, folgt
- ,
und da die ri invertierbar sind für alle i, gilt
- .
Alternativbeweis
Der Satz von Euler ist ein Sonderfall des folgenden Satzes aus den Elementen der Gruppentheorie: In jeder Gruppe G mit endlicher Ordnung m ist die m-te Potenz jedes Elements das Einselement. Hier ist also , wobei die Operation von G die Multiplikation modulo n ist.
Siehe auch
Literatur
- Harald Scheid: Zahlentheorie, Spektrum Akademischer Verlag, 2003, ISBN 3-8274-1365-6
Wikimedia Foundation.