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