Is there a methodical way to compute Euler's Phi function Is there an algorithmic or methodical way to "factorise" the numbers in euler's phi function such that it becomes easily computable? For example, $\phi(7000) = \phi(2^3 \cdot 5^3 \cdot 7)$ I'm finding it difficult to find this "factorised" version of 7000 in terms that are easily computable in the phi function. Also, since computing $\phi$ of a prime number is easy, I thought one method would be to factorise 7000 down to multiples of ONLY prime numbers, ie: $7000 = 7 \times 5 \times 5 \times 5 \times 2 \times 2 \times 2 $ $\phi(7000) = \phi(7) \times \phi(5) \times \phi(5) \times \phi(5) \times \phi(2) \times \phi(2) \times \phi(2)$ $\phi(7000) = 6 \times 4 \times 4 \times 4 \times 1 \times 1 \times 1 $ (Since the $\phi$ of a prime number is just that number $- 1$) But the answer is not correct. I get $384$. Supposed to be $2400$. Why does this not work?

The problem is that $\phi(a \cdot b) = \phi(a) \cdot \phi(b)$ works if $a$ and $b$ are relatively prime, but it doesn't work in general.

Thus, it is true that $\phi(7000) = \phi(2^3) \cdot \phi(5^3) \cdot \phi(7)$. However, we cannot break $\phi(2^3)$ down to $\phi(2)^3$. (You can check that $\phi(2^3) = 4$ and $\phi(2)^3 = 1$.)

Thus, the problem reduces to figuring out how to evaluate $\phi(p^k)$ where $p$ is a prime. There is a nice formula for this, which isn't very tricky to find. Try some examples. Do you see a pattern?