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

 Definition

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

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

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

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

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

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

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

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

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.