p teilt (n^p – n)

Behauptung:

Sei p eine beliebige Primzahl. Dann gilt: $$p~|~(n^p -n)\quad (n\geq 1)$$



Beweis:

Induktionsanfang: n = 1

Für jede Primzahl p gilt: $$p~|~0~=~(1^p -1)$$

Induktionsschritt: A(n) => A(n+1)

Zu zeigen:

$$p~|~((n+1)^p -(n+1))$$

Es 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 Vorraussetzung: $$p\text{ }|\text{ }(n^p -n)$$

Bleibt zu zeigen: $$p\text{ }|\text{ }\sum_{k=0}^{p-1} \binom{p}{k} n^k$$

Es gilt:

$$\binom{p}{k} = \frac{p!}{k!\cdot(p-k)!}$$

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 $$p~|~\binom{p}{k}$$ und $$p~|~\binom{p}{k} n^k$$
was in jedem Summanden der Summe vorkommt.

$$\Rightarrow p\text{ }|\text{ }\sum_{k=0}^{p-1} \binom{p}{k} n^k$$

q.e.d

Weiterlesen: Die Potenzmenge einer n-elementigen Menge enthält 2^n Elemente