Oder der kleine Fermat, wie er auch genannt wird. Wir zeigen den vollständigen Beweis des Satzes. Anschließend folgt noch ein anschauliches Rechenbeispiel.
Behauptung:
Sei p eine Primzahl und n eine natürliche Zahl mit ggT(n, p) = 1.
Dann gilt: p~|~n^{p-1}-1.
Beweis:
Mit Vollständiger Induktion lässt sich zeigen: p~|~(n^{p}-n) . Siehe: p teilt (n^p – n).
Es ist: n^{p}-n = n(n^{p-1}-1) . (Wir haben n einfach ausgeklammert).
Da p prim ist, gilt p~|~n oder p~|~(n^{p-1}-1) . Da p das ganze Produkt teil, muss es entweder den ersten Faktor oder den zweiten Faktor teilen.
Nach der Voraussetzung gilt ggT(n, p) = 1 . Daraus folgt:
p~|~n^{p-1}-1 .
p teilt also den zweiten Faktor. Würde p das n teilen, dann wäre ja ggT(n, p) = p . Dies ist aber nach Voraussetzung nicht so.
quod erat demonstrandum
Beispiel
Sehen wir uns nun ein Rechenbeispiel an:
Sei p die Primzahl 3 und n=4.
Dann sollte 3 die Zahl 4^{3-1}-1 teilen.
4^{3-1}-1 = 4^2 – 1 = 16 -1 = 15
15 ist tatsächlich ohne Rest durch 3 teilbar.