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 ${\displaystyle n\in \mathbb {N} }$ dar.

Aussage

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

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

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

Für prime Moduli ${\displaystyle p}$ gilt ${\displaystyle \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 ${\displaystyle n}$. Aus ihm folgt für ganze Zahlen ${\displaystyle k}$, dass ${\displaystyle 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 i​st die letzte Ziffer i​m Dezimalsystem v​on 7²²², a​lso welche Dezimalziffer i​st 7²²² kongruent modulo 10?

Zunächst bemerken wir, d​ass ggT(7,10) = 1 u​nd dass φ(10) = 4. Also liefert d​er Satz v​on Euler

${\displaystyle 7^{4}\equiv 1{\pmod {10}}}$

und w​ir erhalten

${\displaystyle 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:

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

Weil d​ie Multiplikation kommutativ ist, folgt

${\displaystyle 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 ${\displaystyle r_{i}}$ invertierbar sind für alle ${\displaystyle i}$, gilt

${\displaystyle 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 ${\displaystyle G}$ mit endlicher Ordnung ${\displaystyle m}$ ist die ${\displaystyle m}$-te Potenz jedes Elements das Einselement. Hier ist ${\displaystyle G=\{1\leq a\leq n\mid \operatorname {ggT} (a,n)=1\}=(\mathbb {Z} /n\mathbb {Z} )^{\times }}$ also ${\displaystyle |G|=\varphi (n)}$, wobei die Operation von ${\displaystyle G}$ die Multiplikation modulo ${\displaystyle 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.