Kleiner fermatscher Satz
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.