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.

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

Literatur

Bearbeiten
Bearbeiten