Satz von Euler
# 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$^{222}$, also welche Dezimalziffer ist 7$^{222}$ 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.