2
$\begingroup$

I have this math question that I am kind of stuck on.

Show that if $\gcd(m_1,m_2) = 1$ and $n$ is an integer with $m_1\mid n$ and $m_2\mid n$, then $m_1m_2\mid n$, using unique factorization.

I'm not 100% how to start this. I already proved this using Bezout's identity. Thanks

$\endgroup$
  • $\begingroup$ What can you say about the unique factorizations of $m_1$ and $m_2$, under these conditions What about $n$? $\endgroup$ – Thomas Andrews Nov 22 '15 at 22:59
  • $\begingroup$ Would I say that $n$ can be written as a product of primes and that $m_1$ and $m_2$ divides at least one of them? $\endgroup$ – KFC Nov 22 '15 at 23:01
  • $\begingroup$ Show ... using unique factorization + I already proved this using Bezout's identity. To me the latter would have been a perfectly good proof, since unique factorization implies Bezout's identity (a.k.a. a PID is a Bezout domain). But then I am not your teacher, of course. $\endgroup$ – dxiv Nov 23 '15 at 0:45
2
$\begingroup$

Write $n=p_1^{a_1}p_2^{a_2}\dots p_k^{a^k}$ as product of prime powers ($p_1,\dots,p_k$ pairwise distinct and $a_i>0$).

Then you can write $$ m_1=p_1^{b_1}p_2^{b_2}\dots p_k^{b_k},\qquad m_2=p_1^{c_1}p_2^{c_2}\dots p_k^{c_k} $$ where $0\le b_i\le a_i$ and $0\le c_i\le a_i$ ($i=1,2,\dots,k$). Then $$ m_1m_2=p_1^{b_1+c_1}p_2^{b_2+c_2}\dots p_k^{b^k+c_k} $$ and $m_1m_2\nmid n$ implies $b_i+c_i>a_i$, for some $i$. In particular $b_i>0$ and $c_i>0$, so $p_i$ divides both $m_1$ and $m_2$.

$\endgroup$
0
$\begingroup$

There is a simpler proof without the sophisticated unique factorisation tool, based on Gauß's lemma:

If a number $n$ divides a product $ab$, and $n$ and $a$ are coprime, then $n$ divides $b$.

Indeed, if $m_1$ divides $n$, we can write $n=m_1 n'$. Now $m_2$ divides $n=m_1n'$, and $m_2$ and $m_1$ are coprime. Thus, by Gauß's lemma, $m_2$ divides $n'$, i.e. $n'=m_2n''$ for some $n''$, and we have $$n=(m_1m_2)n''.$$

$\endgroup$
0
$\begingroup$

You know that $m1$ and $m2$ are relatively prime, since their $gcd$ is 1. In other words, when written as a product of primes, they do not share any prime divisors.

Since $m1$ divides $n$, and $m2$ divides $n$, then you also know that $n$ written as a product of primes contains all those prime factors of $m1$, as well as those of $m2$. You can then conclude that $m1m2$ divides $n$ by using your definitions of what it means for an integer to divide another.

$\endgroup$
  • 1
    $\begingroup$ The g.c.d. of $m_1$ and $m_2$ is $\color{red}1$. $\endgroup$ – Bernard Nov 22 '15 at 23:48

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.