Satz von Euler

Der Satz von Euler, auch als "Satz von Euler-Fermat" bekannt nach Leonhard Euler und Pierre de Fermat, stellt eine Verallgemeinerung des kleinen Fermatschen Satzes auf.

Satz 164S (Satz von Euler)

Seien \(\displaystyle a,n\in\mathbb{N}\) und \(\displaystyle \ggT(a,n) = 1\) Dann gilt:
\(\displaystyle a^{\varphi(n)} \equiv 1\, (\mathrm{mod}\, n)\),
wobei \(\displaystyle \phi(n)\) die Eulersche Phi-Funktion bezeichnet.
Da für prime Moduln \(\displaystyle p\) gilt: \(\displaystyle f(p) = p-1\), geht für diese der Satz von Euler in den kleinen Satz von Fermat über.
 
 

Beweis

Sei \(\displaystyle (\mathbb{Z}/n\mathbb{Z})^\times=\{r_1, \dots, r_{\varphi(n)}\}\) die Menge der multiplikativ modulo \(\displaystyle n\) invertierbaren Elemente. Für jedes \(\displaystyle a\) mit \(\displaystyle \ggT(a,n)=1\) ist dann \(\displaystyle x\mapsto ax\) eine Permutation von \(\displaystyle (\mathbb{Z}/n\mathbb{Z})^\times\), denn aus \(\displaystyle ax \equiv ay \mod n\) folgt \(\displaystyle x \equiv y \mod n\).
Weil die Multiplikation kommutativ ist, folgt
\(\displaystyle r_1\cdots r_{\varphi(n)} \equiv (ar_1)\cdots (ar_{\varphi(n)})\) \(\displaystyle \equiv r_1\cdots r_{\varphi(n)}a^{\varphi(n)}\, \mod n\),
und da die \(\displaystyle r_i\) invertierbar sind für alle \(\displaystyle i\), gilt
\(\displaystyle 1 \equiv a^{\varphi(n)} \mod n\). \(\displaystyle \qed\)

Anwendungen

Der Satz von Euler dient der Reduktion großer Exponenten modulo n. Praktische Anwendung findet er in dieser Eigenschaft in der computergestützten Kryptographie, beispielsweise im RSA-Verschlüsselungsverfahren.

Beispiel

Was ist die letzte Dezimalstelle von \(\displaystyle 7^{222}\), also welcher Zahl ist \(\displaystyle 7^{222}\) kongruent modulo 10?
Zunächst bemerken wir, dass \(\displaystyle \ggT(7,10) = 1\) und dass \(\displaystyle \phi(10) = 4\). Also liefert der Satz von Euler
\(\displaystyle 7^{\, 4}\, \equiv 1\, \mathrm{mod}\, 10\)
und wir erhalten
\(\displaystyle 7^{222} = 7^{\, 4 \cdot 55 + 2} \) \(\displaystyle = (7^{\, 4})^{55} \cdot 7^{2} \equiv 1^{55} \cdot 7^{2} \equiv 49 \equiv 9\, \mathrm{mod}\, 10\, \)
Allgemein gilt:
\(\displaystyle a^b \equiv a^{b\, \mathrm{mod}\, \varphi(n)}\, \mathrm{mod}\, n\) mit \(\displaystyle a, b, n \in\mathbb{N} \wedge \mathrm{ggT}(a,n)=1\).

Das Buch der Natur ist mit mathematischen Symbolen geschrieben.

Galileo Galilei

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Satz von Euler aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе