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
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:
![{\displaystyle a^{b}\equiv a^{b{\bmod {\varphi }}(n)}{\pmod {n}}\qquad a,b,n\in \mathbb {N} \wedge \operatorname {ggT} (a,n)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a0da39ed1ec341d6d89d344cc64a523aeeec322)
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
- Carmichael-Funktion
- Kongruenz
- Teilbarkeit
- Zahlentheorie
- Kryptographie
Literatur
- Harald Scheid: Zahlentheorie, Spektrum Akademischer Verlag, 2003, ISBN 3-8274-1365-6
Weblinks
- Christian Spannagel: Sätze von Euler und Fermat. Vorlesungsreihe, 2012.