# Thread: Help with a divisibility proof

1. ## Help with a divisibility proof

Prove that if a|c, b|c, (a,b)=d then ab|cd.

Having a little trouble with these kinds of proofs. Help would be greatly appreciated until I wrap my head around them. I figured if you can prove that ab|c that would be all that's required because d has to be an integer. Having said that, I'm having issues proving ab|c, even though it makes sense to me intuitively. 2|16, 4|16 therefore 8|16... but how do you prove that?

2. ## Re: Help with a divisibility proof

Originally Posted by notinsovietrussia
Prove that if a|c, b|c, (a,b)=d then ab|cd.

Having a little trouble with these kinds of proofs. Help would be greatly appreciated until I wrap my head around them. I figured if you can prove that ab|c that would be all that's required because d has to be an integer. Having said that, I'm having issues proving ab|c, even though it makes sense to me intuitively. 2|16, 4|16 therefore 8|16... but how do you prove that?
These are all about writing down what you know and what you want.

$\displaystyle a|c \implies c =q_1a$

$\displaystyle b|c \implies c=q_2b$

and

$\displaystyle (a,b)=d \implies ax+by=d$

Now we want to show that

$\displaystyle ab|cd \implies cd = q_3(ab)$

If we multiply the LCM by c we get

$\displaystyle cd=cax+cby$

Since we need each factor on the left hand side to have ab in it we can replace c with the first two equations to get

$\displaystyle cd=(q_2b)ax+(q_1a)by=(q_2x+q_1y)ab \implies ab|cd$

3. ## Re: Help with a divisibility proof

Thanks for the help! Your proof makes sense, except for this little bit:

Originally Posted by TheEmptySet
If we multiply the LCM by 3 we get
You say multiply by three but that doesn't appear in the proof.

EDIT: Wow, I realised what you meant as soon as I posted the reply. LCM being c, and 3 being the third equation. Perfect. Thanks again!