Divisibility and GCD proof

Question

I'm having trouble with this simple proof. Any help would be appreciated. I don't really know where to start to try to conquer this problem.

Suppose $a|m$, $b|m$ and $\gcd(a,b) = 1$. Prove, without appealing to the fundamental theorem of arithmetic, that $ab|m$.

I know that $\gcd(a,b)=1$ means they are relatively prime. I also know that $a|m$ means $a=ms$ and that $b|m$ means $b=mt$ and lastly that $\gcd(a,b)=1$ means $1=as+bt$. I just have no idea what to do next. Any help would be appreciated. Thanks!

Answer 1

The observation you make in your question isn't quite right: Given that $a\mid m$ and $b\mid m$, there exist integers $s$ and $t$ such that $$as=m\qquad\text{ and }\qquad bt=m.$$ Also, when you say that $\gcd(a,b)=1$ implies $1=as+bt$ you should be careful using the same letters $s$ and $t$ as before; they need not be the same numbers! In stead you can say there exist integers $x$ and $y$ such that $$ax+by=1.$$ Perhaps you can already take it from here? If not, here's a hint:

If $ax+by=1$ then $st=axst+byst=mxt+mys=m(xt+ys)$, so $m\mid st$.

Answer 2

Start from Bézout's identity: since $a,b$ are coprime, there exist integers $u,v\in \mathbf Z$ such that $ua+vb=1$, whence $$m=uam+vbm.$$ If $a\mid m$ and $b\mid m$, there exist integers $m_1,m_2$ such that $\;m=am_1,\enspace m=bm_2$. Combining with the above equation, we have: $$m=uabm_2+vbam_1=ab(um_2+vm_1).$$