# Euler's phi function and distinct primes

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.

• 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
• @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
• 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

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