Der Kleine Fermatsche Satz, kurz der Kleine Fermat, ist ein Lehrsatz in der Zahlentheorie, aufgestellt im 17. Jahrhundert von Pierre de Fermat. Dieser Satz beschreibt eine allgemein gültige Kongruenz:
ap == a modulo p
wobei a eine ganze Zahl und p eine Primzahl sind. Falls a kein Vielfaches von p ist, kann man das Resultat in die häufig benutzten Form
ap-1 == 1 modulo p
bringen.
Der Beweis beruht auf der Tatsache, dass, wenn zwei Zahlen a und b zueinander inkongruent (modulo einer festen Zahl n) sind, auch die beiden Produkte x*a und x*b inkongruent modulo n sind für x>0. Im folgenden betrachtet man zum einen die Menge A aller Reste (mod p) - also alle natürlichen Zahlen kleiner als p, und zum anderen die Menge B, die diese Reste multipliziert mit a enthält. Zwei beliege Zahlen aus A sind zueinander inkongruent modulo p. Aus dem oberen Satz folgt, dass damit auch zwei beliebige Zahlen aus B zueinander inkongruent sind. Dadurch ergibt sich, dass das Produkt über allen Zahlen aus A kongruent zum Produkt aller Zahlen aus B ist:
1*2*3*...*(p-1) == (1*a)*(2*a)*...*((p-1)*a) modulo p , also
W == W*ap-1 modulo p
Wobei W das Produkt 1*2*3*...*(p-1) ist. Da es in Restklassenkörpern stets ein multiplikatives Inverses gibt, kann man diese Kongruenzgleichung durch W dividieren und man erhält:
ap-1 == 1 modulo p
Man kann den kleinen Fermatschen Satz zum Satz von Euler verallgemeinern: Für zwei teilerfremde Zahlen n und a gilt:
wobei φ(n) die Eulersche Phi-Funktion bezeichnet. Diese hat als Ergebnis die Anzahl der Zahlen zwischen 1 und n-1 welche teilerfremd zu n sind. Ist n eine Primzahl, so ist φ(n) = n-1, so dass man Fermats kleinen Satz als Spezialfall erhält.