Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: A proof involving Greatest common divisors

  1. Nov 8, 2008 #1
    1. The problem statement, all variables and given/known data

    If b>0 and a=bq + r, prove that (a,b) = (b,r)

    I made an attempt... it didnt really go anywhere.

    I think I can say that (a,b) = am + bn and (b,r) = bp + rq.
    a = bq + r
    b = rp + s
    You can see that I have absolutely no idea how to solve this.

    Any help would be greatly appreciated. Thank you in advance.
  2. jcsd
  3. Nov 9, 2008 #2
    It follows from the Euclidean Algorithm; Consider if c divides a and b, then let a=cs and b=ct with s,t being integers. Then

    [tex]r=a-bq=cs-(ct)q=c(s-tq) \Rightarrow c | r [/tex]

    And therefore c also divides b and r. Can you think of how the rest should go?
  4. Nov 9, 2008 #3
    well... I didn't accomplish too much. What exactly is my final goal supposed to be? What should I be showing next?

    I tried to say
    r = bq + w
    w = r-bp
    w = r - ctp
    w c(s - tq) - ctq
    w = c(s - t(q - p))

    and then i decided that I wasn't really doing anything correctly and examined the equation
    r - r = bq
    q - c(s - tq) = bq
    a = cs - ctq = bq
    cs - cs - ctq = bq
    bq = bq...
    Clearly this is wrong...

    So what am I trying to accomplish in the end?
  5. Nov 9, 2008 #4
    Now you have c|a and c|b. you get c|r from jeffreydk's hint.
    Then you have c|b and c|r, which implies c|gcd(b,r), which means c is a common divisor of b and r.
    if c=gcd(a,b), you are supposed to show c is actually the GREATEST common divisor of b and r

    here's another way, gcd(a,b)|gcd(b,r) and gcd(b,r)|gcd(a,b) will imply they are equal. I think you have already got gcd(a,b)|gcd(b,r), you can prove gcd(b,r)|gcd(a,b) in a similar way.
  6. Nov 9, 2008 #5
    alright. that makes sense based on the proof of a GCD. Thank you. I probably got it from here.
  7. Nov 9, 2008 #6
    well... I think im dropping this class. its simply not making sense, and this is supposed to be one of the easier problems

    I said
    let r = cp
    b = rq + w
    w = b - rq
    w = ct - cpq
    w = c(t - pq)
    implies c divides w

    but I dont think this implies c divided (a,b)...

    anyone know some good resources where I can get some help?
  8. Nov 9, 2008 #7
    foget about b=rq+w, focus on a=bx+r. Now a=c*something+c*something...can you get it now?

    Also you would notice that,
    1,a=bq+r. if c|a and c|b, you proved that c|r
    now look at this one
    2,b=rp+w. you have c|b and c|r, you proved that c|w
    See? you are doing exactly the same thing two times.
  9. Nov 9, 2008 #8
    Well, I just tried it, wrote everything out and then realized that I made the same error that i did last time.

    I guess I'm not really sure how to set the problems up in the first place. Clearly I don't understand something quite integral to the topic at hand.

    What exactly am I saying when i write a = bx + r and a = bq+ r? Why is r the same for both of them? Why isn't a separate value required?

    im calling it quits on this one... i cant figure it out.
    I just don't understand the concepts at hand. Until I learn them, attempting this is futile.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook