Kleiner Satz von Fermat

Erklärung

Der kleine Satz von Fermat beschreibt Potenzen modulo einer Primzahl $p$: Ist $a$ nicht durch $p$ teilbar, so ist $a^{p-1} - 1$ durch $p$ teilbar. Multipliziert man mit $a$, erhält man die Form

die für alle ganzen Zahlen $a$ gilt, auch für Vielfache von $p$.

Beweisidee: Die Zahlen $a, 2a, \ldots, (p-1)a$ haben modulo $p$ paarweise verschiedene Reste ungleich $0$, sind also eine Umordnung von $1, 2, \ldots, p-1$. Multipliziert man alle, folgt $a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod p$. Da $(p-1)!$ zu $p$ teilerfremd ist, darf man kürzen.

Anwendungen:

• Große Potenzen reduzieren: Ist $p \nmid a$, darf man Exponenten modulo $p - 1$ verkleinern.
• Primzahltest: Gilt $a^{n-1} \not\equiv 1 \pmod n$ für ein $a$ mit $\operatorname{ggT}(a, n) = 1$, dann ist $n$ sicher keine Primzahl.

Der Satz ist ein Spezialfall des Satzes von Euler, denn für Primzahlen gilt $\varphi(p) = p - 1$.

Beispiele

Rest von $3^{100}$ modulo $7$: Nach Fermat ist $3^6 \equiv 1 \pmod 7$ (Probe: $3^6 = 729 = 104 \cdot 7 + 1$). Mit $100 = 16 \cdot 6 + 4$ folgt

$15$ ist keine Primzahl: $2^{14} = 16\,384 \equiv 4 \pmod{15}$. Wäre $15$ prim, müsste der Rest $1$ sein.

Typische Fehler

• Die Umkehrung für wahr halten. Aus $a^{n-1} \equiv 1 \pmod n$ folgt nicht, dass $n$ prim ist. Gegenbeispiel: $341 = 11 \cdot 31$, aber $2^{10} = 1024 = 3 \cdot 341 + 1$, also $2^{340} = \left(2^{10}\right)^{34} \equiv 1 \pmod{341}$. Solche Zahlen heißen Fermatsche Pseudoprimzahlen.
• Die Voraussetzung $p \nmid a$ vergessen. Für $a = 6$ und $p = 3$ ist $6^2 = 36 \equiv 0 \pmod 3$, nicht $1$. Ohne Voraussetzung gilt nur $a^p \equiv a$.
• Den Exponenten modulo $p$ statt modulo $p - 1$ reduzieren. Bei $3^{100}$ modulo $7$ zählt $100 \bmod 6 = 4$, nicht $100 \bmod 7 = 2$.
• Den Satz für zusammengesetzte Moduln verwenden. Für $m = 15$ braucht man den Satz von Euler mit $\varphi(15) = 8$, nicht den Exponenten $14$.