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 a,n∈Na,n\in\mathbb{N} und ggT⁡(a,n)=1\ggT(a,n) = 1 Dann gilt:
aφ(n)≡1 (mod n)a^{\varphi(n)} \equiv 1\, (\mathrm{mod}\, n),
wobei φ(n)\phi(n) die Eulersche Phi-Funktion bezeichnet.
Da für prime Moduln pp gilt: f(p)=p−1f(p) = p-1, geht für diese der Satz von Euler in den kleinen Satz von Fermat über.
 
 

Beweis

Sei (Z/nZ)×={r1,…,rφ(n)}(\mathbb{Z}/n\mathbb{Z})^\times=\{r_1, \dots, r_{\varphi(n)}\} die Menge der multiplikativ modulo nn invertierbaren Elemente. Für jedes aa mit ggT⁡(a,n)=1\ggT(a,n)=1 ist dann x↦axx\mapsto ax eine Permutation von (Z/nZ)×(\mathbb{Z}/n\mathbb{Z})^\times, denn aus ax≡aymod  nax \equiv ay \mod n folgt x≡ymod  nx \equiv y \mod n.
Weil die Multiplikation kommutativ ist, folgt
r1⋯rφ(n)≡(ar1)⋯(arφ(n))r_1\cdots r_{\varphi(n)} \equiv (ar_1)\cdots (ar_{\varphi(n)}) ≡r1⋯rφ(n)aφ(n) mod  n\equiv r_1\cdots r_{\varphi(n)}a^{\varphi(n)}\, \mod n,
und da die rir_i invertierbar sind für alle ii, gilt
1≡aφ(n)mod  n1 \equiv a^{\varphi(n)} \mod n. □\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 72227^{222}, also welcher Zahl ist 72227^{222} kongruent modulo 10?
Zunächst bemerken wir, dass ggT⁡(7,10)=1\ggT(7,10) = 1 und dass φ(10)=4\phi(10) = 4. Also liefert der Satz von Euler
7 4 ≡1 mod 10 7^{\, 4}\, \equiv 1\, \mathrm{mod}\, 10
und wir erhalten
7222=7 4⋅55+27^{222} = 7^{\, 4 \cdot 55 + 2} =(7 4)55⋅72≡155⋅72≡49≡9 mod 10 = (7^{\, 4})^{55} \cdot 7^{2} \equiv 1^{55} \cdot 7^{2} \equiv 49 \equiv 9\, \mathrm{mod}\, 10\,
Allgemein gilt:
ab≡ab mod φ(n) mod na^b \equiv a^{b\, \mathrm{mod}\, \varphi(n)}\, \mathrm{mod}\, n mit a,b,n∈N∧ggT(a,n)=1a, b, n \in\mathbb{N} \wedge \mathrm{ggT}(a,n)=1.

"Offensichtlich" ist das gefährlichste Wort in der Mathematik.

Eric Temple Bell

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е
Datenschutzerklärung

 

Elementare Zahlentheorie