Euler's totient function for large numbers

Question

I know that $\phi(n)$, Euler's totient function, defines the number of all integers less than or equal to $n$ that are relatively prime to $n$.

I know that there is a trick to finding this with the larger non-prime numbers, but now I cannot find it anywhere. Could someone please explain how to find $\phi(n)$ for some large, non prime $n$.

For example: $\phi(352)$?

Answer 1

There are two basic facts that you should know that will help you remember the formula.

First, if $n$ is a power of a prime, say $n=p^k$, then $\phi(p^k)=p^k-p^{k-1}$. This is because the only numbers less than or equal to $p^k$ that are not relatively prime to $p$ are $p,p^2,\ldots,p^{k-1}$. Note that $\phi(n)=\phi(p^k)=p^k(1-\frac{1}{p})$.

The second is that if $m$ and $n$ are relatively prime, then $\phi(mn)=\phi(m)\phi(n)$. This can be shown with not too much trouble using the chinese remainder theorem.

Putting all this together, if you can find the prime factorization $n=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$, where $p_1,\ldots,p_m$ are distinct primes, then $$\phi(n)=p_1^{k_1}(1-\frac{1}{p_1})p_2^{k_2}(1-\frac{1}{p_2})\cdots p_m^{k_m}(1-\frac{1}{p_m})\\ =n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_m}).$$

For example, if $n=140$ and you find that $n=(2^2)(5)(7)$, then $\phi(140)=140(1-\frac{1}{2})(1-\frac{1}{5})(1-\frac{1}{7})$.

Answer 2

The main tool is multiplicativity: $\phi(ab)=\phi(a)\phi(b)$ if $\gcd(a,b)=1$.

Also, if $p$ is a prime, then $\phi(p^k)=p^{k-1}(p-1)$.

In particular, if $n=2^k m$, with $m$ odd, then $\phi(n)=2^{k-1} \phi(m)$.

For $n=352=2^5\cdot 11$, we get $\phi(352)=2^4 \phi(11)=2^4 \cdot 10 = 160$.