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:
am == 1 modulo p
für zwei teilerfremde Zahlen m und p.
Ein Spezialfall ergibt sich, wenn p eine Primzahl ist: dann gilt der Satz nämlich für alle m kleiner p.
Der Beweis beruht auf der Tatsache, dass -- wenn zwei Zahlen a und b zueinander inkongruent (modulo einer festen Zahl n) sind -- dann 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*a)*(2*a)*...*(p*a) modulo p , also
W == W*am modulo p
Wobei W das Produkt 1*2*3*...*p ist. Da es in Restklassenringen stehts ein multiplikatives Inverses gibt, kann man diese Kongruenzgleichung durch W dividieren und man erhält:
am == 1 modulo p