Elementarer Satz der Zahlentheorie, der aussagt, dass für eine Primzahl p und eine ganze Zahl a mit p ∤ a gilt a^{p-1} ≡ 1 (mod p); äquivalent gilt a^p ≡ a (mod p) für alle ganzen Zahlen a.

Prinzip

Die multiplikative Gruppe der Einheiten modulo einer Primzahl p ist zyklisch von Ordnung p−1, sodass jedes Element a mit gcd(a,p)=1 eine Ordnung hat, die p−1 teilt, woraus a^{p-1} ≡ 1 folgt.

Demonstration

Beispiel: a=2, p=7 → 2^6 = 64 ≡ 1 (mod 7). Eine gruppentheoretische Begründung verwendet, dass {1,a,a^2,...,a^{p-2}} die nichtnullten Restklassen modulo p permutiert; multipliziert ergibt sich a^{p-1} ≡ 1.

Fehlanwendung

Den Kongruenzsatz als biconditionalen Primalitätstest verwenden: zusammengesetzte Zahlen können für manche a a^{n-1} ≡ 1 (mod n) erfüllen (Carmichael- oder Pseudoprimes), und der Satz versagt, wenn gcd(a,p) ≠ 1.

Konsequenz

Grundlage vieler Argumente in der modularen Arithmetik, einfacher Primalitätstests und Algorithmen; verallgemeinert sich zu Eulers Satz für zusammengesetzte Moduli mittels der Euler-φ-Funktion.

Umkehrung

Die naive Umkehrung ‚wenn a^{n-1} ≡ 1 (mod n) für viele a gilt, dann ist n prim‘ ist falsch; korrekt ist: Scheitert die Kongruenz für ein a, so ist n zusammengesetzt, aber Bestehen garantiert nicht Primheit.

Abgrenzung

Voraussetzung ist, dass p prim ist und gcd(a,p)=1 für die Formulierung a^{p-1} ≡ 1; die Variante a^p ≡ a gilt für alle a modulo p. Gilt nicht für zusammengesetzte Moduli ohne Ersetzung von p−1 durch φ(n).

Semantische Spannung

Wird oft mit Eulers Satz und probabilistischen Primalitätstests verwechselt; Spannung entsteht durch die deterministische Kongruenz und das Vorkommen von Pseudoprimes, die Primverhalten für viele Basen nachahmen.

Synthese

Fermats Kleiner Satz verbindet die algebraische Struktur der multiplikativen Restklassen modulo einer Primzahl mit einfachen Kongruenzen: Einheiten haben Ordnung teilend p−1, woraus a^{p-1} ≡ 1 (mod p) folgt und zahlreiche Anwendungen in der Zahlentheorie ergeben.