Eulersche Phi-Funktion/Chinesischer Restsatz/Berechnung/Bemerkung

Aus der Einheitenversion des Chinesischen Restsatzes folgt für die Eulersche Funktion, wenn ${\displaystyle {}n=p_{1}^{r_{1}}\cdot p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}}$ 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}})\,.}$

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

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

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