Kleiner Satz von Fermat — Magie der Primzahlen
Kleiner Satz von Fermat (1640)
Wenn p prim ist und a nicht durch p teilbar, dann gilt:
a^(p-1) ≡ 1 (mod p)Beispiel
p = 7, a = 3:
3^6 = 729 = 104·7 + 1 → 729 mod 7 = 1 ✓
p = 11, a = 2:
2^10 = 1024 = 93·11 + 1 → 1024 mod 11 = 1 ✓Anwendungen
- Primzahltests: Wenn a^(n-1) ≢ 1 mod n, dann ist n keine Primzahl.
- RSA-Verschlüsselung: Direkt aus Fermat / Euler abgeleitet.
- Schnelles Potenz-Modulo: Reduziert Exponenten.
Eulerscher VerallgemeinerungFür allgemeines n (nicht nur prim): a^φ(n) ≡ 1 mod n, wenn ggT(a, n) = 1. φ(n) = Anzahl Zahlen 1..n−1, die teilerfremd zu n sind. Direkt aus φ(n) folgt RSA.