##  [Fermats Kleiner Satz](/de/node/58038) 

 Definition

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

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

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

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

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

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

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

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

Synthese

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