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

Solution 1:

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.

Solution 2:

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.