Satz von Euler

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel beschreibt eine Verallgemeinerung des kleinen fermatschen Satzes.

Der Satz von Euler, auch als Satz von Euler-Fermat benannt nach Leonhard Euler und Pierre de Fermat, stellt eine Verallgemeinerung des kleinen fermatschen Satzes auf beliebige (nicht notwendigerweise prime) Moduli n\in\mathbb{N} dar.

Aussage[Bearbeiten]

Er lautet:

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

unter der Bedingung ggT(a,n) = 1, wobei φ(n) die eulersche φ-Funktion bezeichnet, nämlich die Anzahl der zu n teilerfremden Reste modulo n. Für prime Moduli p gilt φ(p) = p–1, also geht für sie der Satz von Euler in den kleinen Satz von Fermat über.

Anwendungen[Bearbeiten]

Der Satz von Euler dient der Reduktion großer Exponenten modulo n. Aus ihm folgt für ganze Zahlen k, dass a^x\equiv a^{x+k\cdot\varphi(n)}\pmod n. Praktische Anwendung findet er in dieser Eigenschaft in der computergestützten Kryptographie, beispielsweise im RSA-Verschlüsselungsverfahren.

Beispiel[Bearbeiten]

Was ist die letzte Ziffer im Dezimalsystem von 7222, also welche Zahl ist 7222 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}(\mathrm{mod}\,10) \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[Bearbeiten]

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).

Weil die Multiplikation kommutativ ist, folgt

r_1\cdots r_{\varphi(n)} \equiv (ar_1)\cdots (ar_{\varphi(n)}) \equiv r_1\cdots r_{\varphi(n)}a^{\varphi(n)}\,(\operatorname{mod}\,n),

und da die r_i invertierbar sind für alle i, gilt

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

Alternativbeweis[Bearbeiten]

Der Satz von Euler ist eine direkte Folgerung aus dem Satz von Lagrange aus der Gruppentheorie: In jeder Gruppe G mit endlicher Ordnung m ist die m-te Potenz jedes Elements das Einselement. Hier ist G=\{1\le a\le n\mid\operatorname{ggT}(a,n)=1\} also |G|=\varphi(n), wobei die Operation von G die Multiplikation modulo n ist.

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]