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
    How did you define $\phi$?2011-04-07
  • 0
    It is just the standard definition I believe. $\phi(m) = m \cdot \prod(1-p^-1)$ where p are the distinct primes of m.2011-04-07
  • 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.2011-04-07
  • 0
    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)?2011-04-07
  • 0
    Exactly, it was a mistake perhaps on my part to use ps as that causes some misunderstanding.2011-04-07
  • 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)2011-04-07
  • 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)\ $$