Euler's totient function for large numbers

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)$?

• Are you assuming that $n$ is large, but not so large that you can factor it? – Casteels Dec 19 '14 at 10:06
• Yes, something between 100 and 300... – Lydia Dec 19 '14 at 10:13
• In pari gp: ${\rm eulerphi}(352)=160$. – Dietrich Burde Dec 19 '14 at 10:46

2 Answers

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})$.

• the issue is I need to find all of these without a calculator and Im not super confident on my computational skills in a timed setting... – Lydia Dec 19 '14 at 10:54
• @Lydia I'm not sure there's an easy way around not finding divisors of $n$ of some sort, it's just something you're expected to have mastered by now. So maybe just practice your long division to get back in the groove. Alternatively, you could ask another question here asking for tricks/tips on how to factorize small-ish numbers by hand. – Casteels Dec 19 '14 at 11:15

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$.