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.

AussageBearbeiten

Der Satz von Euler lautet:

 

Er gilt unter der Bedingung  , mit  , wobei   der größte gemeinsame Teiler der beiden natürlichen Zahlen   und   ist und   die eulersche φ-Funktion bezeichnet, 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.

AnwendungenBearbeiten

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.

BeispielBearbeiten

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 EulerBearbeiten

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

 .

AlternativbeweisBearbeiten

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 auchBearbeiten

LiteraturBearbeiten

WeblinksBearbeiten