# Help with a divisibility proof

• Sep 27th 2012, 01:52 PM
notinsovietrussia
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?
• Sep 27th 2012, 02:34 PM
TheEmptySet
Re: Help with a divisibility proof
Quote:

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.

$a|c \implies c =q_1a$

$b|c \implies c=q_2b$

and

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

Now we want to show that

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

If we multiply the LCM by c we get

$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

$cd=(q_2b)ax+(q_1a)by=(q_2x+q_1y)ab \implies ab|cd$
• Sep 27th 2012, 02:51 PM
notinsovietrussia
Re: Help with a divisibility proof
Thanks for the help! Your proof makes sense, except for this little bit:

Quote:

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!