Thread: 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?

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.





and



Now we want to show that



If we multiply the LCM by c we get



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

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!