Aus
der Einheitenversion
des Chinesischen Restsatzes folgt für die
Eulersche Funktion,
wenn
die Primfaktorzerlegung ist, die Identität
-
![{\displaystyle {}\varphi (n)=\varphi (p_{1}^{r_{1}})\cdot \varphi (p_{2}^{r_{2}})\cdots \varphi (p_{k}^{r_{k}})\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ad2e3a800d64365b655c0dfac423d17ed37b832)
Man muss also nur noch
für eine Primzahl
berechnen, wobei natürlich
ist. Für
mit
ist eine Zahl
genau dann teilerfremd zu
, wenn sie teilerfremd zu
ist, und das ist genau dann der Fall, wenn sie kein Vielfaches von
ist. Die Vielfachen von
im beschriebenen Intervall sind genau die Zahlen
mit
.
Dies sind
Stück, so dass es also
Einheiten gibt. Wir erhalten demnach
-
![{\displaystyle {}\varphi (p^{r})=p^{r-1}(p-1)\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d81a36d64888e6dda082a2d4f23f615018220646)
und insgesamt
-
![{\displaystyle \varphi (n)=p_{1}^{r_{1}-1}(p_{1}-1)\cdot p_{2}^{r_{2}-1}(p_{2}-1)\cdots p_{k}^{r_{k}-1}(p_{k}-1)\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1b72b7a45fece5a8853d77964c7ecfdd5d827cb)