Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
5  
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
4  
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
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-\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
show 1 more comment

2 Answers 2

up vote 7 down vote accepted

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?

share|improve this answer
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 read –  Arvin Nov 6 '11 at 14:32
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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