= Euler's totient product formula
{c}
{title2=$\varphi(n)=n\prod_{p\mid n}(1-1/p)$}
For a positive <integer> $n$, <Euler's totient product formula> is
$$
\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right),
$$
with the product over distinct <prime divisors>. Among the residues $1,\ldots,n$, a fraction $1/p$ is divisible by $p$. <Inclusion-exclusion> over the prime divisors removes exactly those residues not <coprime> to $n$.
For $n=12$, the formula gives $12(1-1/2)(1-1/3)=4$, corresponding to $1,5,7,11$. It gives $\varphi(p^a)=p^{a-1}(p-1)$ and shows that the <Euler totient function> is multiplicative on <coprime integers>. For $n=1$, the empty product gives $\varphi(1)=1$.
Back to article page