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 nichtprime, beliebige Moduln $n\backslash in\backslash mathbb\{N\}$ dar. Er lautet:

$a^\{\backslash varphi(n)\}\; \backslash equiv\; 1\backslash ,(\backslash mathrm\{mod\}\backslash ,n)$

unter der Bedingung ggT(a,n) = 1, wobei φ(n) die Eulersche φ-Funktion bezeichnet. Da für prime Moduln p gilt φ(p) = p-1, geht für diese der Satz von Euler in den kleinen Satz von Fermat über.

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 7²²², also welcher Zahl ist 7²²² kongruent modulo 10?

Zunächst bemerken wir, dass ggT(7,10) = 1 und dass φ(10) = 4. Also liefert der Satz von Euler

$7^\{\backslash ,4\}\backslash ,\; \backslash equiv\; 1\backslash ,(\backslash mathrm\{mod\}\backslash ,10)$

und wir erhalten

$7^\{222\}\; =\; 7^\{\backslash ,4\; \backslash cdot\; 55\; +\; 2\}\; =\; (7^\{\backslash ,4\})^\{55\}\; \backslash cdot\; 7^\{2\}\; \backslash equiv\; 1^\{55\}\; \backslash cdot\; 7^\{2\}\; \backslash equiv\; 49\; \backslash equiv\; 9\backslash ,(\backslash mathrm\{mod\}\backslash ,10).$

Allgemein gilt:

$a^b\; \backslash equiv\; a^\{b\backslash ,\backslash mathrm\{mod\}\backslash ,\backslash varphi(n)\}\backslash ,(\backslash mathrm\{mod\}\backslash ,n)\backslash qquad\; a,\; b,\; n\; \backslash in\backslash mathbb\{N\}\; \backslash wedge\; \backslash mathrm\{ggT\}(a,n)=1$

Beweis des Satzes von Euler

---

Sei $(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})^\backslash times=\backslash \{r\_1,\; \backslash dots,\; r\_\{\backslash varphi(n)\}\backslash \}$ die Menge der multiplikativ modulo $n$ invertierbaren Elemente. Für jedes $a$ mit $\backslash operatorname\{ggT\}(a,n)=1$ ist dann $x\backslash mapsto\; ax$ eine Permutation von $(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})^\backslash times$, denn aus $ax\; \backslash equiv\; ay\backslash ,(\backslash operatorname\{mod\}\backslash ,n)$ folgt $x\; \backslash equiv\; y\backslash ,(\backslash operatorname\{mod\}\backslash ,n)$.

Weil die Multiplikation kommutativ ist, folgt

$r\_1\backslash cdots\; r\_\{\backslash varphi(n)\}\; \backslash equiv\; (ar\_1)\backslash cdots\; (ar\_\{\backslash varphi(n)\})\; \backslash equiv\; r\_1\backslash cdots\; r\_\{\backslash varphi(n)\}a^\{\backslash varphi(n)\}\backslash ,(\backslash operatorname\{mod\}\backslash ,n)$,

und da die $r\_i$ invertierbar sind für alle $i$, gilt

$1\; \backslash equiv\; a^\{\backslash varphi(n)\}\backslash ,(\backslash operatorname\{mod\}\backslash ,n)$.

Verwandte Einträge

---

• Kongruenz
• Teilbarkeit
• Zahlentheorie
• Kryptografie

Literatur

---

• H. Scheid Zahlentheorie. Spektrum Akademischer Verlag, 2003, ISBN 3-8274-1365-6

Zahlentheorie | Satz (Mathematik)

Теорема на Ойлер | Euler's theorem | Théorème d'Euler | משפט אוילר | Euler-Fermat-tétel | Teorema Euler | Teorema di Eulero | Stelling van Euler | Małe twierdzenie Fermata | Eulers sats