Calculating Euler's totient function values.

Solution 1:

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.

Solution 2:

It seems to me that to understand how to calculate values of Euler's totient function one first has to understand what the function does. Without that understanding, all the formulas in the world are useless.

A few smaller but well-chosen examples might be a big help as well. First let's think about $\phi(3) = 2$ and the sequence of thirds from $\frac{1}{3}$ to $1$: $$\frac{1}{3}, \frac{2}{3}, \frac{3}{3}.$$ These can be rewritten as $$\frac{1}{3}, \frac{2}{3}, 1.$$ Two of these fractions retained $3$ as denominator.

Now consider $\phi(6) = 2$. Consider also the sequence of sixths from $\frac{1}{6}$ to $1$: $$\frac{1}{6}, \frac{2}{6}, \frac{3}{6}, \frac{4}{6}, \frac{5}{6}, \frac{6}{6}.$$ These can be rewritten thus: $$\frac{1}{6}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{5}{6}, 1.$$ Only two of them retained $6$ as denominator.

Next consider $\phi(12) = 4$. Consider also the sequence of twelfths from $\frac{1}{12}$ to $1$: $$\frac{1}{12}, \frac{2}{12}, \frac{3}{12}, \frac{4}{12}, \frac{5}{12}, \frac{6}{12}, \frac{7}{12}, \frac{8}{12}, \frac{9}{12}, \frac{10}{12}, \frac{11}{12}, \frac{12}{12}.$$ These can be rewritten thus: $$\frac{1}{12}, \frac{1}{6}, \frac{1}{4}, \frac{1}{3}, \frac{5}{12}, \frac{1}{2}, \frac{7}{12}, \frac{2}{3}, \frac{3}{4}, \frac{5}{6}, \frac{11}{12}, 1.$$ Only four of them retained $12$ as denominator.

But more importantly than that, notice where the $12$s are placed: the corresponding numerators are $1, 5, 7, 11$, and $7 = 1 + 6$ and $11 = 5 + 6$. It's kind of as if we duplicated the structure of the sixths and carried it over to the twelfths. Do you understand in what ways it's different to go from sixths to twelfths than to go from thirds to sixths?

That difference need not concern us in your example of $2010$, since that number is squarefree:

• $\phi(67) = 66$. In writing sixty-sevenths from $\frac{1}{67}$ to $1$, you won't be able to change the numerator for any of them except for $\frac{67}{67}$.
• $\phi(5) = 4$ and $\phi(335) = 264$. Of the integers between $1$ and $335$, sixty-seven of them are divisible by $5$ and five are divisible by $67$, but only one of them is divisible by both $5$ and $67$ (and that's $335$ itself). Notice: $335 - 5 - 67 = 263$ (this overcounts $335$).
• $\phi(3) = 2$ and $\phi(1005) = 528$. I leave this one for you to work out yourself.
• $\phi(2) = 1$ and $\phi(2010) = 528$. Here we have twice as many numbers to deal with, but twice an odd number is an even number which is of course divisible by $2$, so if we actually troubled ourselves with writing fractions from $\frac{1}{2010}$ to $1$, we'd be able to change the denominator on at least half of those, so multiplying by $2$ doesn't really gain us coprimes...

Solution 3:

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.

Solution 4:

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$