Calculating Euler's totient function values. I never understood how to calculate values of Euler's totient function. Can anyone help?
For example, how do I calculate $\phi(2010)$?
I understand there is a product formula, but it is very different from regular products, so how should I do this? Thanks.
 A: From Wikipedia: if $\displaystyle n=p_1^{k_1}\cdots p_r^{k_r}$, then
$\varphi(n)=\varphi(p_1^{k_1})\varphi(p_2^{k_2})\cdots\varphi(p_r^{k_r})=p_1^{k_1}\left(1- \frac{1}{p_1}\right)p_2^{k_2}\left(1-\frac{1}{p_2}\right)\cdots p_r^{k_r}\left(1-\frac{1}{p_r} \right)=$
$=n\cdot\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_r}\right)$
So you'll have to find all different prime factors $p_1,\cdots,p_r$ of n.
A: The most important fact to remember is that Euler's totient function is multiplicative, conditioned on coprimality. If $\gcd(m, n) = 1$, then $\phi(mn) = \phi(m) \phi(n)$.
For example, $\phi(2010) = \phi(2) \phi(3) \phi(5) \phi(67) = 1 \times 2 \times 4 \times 66 = 528$. This one's easy because the number is squarefree. You have to be a little more careful when the number is not squarefree.
A: If you take into account that the totient function is multiplicative $\phi(ab)=\phi(a)\phi(b)$ for $a$, $b$ coprime, and that $\phi(p^n)=p^n-p^{n-1}$ for any prime $p$ a simple computation yields $$\phi(n)=n\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)$$ where $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ is the prime decomposition of $n$
