# 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?

-
Function $\phi$ is multiplicative but not completely multiplicative. I.e. $\phi(7.5^3.2^3)=\phi(7)\phi(5^3)\phi(2^3)$ is true, but $\phi(2^2)\ne\phi(2).\phi(2)$. – Martin Sleziak Nov 6 '11 at 14:19
Does this formula help? – J. M. Nov 6 '11 at 14:23
Thanks J.M. The formula is a bit confusing to me as I'm not used to that product notation. Is there an example of its usage? – Arvin Nov 6 '11 at 14:30
Sure. Let's use your example, $\phi(7000)$. We know that $7000=2^3 \times 5^3 \times 7$. To use that formula, you compute $7000\times\left(1-\frac12\right)\times\left(1-\frac15\right)\times\left(1-\frac‌​17\right)$. That should yield the answer you're expecting. – J. M. Nov 6 '11 at 14:36
That does indeed equal 2400, the correct answer. Now my only problem is is there a nice way to find those numbers - 2, 5 and 7 easily without trial and error? – Arvin Nov 6 '11 at 14:48

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?

-
Ahh, so it only works if it's relatively prime. I see now that $\phi(2^3)$ is not the same as $\phi(2)^3$. I've seen the formula, but to be honest I'm finding it very confusing to read – Arvin Nov 6 '11 at 14:32

Are you aware if that $\phi(m)=m \prod_{i=1}^k(1-\frac{1}{p_i})$ where $p_i$ is a prime in the canonical representation of m?

Edit:I did not see J.M.'s comment.

-