# If $\gcd(a,b)=1$ and $a$ and $b$ divide $c$, then so does $ab$

Using divisibility theorems, prove that if $\gcd(a,b)=1$ and $a|c$ and $b|c$, then $ab|c$.

This is pretty clear by UPF, but I'm having some trouble proving it using divisibility theorems. I was looking at this Math.SE problem, and if this could be proven, then the solution would follow immediately.

If $\gcd(a,b)=1$ then there exist integers $s$ and $t$ such that $a s +b t =1$. Hence $c a s +c b t =c$. Now since $a \vert c$ and $b \vert c$ there exist integers $m$ and $n$ such that $c = m a$ and $c= n b$. Hence $n b a s + m a b t =c$. Since $a b$ divides the entire left hand side, it must also divide the right hand side.

• Easily the better answer here. – Noldorin May 25 '14 at 17:58
• @Noldorin fyi: other answer is not only simpler, but it works more generally. – Bill Dubuque Nov 17 '16 at 15:38
• More general maybe, but this one is much clearer! – Noldorin Nov 17 '16 at 16:32

Yes, you can use Euclid's Lemma: $\, (a,b)=1,\,\ a\mid b(c/b)\,\Rightarrow\, a\mid c/b\,\Rightarrow\, ab\mid c. \ \$ QED

If fact, they're equivalent, i.e. conversely, this lcm property $\color{#c00}{\rm L\ implies}$ Euclid's Lemma

$$(a,b)=1,\ a\mid bc\ \Rightarrow\ a,b\mid bc\,\color{#c00}{\stackrel{\rm L}\Rightarrow}\, ab\mid bc\,\Rightarrow\,a\mid c$$

There are many useful properties known equivalent to Euclid's Lemma over arbitrary domains, e.g. see the end of this post for a handful, and some closely related gcd properties.