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