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.