3. Elementare Zahlentheorie

E Primzahltest

Kleiner fermatscher Satz

Der kleine fermatsche Satz, kurz „der kleine Fermat“, ist ein Lehrsatz der Zahlentheorie. Er macht eine Aussage über die Eigenschaften von Primzahlen. Der Satz beschreibt die allgemeingültige Kongruenz:
 
ap ≡ a (mod p)
 
wobei a eine ganze Zahl und p eine Primzahl ist.
 
Falls a kein Vielfaches von p ist, kann man das Resultat in die häufig benutzte Form ap − 1 ≡ 1 (mod p) bringen.

Diskussion