3
$\begingroup$

Let $m_1,m_2\ge1$ be such that $\gcd(m_1,m_2) \ne 1$. Argue that $\phi(m_1*m_2)$ is strictly less that $\phi(m_1)*\phi(m_2)$.

What I have so far:

By example (which I'm not sure if that's how he wants the answer... ):

$$\phi(5*20)=\phi(100)=(2^2-2)*(5^2-5)=40$$

$$\phi(5)=4$$

$$\phi(20)=(2^2-2)*(4)=8$$

$$8*4=32$$

Where $32 \lt 40$. Is this a sufficient way to answer this question? Could someone maybe give me a hint as to how to how I could answer the question in a way other than by example?

  • 0
    You have to prove it in general. This only answers it for the specific case.2012-10-08
  • 0
    How would I go about doing that?2012-10-08
  • 0
    Speaking for myself, if I gave a student an extra credit problem, I would care much more than if it were just homework that the student did it on their own. So, do you have permission from your instructor to ask about this problem on here?2012-10-08
  • 0
    I'm not even positive it is extra credit, he just said to do it if we can. Last time he did this he gave us extra credit, but idk if he will again. I tried to do as much of it as I could on my own also. :)2012-10-08
  • 0
    More is true: $\phi(mn) = \phi(m) \phi(n) \frac{d}{\phi(d)}$.2012-10-08
  • 0
    An example is insufficient, generally speaking. Maybe $m_1 = 5$ and $m_2 = 20$ works and maybe other values work and maybe other values don't work. Maybe the pair you chose is the only pair that works! What you need is a logical proof that shows you that any pair of values satisfying the specified conditions will also satisfy the inequality.2015-02-26

2 Answers 2

2

I think you've gotten a couple of things switched around, or I might be the dyslexic one, I'm not sure. Your example suggests that $\phi(m_1 m_2) > \phi(m_1) \phi(m_2)$. But an example only proves one case out of infinitely many.

You should already know that if $\gcd(m_1, m_2) = 1$, then $\phi(m_1 m_2) = \phi(m_1) \phi(m_2)$. You should also know this formula: $\phi(p^x) = (p - 1)p^{x - 1}$, where $p$ is a prime number and $x$ is a positive integer.

Let's say $m_1 = pq$ (where $q$ is another prime) and $m_2 = pr$ (where $r$ is yet another prime, distinct from $p$ and $q$). Then $$\phi(m_1 m_2) = \phi(p^2 qr) = (p^2 - p)(q - 1)(r - 1),$$ $$\phi(m_1) = (p - 1)(q - 1), \phi(m_2) = (p - 1)(r - 1),$$ $$\phi(m_1) \phi(m_2) = (p - 1)(q - 1)(p - 1)(r - 1) = (p^2 - 2p + 1)(q - 1)(r - 1).$$

In both products we have $(q - 1)(r - 1)$. If we divide that out, we're left with $$(p^2 - p) > (p^2 - 2p + 1).$$

This still does not prove every possible case specified by your question, but at least it does prove more than just one specific case.

1

Try more examples and see if you can figure it out. Start by trying to prove it for $\phi(p \cdot p)$, where $p$ is prime. Then, make things a bit more complicated and try again. Eventually, you want to be able to prove it for two general numbers with prime factorization $p_1^{r_1} \cdots p_m^{r_m}$ and $q_1^{s_1} \cdots q_n^{s_n}$. Since the gcd is not 1, you know that they share at least one prime in common. Just let $p_1 = q_1$.