Der kleine Satz von Fermat

Behauptung:

Sei p eine Primzahl und n eine natürliche Zahl mit ggT(n, p) = 1.
Dann gilt: [latex]p~|~n^{p-1}-1[/latex]

Beweis:

Mit Vollständiger Induktion lässt sich zeigen: p | (np – n) [Beweis]

Es ist: [latex]n^{p}-n = n(n^{p-1}-1)[/latex]

Da p prim ist, gilt p | n oder [latex]p~|~(n^{p-1}-1)[/latex]

Da ggT(n, p) = 1 folgt: [latex]p~|~n^{p-1}-1[/latex]

q.e.d.