1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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