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 : 1p−1=1−1=0≡0 mod p
IV: np−n≡0 mod p.
IS: Nach dem binomische Satz gilt:
(n+1)p−(n+1)=
=np+∑k=1p−1(kp)np−k+1−n−1=
≡np+1−n−1=np−n≡0 mod p,
da (kp)≡0 mod p für 0<k<p gilt.