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?

  • 5
    Function $\phi$ is [multiplicative](http://en.wikipedia.org/wiki/Multiplicative_function) 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)$.2011-11-06
  • 4
    Does [this formula](http://functions.wolfram.com/NumberTheoryFunctions/EulerPhi/08/0001/) help?2011-11-06
  • 0
    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?2011-11-06
  • 4
    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.2011-11-06
  • 0
    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?2011-11-06
  • 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.