Eine zahlentheoretische Aussage, dass für eine Primzahl p und ganze Zahl a gilt a^p ≡ a (mod p); äquivalent: ist a nicht durch p teilbar, dann gilt a^(p-1) ≡ 1 (mod p).

Prinzip

Entsteht aus der Tatsache, dass die multiplikative Gruppe der Einheiten modulo einer Primzahl p zyklisch ist mit Ordnung p−1, sodass Potenzierung die Gruppenordnung respektiert und zu diesen Kongruenzen führt.

Demonstration

Für p=7 und a=3 rechnet man 3^6 = 729 ≡ 1 (mod 7), was den Satz bestätigt; ist a ein Vielfaches von p, ist a^p ≡ a trivial erfüllt.

Fehlanwendung

Den Satz zur Certifizierung von Primalität zu verwenden, ohne zusammengesetzte Zahlen zu prüfen, die die Kongruenz für viele Basen erfüllen (Carmichael-Zahlen), oder die reduzierte Form modulo einer zusammengesetzten Zahl ohne Bedingungen anzuwenden.

Konsequenz

Er liefert eine schnelle modular-exponentielle Identität, die in Primalitätstests, bei der Berechnung modularer Inversen für primäres Modul und in vielen Algorithmen der rechnerischen Zahlentheorie und Kryptographie verwendet wird.

Umkehrung

Eulers Satz verallgemeinert diese Aussage auf zusammengesetzte Moduli, indem p−1 durch Eulers ϕ(n) ersetzt wird; die Umkehrung schwächt die Aussage zu Gruppenordnungs-Aussagen in beliebigen endlichen Ringen.

Abgrenzung

Gilt nur wenn das Modul prim ist für die einfache Potenz p oder für ganze Zahlen teilerfremd zu p in der p−1-Form; impliziert keine Primalität und gilt nicht für beliebige zusammengesetzte Moduli.

Semantische Spannung

Spannung zu Eulers Satz und Carmichael-Gegenbeispielen: Fermats Kongruenz ist eine starke, leicht prüfbare Eigenschaft für Primzahlen, reicht aber allein nicht zur Primalitätsprüfung in Gegenwart von Pseudoprimzahlen.

Synthese

Eine grundlegende Kongruenz, die Primmoduli und Potenzierung verknüpft: Potenzen ganzer Zahlen reduzieren sich modulo eines Primzahlmoduls voraussagbar, wegen der endlichen multiplikativen Gruppenordnung.