Satz von Euler

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Der Titel dieses Artikels ist mehrdeutig. Weitere Bedeutungen sind unter Satz von Euler (Begriffsklärung) aufgeführt.

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[Bearbeiten | Quelltext bearbeiten]

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. Für prime Moduli p gilt φ(p) = p–1, also geht für sie der Satz von Euler in den kleinen Satz von Fermat über.

Anwendungen[Bearbeiten | Quelltext bearbeiten]

Der Satz von Euler dient der Reduktion großer Exponenten modulo n. Aus ihm folgt für ganze Zahlen k, dass . Praktische Anwendung findet er in dieser Eigenschaft in der computergestützten Kryptographie, beispielsweise im RSA-Verschlüsselungsverfahren.

Beispiel[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]