Satz von Euler

Erklärung

Der Satz von Euler verallgemeinert den kleinen Satz von Fermat auf beliebige Moduln $m$: Ist $a$ zu $m$ teilerfremd, so ist $a^{\varphi(m)} - 1$ durch $m$ teilbar. Für eine Primzahl $m = p$ ist $\varphi(p) = p - 1$, und man erhält genau den Satz von Fermat.

Beweisidee: Die $\varphi(m)$ zu $m$ teilerfremden Reste $r_1, \ldots, r_{\varphi(m)}$ werden durch Multiplikation mit $a$ nur umgeordnet. Vergleicht man die Produkte, folgt $a^{\varphi(m)} \cdot \prod r_j \equiv \prod r_j \pmod m$, und das Produkt darf man kürzen, weil es zu $m$ teilerfremd ist.

Folgerungen:

• Exponenten reduzieren: $a^k \equiv a^{k \bmod \varphi(m)} \pmod m$, solange $\operatorname{ggT}(a, m) = 1$.
• Inverses: $a^{\varphi(m) - 1}$ ist ein Inverses von $a$ modulo $m$.
• RSA: Für $n = p \cdot q$ mit verschiedenen Primzahlen $p, q$ und $d \cdot e \equiv 1 \pmod{\varphi(n)}$ gilt $(x^e)^d \equiv x \pmod n$; darauf beruhen Ver- und Entschlüsselung.

Beispiele

Letzte zwei Ziffern von $3^{123}$: Gesucht ist der Rest modulo $100$. Es gilt $\varphi(100) = 40$ und $\operatorname{ggT}(3, 100) = 1$. Mit $123 = 3 \cdot 40 + 3$ folgt

Die letzten beiden Ziffern sind $27$.

Inverses von $3$ modulo $10$: $\varphi(10) = 4$, also ist $3^{4-1} = 27 \equiv 7 \pmod{10}$ das Inverse. Probe: $3 \cdot 7 = 21 \equiv 1 \pmod{10}$.

Typische Fehler

• Die Teilerfremdheit nicht prüfen. Für $a = 2$, $m = 10$ ist $2^{\varphi(10)} = 2^4 = 16 \equiv 6 \pmod{10}$, nicht $1$.
• $\varphi(m) = m - 1$ einsetzen. Das stimmt nur für Primzahlen. Für $m = 100$ ist der Exponent $40$, nicht $99$.
• $\varphi(m)$ für die kleinste Periode halten. Der Satz garantiert nur, dass $\varphi(m)$ eine Periode ist. Oft reicht ein kleinerer Exponent: $7^4 \equiv 1 \pmod{100}$, obwohl $\varphi(100) = 40$.