Satz von Euler

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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.

[Bearbeiten] 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.

[Bearbeiten] 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$

[Bearbeiten] 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)$ .