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?

$\endgroup$
  • $\begingroup$ You have to prove it in general. This only answers it for the specific case. $\endgroup$ – Euler....IS_ALIVE Oct 8 '12 at 20:47
  • $\begingroup$ How would I go about doing that? $\endgroup$ – Chloe Williams Oct 8 '12 at 20:49
  • $\begingroup$ 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? $\endgroup$ – Graphth Oct 8 '12 at 20:57
  • $\begingroup$ 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. :) $\endgroup$ – Chloe Williams Oct 8 '12 at 21:00
  • $\begingroup$ More is true: $\phi(mn) = \phi(m) \phi(n) \frac{d}{\phi(d)}$. $\endgroup$ – lhf Oct 8 '12 at 22:54
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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