Behauptung
Sei \(p\) eine beliebige Primzahl. Dann gilt:
\(p~|~(n^{p} – n)\) für alle \(n \ge 1\)
Dieser Beweis ist Grundlage für den kleinen Satz von Fermat.
Beweis
Induktionsanfang: n = 1
Für jede Primzahl \(p\) gilt:
\(p~|~0 = (1^{p}-1)\)
Induktionsschritt: n => n+1
Angenommen, die Aussage ist richtig für alle natürlichen Zahlen bis n. Dann folgt daraus, dass die Aussage auch richtig ist für n+1:
\(p~|~((n+1)^{p}-(n+1))\)
Der Minuend (der erste Teil der Subtraktion) lässt sich mit der Formel des Binomialkoeffizienten umformen. Damit gilt:
\(\begin{align*}(n+1)^p-(n+1)\\
= \sum_{k=0}^{p} \binom{p}{k} n^k 1^{n-k} \text { } -(n+1)\\
= \sum_{k=0}^{p-1} \binom{p}{k} n^k\text { } + \binom{p}{0} n^0 + \binom{p}{p} n^p -n-1\\
= \sum_{k=0}^{p-1} \binom{p}{k} n^k\text { } +n^p -n \end{align*}\)
Nach der Voraussetzung teilt p den zweiten Summanden:
\(p~|~n^{p}-n\)
Es bleibt also noch zu zeigen, dass p den ersten Summanden teilt:
\(\begin{align*}p~|~\sum_{k=0}^{p-1} \binom{p}{k} n^k \end{align*}\)
Es gilt:
\(\begin{align*} \binom{p}{k} = \frac{p!}{k!\cdot(p-k)!} \end{align*}\)
ist eine natürliche Zahl.
\(p\) ist ein Faktor des Zählers.
\(p\) ist prim und größer als \(k\) und \((p-k)\), daher kann \(p\) nicht weggekürzt werden.
Somit gilt:
\(\begin{align*} p~|~\binom{p}{k} \text{ und } p~|~\binom{p}{k} n^k \end{align*}\)
was in jedem Summanden der Summe vorkommt.
⇒ \(\begin{align*} p~|~\sum_{k=0}^{p-1} \binom{p}{k} n^k \end{align*}\)
quod erat demonstrandum