5
$\begingroup$

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.

  • 0
    Well, the point is we don't know the nature of a,b,c,d or their relationships to each other. It seems that the result is not true in general then due to that counterexample.2011-04-07

2 Answers 2

11

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.

2

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