Eulersche Funktion (Zahlentheorie)/Formel für Primzahlpotenz/Fakt/Beweis

Beweis

Eine Zahl ${}a$ ist genau dann teilerfremd zu einer Primzahlpotenz ${}p^{r}$, wenn sie teilerfremd zu ${}p$ selbst ist, und dies ist genau dann der Fall, wenn sie kein Vielfaches von ${}p$ ist. Unter den natürlichen Zahlen ${}<p^{r}$ sind genau die Zahlen

$0,p,2p,3p,\ldots ,(p^{r-1}-1)p$

Vielfache von ${}p$. Das sind ${}p^{r-1}$ Stück, und daher gibt es

${}p^{r}-p^{r-1}=p^{r-1}(p-1)\,$

Einheiten in ${}\mathbb {Z} /(p^{r})$. Also ist ${}{\varphi (p^{r})}=p^{r-1}(p-1)$.

Zur bewiesenen Aussage