# 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

Applying $$\rm\color{#c00}{Euclid's}$$ Lemma: $$\,\ b\mid an\overset{\color{#c00}{(a,\,b)\ {\bf =}\ 1}}\Longrightarrow\,b\mid n\,\overset{\large \times\ a\ }\Longrightarrow\,ab\mid an\quad \small{\bf QED}$$

Remark  They're equivalent, i.e. conversely, this lcm property $$\color{#0a0}{\rm L\ implies}$$ Euclid's Lemma

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

Unlike proofs by Bezout, this proof by Euclid's Lemma works in UFDs which have no Bezout identity, e.g. polynomial rings like $$\,\Bbb Z[x]\,$$ and $$\,\Bbb Q[x,y].\,$$ The Bezout-based proofs essentially substitute inline into the above proof a Bezout-based proof of Euclid's Lemma, yielding essentially the following proof $$\ a,b\mid c\,\Rightarrow\,ab\mid ac,bc\,\Rightarrow\,ab\mid (ac,bc) = (a,b)c = c\$$ in gcd (or ideal) language (compare various forms of Euclid's Lemma).

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.