8
$\begingroup$

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.

$\endgroup$
30
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.