1
$\begingroup$

Show that if $(a,b)=1$, $a\mid c$ and $b\mid c$, then $a\cdot b\mid c$.

Tried

$c=a\cdot k$ and $c=b\cdot j$ with $k,j\in\mathbb{N}$ then $a\cdot b\mid c^2=c\cdot c$.

$\endgroup$
6
$\begingroup$

By Bezout theorem $(a,b)=1\iff \exists u,z\in\mathbb Z:\ ua+bv=1(*)$ and since $a|c$ and $b|c$ so $c=ka$ and $c=k'b$ so multiplying $(*)$ by $c$ we find $$uac+bvc=uk'ab+vkab=ab(uk'+vk)=c\Rightarrow ab|c$$

$\endgroup$
5
  • $\begingroup$ This was very good. I did very well. Thank you! $\endgroup$ – marcelolpjunior Dec 9 '13 at 21:04
  • $\begingroup$ You're welcome. $\endgroup$ – user63181 Dec 9 '13 at 21:05
  • $\begingroup$ Ben Rodhane Using this, or similar concepts, as I could show that, if $(a,b)=1$ then $(ac,b)=(c,b)$. $\endgroup$ – marcelolpjunior Dec 9 '13 at 21:08
  • $\begingroup$ Morning Sami. Thanks for noting that typo. :) $\endgroup$ – Mikasa Dec 10 '13 at 7:15
  • $\begingroup$ You know your theorems! Just the right tool for the job! $\endgroup$ – amWhy Dec 11 '13 at 13:35
2
$\begingroup$

$\rm\ a\mid c=b(c/b)\overset{(a,b)=1}{\color{#c00}\Rightarrow} a\mid c/b \,\Rightarrow\, ab\mid c,\ $ the $\rm\color{#c00}{red}$ inference by Euclid's Lemma. $\ \ $ QED

$\endgroup$
1
$\begingroup$

Get the prime factors of c. Then some of them form a, some of them are the factors of b, and because $(a,b)=1$ no factors of a and b occur twice. Then the remaining factors of c are what you have to multiply to $a\cdot b$ to get c, so $a\cdot b|c$.

$\endgroup$
0
$\begingroup$

$c=a.k=b.j$

But $(a,b)=1$, and $a$ divides $b.j$, so $a$ divides $j$. Hence $a.b$ divides $c$.

$\endgroup$
0
$\begingroup$

You can generalize this theorem further:

If $a \mid c$ and $b \mid c$ then $\operatorname{lcm}(a,b) \mid c$ where $\operatorname{lcm}(a,b)$ is the least common multiple of $a$ and $b$. This is obvious by definition of lcm but you also need to prove that $\displaystyle \operatorname{lcm}(a,b) = \frac{|a \cdot b|}{\gcd(a,b)}$.

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