# How to prove $\phi(mn) > \phi(m)\phi(n)$ if $(m,n) \ne 1$

I need to prove that

$$\phi(mn) > \phi(m)\phi(n)$$

if $m$ and $n$ have a common factor greater than 1.

I have read up on the case where $m$ and $n$ are relatively prime, then $\phi(mn)=\phi(m)\phi(n)$.

-
Write both $m,n$ as product of power of primes, and observe that $$\varphi(p^k) = p^{k-1}(p-1) > \varphi(p)^k = (p-1)^{k-1}(p-1)$$ – user2468 Mar 13 '12 at 1:46
J.D., this is pretty much the answer OP is looking for. You should post this. – Patrick Da Silva Mar 13 '12 at 1:48
It'd be nice to show explicitly that the natural map $U_{mn}\to U_m \times U_n$ is surjective but not injective, if it is true. – lhf Mar 13 '12 at 1:50
Ah, it seems that the natural map $U_{mn}\to U_m \times U_n$ has a kernel of size $d$ and an image of index $\phi(d)$ and so my idea above does not seem to work... – lhf Mar 13 '12 at 2:20
@lhf: Your idea works well enough...it leads to Dane's answer. (By the way, I had the same thought of expressing things in terms of this natural homomorphism. I think it would be a positive contribution if you left this as answer.) – Pete L. Clark Mar 13 '12 at 2:40

## 2 Answers

Hint: Write the prime factorization of both $m,n$ and observe that $$\varphi(p^k) = p^{k-1}(p-1) > \varphi(p)^k = (p-1)^{k-1}(p-1).$$

I'm sorry I'm too lazy this moment to work a whole proof. But here is a simple case. If $$m = pq, n = ph$$ for primes $p,q,h$. Then $$\varphi(m)\varphi(n) = \varphi(p)^2 \varphi(q)\varphi(h)$$ and $$\varphi(mn) = \varphi(p^2)\varphi(q)\varphi(h)$$ Result follows since $\varphi(p^2) > \varphi(p)^2$ as above.

-

According this recently asked question, $$\phi(mn) = \phi(m) \phi(n) \frac{d}{\phi(d)} ,$$ where $d = \gcd(m,n)$. Your question follows from the fact that $\varphi(d) < d$ whenever $d>1$.

-