Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
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
1  
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
2  
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
1  
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
1  
@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 2

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$.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.