Results 1 to 3 of 3

Math Help - Help with a divisibility proof

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    Canada
    Posts
    7

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78

    Re: Help with a divisibility proof

    Quote Originally Posted by notinsovietrussia View Post
    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
    Last edited by TheEmptySet; September 27th 2012 at 03:14 PM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2012
    From
    Canada
    Posts
    7

    Re: Help with a divisibility proof

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

    Quote Originally Posted by TheEmptySet View Post
    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility Proof
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: February 19th 2010, 01:01 AM
  2. Divisibility Proof
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: March 16th 2009, 06:11 PM
  3. divisibility proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 20th 2009, 10:27 PM
  4. Proof of divisibility
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 2nd 2008, 10:34 AM
  5. Divisibility proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 10th 2008, 07:07 AM

Search Tags


/mathhelpforum @mathhelpforum