# Unique Factorization proof with GCD

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

• What can you say about the unique factorizations of $m_1$ and $m_2$, under these conditions What about $n$? – Thomas Andrews Nov 22 '15 at 22:59
• 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? – KFC Nov 22 '15 at 23:01
• 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. – dxiv Nov 23 '15 at 0:45

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

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

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.

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