Das Kefk Network Wiki befindet sich im Testbetrieb.

Satz von Euler

Aus Kefk.

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\in\mathbb{N}$ dar. Er lautet:

$a^{\varphi(n)} \equiv 1\,(\mathrm{mod}\,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 Ziffer im Dezimalsystem von 7²²², also welche 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^{\,4}\, \equiv 1\,(\mathrm{mod}\,10)$

und wir erhalten

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

Allgemein gilt:

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

Beweis des Satzes von Euler

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