\(p\) sei prim, \(n\) natürlich:
Ich tu mal so, als ob ich dem kleinen Fermat nie begegnet wäre.
Daher Beweis mit vollst. Induktion über \(n\):
IA: \(n=1: \; 1^p-1=1-1=0\equiv 0\) mod \(p\)
IV: \(n^p-n \equiv 0\) mod \(p\).
IS: Nach dem binomische Satz gilt:
\((n+1)^p-(n+1)=\)
\(=n^p+\sum_{k=1}^{p-1}{p\choose k}n^{p-k}+1-n-1=\)
\(\equiv n^p+1-n-1=n^p-n\equiv 0\) mod \(p\),
da \({p\choose k}\equiv 0\) mod \(p\) für \(0<k<p\) gilt.
