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.

  • $\begingroup$ How did you define $\phi$? $\endgroup$ – quanta Apr 7 '11 at 10:39
  • $\begingroup$ It is just the standard definition I believe. $\phi(m) = m \cdot \prod(1-p^-1)$ where p are the distinct primes of m. $\endgroup$ – EuYu Apr 7 '11 at 10:43
  • 1
    $\begingroup$ @Yuqing, that's weird because that definition makes the theorem trivial. I've shown how and an alternative definition which I am used to. $\endgroup$ – quanta Apr 7 '11 at 10:49
  • $\begingroup$ 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)? $\endgroup$ – quanta Apr 7 '11 at 10:53
  • 6
    $\begingroup$ 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) $\endgroup$ – quanta Apr 7 '11 at 10:56

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.


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)\ $$


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.