## [Fermats Kleiner Satz](/de/node/63493) Definition Eine zahlentheoretische Aussage: Ist p eine Primzahl und a eine ganze Zahl, die nicht durch p teilbar ist, dann gilt a^{p−1} ≡ 1 (mod p); äquivalent gilt a^p ≡ a (mod p) für alle ganzen Zahlen a. ## Prinzip Prinzip Die Einheiten modulo einer Primzahl bilden eine endliche multiplikative Gruppe der Ordnung p−1, daher teilt die Ordnung jedes Elements p−1, wodurch a^{p−1} das Einselement in dieser Gruppe ist. ## Demonstration Demonstration Für p=7 und a=3 berechnet man 3^6 = 729, und 729 ≡ 1 (mod 7), ein konkretes Beispiel für die Kongruenz des Satzes. ## Fehlanwendung Fehlanwendung Die Kongruenz a^{n−1} ≡ 1 (mod n) unbedacht als Primzahltest verwenden: Viele zusammengesetzte n (Carmichael-Zahlen oder Fermat-Pseudoprimzahlen bezüglich a) können die Kongruenz für einige oder alle a erfüllen und zu falschen Positiven führen. ## Konsequenz Konsequenz Bildet die Grundlage einfacher modularer Inversenberechnungen und vieler Primalitätsheuristiken; es ist ein Ausgangspunkt für Eulers Satz und für Konstruktionen in elementarer Kryptographie bei primem Modul. ## Umkehrung Umkehrung Die Umkehrung gilt nicht: Wenn a^{n−1} ≡ 1 (mod n) für ein a mit gcd(a,n)=1, muss n nicht prim sein. Die Untersuchung der Umkehrung führt zu Pseudoprimen, Carmichael-Zahlen und stärkeren Primalitätstests wie dem Euler- oder starken Wahrscheinlichkeitsprimzahltest. ## Abgrenzung Abgrenzung Gilt klassisch nur für primen Modulus und setzt gcd(a,p)=1 voraus; für beliebige zusammengesetzte Moduli gilt die Aussage ohne Zusatzbedingungen nicht. ## Semantische Spannung Semantische Spannung Steht nahe bei Eulers Satz (der p−1 durch φ(n) ersetzt) und bei probabilistischen Primalitätstests; die Spannung entsteht aus dem Gegensatz zwischen exakten algebraischen Gruppenfakten und heuristischen Anwendungen beim Primzahltest, in denen Ausnahmen auftreten. ## Synthese Synthese Fermats Kleiner Satz fasst zusammen, dass die multiplikative Gruppe modulo einer Primzahl eine Ordnung teilt, was eine einfache Kongruenz liefert und als Ausgangspunkt für Verallgemeinerungen und Anwendungen in modularer Arithmetik dient.