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.

It is true that $\phi(p) = (p-1)$ only if p is a prime. I had also proven (I am not sure if this is a trivial fact or not) that $\phi(pq) = (p-1)(q-1)$ only if p and q are distinct primes.

However, I am having difficulty generalizing the result. It certainly seems true that if $\phi(p_1\cdot p_2\cdots p_n) = (p_1 - 1)(p_2 - 1)\cdots (p_n-1)$ then each $p_i$ are distinct primes.

What I had done in the initial proof for the case n = 2 was to use the the formula $\phi(pq) = \phi(p)\phi(q)\frac{d}{\phi(d)}$ where d = gcd(p,q) and the fact that if $a \mid b$ then $\phi(a) \mid \phi(b)$ to show that $d \mid 1$. The result follows quite easily after showing that p and q are coprime. However, this proof does not seem to be extendable to the general case. I hope that someone can help me with this.

share|improve this question
    
How did you define $\phi$? –  quanta Apr 7 '11 at 10:39
    
It is just the standard definition I believe. $\phi(m) = m \cdot \prod(1-p^-1)$ where p are the distinct primes of m. –  EuYu Apr 7 '11 at 10:43
1  
@Yuqing, that's weird because that definition makes the theorem trivial. I've shown how and an alternative definition which I am used to. –  quanta Apr 7 '11 at 10:49
    
So you want to prove that $\phi(abcd) = (a-1)(b-1)(c-1)(d-1)$ implies a,b,c,d are all primes (for example)? –  quanta Apr 7 '11 at 10:53
6  
Sorry to keep asking.. Is it required that a,b,c,d are coprime? I have found counter-examples if not. (e.g. phi(4*2*9)=3*1*8) –  quanta Apr 7 '11 at 10:56
show 2 more comments

2 Answers

up vote 9 down vote accepted

The general result sought is wrong. For example $$\phi(4 \times 4 \times 4 \times 9 \times 9)=\phi(64)\phi(81)=(32)(54)$$. Note that $$(4-1)(4-1)(4-1)(9-1)(9-1)=(27)(64)=(32)(54)$$

So in general $\phi(a_1a_2\cdots a_n)=(a_1-1)(a_2-1)\cdots(a_n-1)$ does not imply that the $a_i$ are distinct primes.

I expect that a little playing would give a counterexample with smaller $n$ than the 5 we have above.

share|improve this answer
add comment

The above-stated conjecture has infinitely many counterexamples. Namely

$$\rm\phi(p_1\cdot p_2\cdots p_n)\ =\ (p_1 - 1)\ (p_2 - 1)\cdots (p_n-1)\ \ \Rightarrow\ \ p_i\ distinct\ primes$$

is false for all primes $\rm\:p > 3\:$ in the following examples

$$\rm\ \phi(3\cdot 3\cdot 4\cdot p)\ =\ 2\cdot 2\cdot 3\cdot (p-1)\ $$

$$\rm\ \phi(2\cdot 4\cdot 9\cdot p)\ =\ 1\cdot 3\cdot 8\cdot (p-1)\ $$

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.