Satz von Euler

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

Der Satz von Euler lautet: Für alle $a,n\in \mathbb {N}$ mit $\operatorname {ggT} (a,n)=1$ gilt

a^{\varphi (n)}\equiv 1{\pmod {n}}

Dabei ist $\operatorname {ggT}$ der größte gemeinsame Teiler der beiden natürlichen Zahlen $a$ und $n$ , und $\varphi (n)$ die eulersche φ-Funktion, nämlich die Anzahl der zu $n$ teilerfremden Reste modulo $n$ .

Für prime Moduli $p$ gilt $\varphi (p)=p-1$ , also geht für sie der Satz von Euler in den kleinen Satz von Fermat über.

Anwendungen

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

Was ist die letzte Ziffer im Dezimalsystem von 7²²², also welche Dezimalziffer 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{\pmod {10}}$

und wir erhalten

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

Allgemein gilt:

a^{b}\equiv a^{b{\bmod {\varphi }}(n)}{\pmod {n}}\qquad a,b,n\in \mathbb {N} \wedge \operatorname {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{\pmod {n}}$ folgt $x\equiv y{\pmod {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)}{\pmod {n}}

und da die $r_{i}$ invertierbar sind für alle $i$ , gilt

1\equiv a^{\varphi (n)}{\pmod {n}}

Alternativbeweis

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\leq a\leq n\mid \operatorname {ggT} (a,n)=1\}=(\mathbb {Z} /n\mathbb {Z} )^{\times }$ also $|G|=\varphi (n)$ , wobei die Operation von $G$ die Multiplikation modulo $n$ ist.