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 $\mathrm{ggT}(a,n)=1$ gilt

$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$.

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

Für prime Moduli $p$ gilt $\phi (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 \phi (n)}(\mathrm{mod}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(\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 49(\mathrm{mod}10)\equiv 9(\mathrm{mod}10)$.

Allgemein gilt:

$a^b\equiv a^{bmod\phi (n)}(\mathrm{mod}n)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_{\phi (n)}\}$ die Menge der multiplikativ modulo $n$ invertierbaren Elemente. Für jedes $a$ mit $\mathrm{ggT}(a,n)=1$ ist dann $x\mapsto ax$ eine Permutation von $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$, denn aus $ax\equiv ay(\mathrm{mod}n)$ folgt $x\equiv y(\mathrm{mod}n)$.

Weil die Multiplikation kommutativ ist, folgt

$r_1\cdots r_{\phi (n)}\equiv (a{r}_1)\cdots (a{r}_{\phi (n)})\equiv r_1\cdots r_{\phi (n)}{a}^{\phi (n)}(\mathrm{mod}n)$,

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

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

Siehe auch

• Carmichael-Funktion
• Kongruenz
• Teilbarkeit
• Zahlentheorie
• Kryptographie

Literatur

• Harald Scheid: Zahlentheorie, Spektrum Akademischer Verlag, 2003, ISBN 3-8274-1365-6

Weblinks

• Christian Spannagel: Sätze von Euler und Fermat. Vorlesungsreihe, 2012.