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

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?

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

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.

• 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... – user216004 Feb 17 '15 at 0:57
• 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$. – André Nicolas Feb 17 '15 at 7:19
• 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. – bof Feb 17 '15 at 9:24

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

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