Satz von Euler

Der Satz von Euler, auch als Satz von Euler-Fermat benannt nach Leonhard Euler und Pierre de Fermat, stellt eine Verallgemeinerung des kleinen fermatschen Satzes auf beliebige (nicht notwendigerweise prime) Moduli dar.

Aussage

Der Satz von Euler lautet: Für alle mit gilt

.

Dabei ist der größte gemeinsame Teiler der beiden natürlichen Zahlen und , und die eulersche φ-Funktion, nämlich die Anzahl der zu teilerfremden Reste modulo .

Für prime Moduli gilt , also geht für sie der Satz von Euler in den kleinen Satz von Fermat über.

Anwendungen

Der Satz von Euler dient der Reduktion großer Exponenten modulo . Aus ihm folgt für ganze Zahlen , dass . 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 Dezimalziffer 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 invertierbaren Elemente. Für jedes mit ist dann eine Permutation von , denn aus folgt .

Weil die Multiplikation kommutativ ist, folgt

,

und da die invertierbar sind für alle , gilt

.

Alternativbeweis

Der Satz von Euler ist eine direkte Folgerung aus dem Satz von Lagrange aus der Gruppentheorie: In jeder Gruppe mit endlicher Ordnung ist die -te Potenz jedes Elements das Einselement. Hier ist also , wobei die Operation von die Multiplikation modulo ist.

Siehe auch

Literatur