7
$\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$
25
$\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
6
$\begingroup$

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.

$\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.