4
$\begingroup$

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?

  • 0
    Ahh, I see - 2, 5 and 7 are prime factors of 7000. The trick is that they are the unique prime factors - so we don't use three 2s and three 5s, we only take one of them2011-11-07

2 Answers 2

7

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?

  • 1
    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 read2011-11-06
3

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.