Die eulersche Phi-Funktion

$\varphi(m)$ ist die Anzahl der ganzen Zahlen $r$ mit $1\le r\le m$ und $\operatorname{ggT}(r,m)=1$.

Für die verschiedenen Primteiler $p$ von $m$ gilt $\varphi(m)=m\prod_{p\mid m}(1-1/p)$. Bei $m=p^k$ folgt $\varphi(p^k)=p^k-p^{k-1}$.