2
$\begingroup$

Prove for integers $a$, $b$, and $c$, if $\gcd(a, b) = 1$, $a|c$, and $b|c$ then $ab|c$.

Part b of this question is: "Is the converse true? Prove or disprove accordingly?"

Hey, so I've been drawing a blank for at least an hour now. I played around with the definition of divisibility and the gcd of one but couldn't get anywhere. Could someone help out?

$\endgroup$
1
$\begingroup$

Theorem. For $a,b,c\in\mathbb Z$, if $a\mid bc$ and $\gcd(a,b)=1$, then $a\mid c$.

Proof. From Bézout's identity we know that there exist $u,v\in\mathbb Z$ such that $au+bv=1$. This gives us $$c=(au+bv)c = a\cdot uc+bc\cdot v.$$ The number $a$ divides both summands, hence $a\mid c$.

The above result is called Euclid's lemma.

Corollary. For $a,b,c\in\mathbb Z$, if $a\mid bc$ and $\gcd(a,b)=1$, then $a\mid c$.

We have $c=ka$ for some $k\in\mathbb Z$. Since $b\mid ka$ and $\gcd(a,b)=1$, we get from Euclid's lemma that $b\mid k$. This implies $ab\mid ka=c$.

$\endgroup$
0
$\begingroup$

Extended Euclidean algorithm allows one to write the gcd of $a$ and $b$ in the form $xa+yb$, and many results can be proved from there.

$\endgroup$
  • $\begingroup$ Yeah, I used the EEA, which tells me xa + yb = 1, and i also have c = ka, c = lb, but im failing to make the connection here to lead to the conclusion... $\endgroup$ – user216004 Feb 17 '15 at 0:57
  • $\begingroup$ We have $ax+by=1$ so $axc+byc=c$. We have $b$ divides $c$ so $ab$ divides $axc$. Also, $a$ divides $c$ so $ab$ divides $byc$. Thus $ab$ divides the sum $axc+byc$, and therefore $ab$ divides $c$. $\endgroup$ – André Nicolas Feb 17 '15 at 7:19
  • $\begingroup$ If $xa+yb=1$ then $$\frac c{ab}=\frac{c(xa+yb)}{ab}=x\cdot\frac cb+y\cdot\frac ca$$is an integer, given that $x,y,\frac cb,\frac ca$ are integers. $\endgroup$ – bof Feb 17 '15 at 9:24
0
$\begingroup$

converse is obvious since $a|ab$ and $b|ab$ then given $ab|c $ we conclude that $a|c$ and $b|c$

$\endgroup$
  • $\begingroup$ yes, but how does this prove that gcd(a,b) = 1 ? $\endgroup$ – user216004 Feb 17 '15 at 0:59
  • $\begingroup$ if you consider that as converse then that is not true.let $a=b=2$ and $c=4$ $\endgroup$ – BigM Feb 17 '15 at 1:14

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.