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?

  • 5
    $\begingroup$ 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)$. $\endgroup$ – Martin Sleziak Nov 6 '11 at 14:19
  • 4
    $\begingroup$ Does this formula help? $\endgroup$ – J. M. is a poor mathematician Nov 6 '11 at 14:23
  • $\begingroup$ 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? $\endgroup$ – Arvin Nov 6 '11 at 14:30
  • 4
    $\begingroup$ 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-\frac17\right)$. That should yield the answer you're expecting. $\endgroup$ – J. M. is a poor mathematician Nov 6 '11 at 14:36
  • $\begingroup$ 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? $\endgroup$ – 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?

  • 1
    $\begingroup$ 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 $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.