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,nNa,n\in\mathbb{N} und ggT(a,n)=1\ggT(a,n) = 1 Dann gilt:
aφ(n)1(modn)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)=p1f(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 xaxx\mapsto ax eine Permutation von (Z/nZ)×(\mathbb{Z}/n\mathbb{Z})^\times, denn aus axaymodnax \equiv ay \mod n folgt xymodnx \equiv y \mod n.
Weil die Multiplikation kommutativ ist, folgt
r1rφ(n)(ar1)(arφ(n))r_1\cdots r_{\varphi(n)} \equiv (ar_1)\cdots (ar_{\varphi(n)}) r1rφ(n)aφ(n)modn\equiv r_1\cdots r_{\varphi(n)}a^{\varphi(n)}\, \mod n,
und da die rir_i invertierbar sind für alle ii, gilt
1aφ(n)modn1 \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
741mod10 7^{\, 4}\, \equiv 1\, \mathrm{mod}\, 10
und wir erhalten
7222=7455+27^{222} = 7^{\, 4 \cdot 55 + 2} =(74)557215572499mod10= (7^{\, 4})^{55} \cdot 7^{2} \equiv 1^{55} \cdot 7^{2} \equiv 49 \equiv 9\, \mathrm{mod}\, 10\,
Allgemein gilt:
ababmodφ(n)modna^b \equiv a^{b\, \mathrm{mod}\, \varphi(n)}\, \mathrm{mod}\, n mit a,b,nNggT(a,n)=1a, b, n \in\mathbb{N} \wedge \mathrm{ggT}(a,n)=1.

Die Furcht vor der Mathematik steht der Angst erheblich näher als der Ehrfurcht.

Felix Auerbach

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е