Eulersche Phi-Funktion/Chinesischer Restsatz/Berechnung/Bemerkung

Aus der Einheitenversion des Chinesischen Restsatzes folgt für die Eulersche Funktion, wenn ${}n=p_{1}^{r_{1}}\cdot p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}$ die Primfaktorzerlegung ist, die Identität

${}\varphi (n)=\varphi (p_{1}^{r_{1}})\cdot \varphi (p_{2}^{r_{2}})\cdots \varphi (p_{k}^{r_{k}})\,.$

Man muss also nur noch ${}\varphi (p^{r})$ für eine Primzahl ${}p$ berechnen, wobei natürlich ${}\varphi (p)=p-1$ ist. Für ${}p^{r}$ mit ${}r\geq 2$ ist eine Zahl ${}0<a<p^{r}$ genau dann teilerfremd zu ${}p^{r}$, wenn sie teilerfremd zu ${}p$ ist, und das ist genau dann der Fall, wenn sie kein Vielfaches von ${}p$ ist. Die Vielfachen von ${}p$ im beschriebenen Intervall sind genau die Zahlen ${}bp$ mit ${}0\leq b<p^{r-1}$. Dies sind ${}p^{r-1}$ Stück, sodass es also ${}p^{r}-p^{r-1}=p^{r-1}(p-1)$ Einheiten gibt. Wir erhalten demnach

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

und insgesamt

$\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)\,.$