1. Not finding help here? Sign up for a free 30min 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!

Gcd proof

  1. May 25, 2005 #1
    For a, b, c, d positive integers, and d = a + bc, prove that gcd(b, d) = gcd(a, b).

    I don't know about this. I can use the definition of gcd, the diophantine equation of the form as + bt = c and how it relates to the gcd, and the division algorithm theorem.

    I know that gcd(a, b) divides d and gcd(b, d) divides a. I might try to show that gcd(a, b) = gcd(a + b, b) for c = 1 and then use induction for other values of c. But I don't know how to prove the base case.
     
  2. jcsd
  3. May 25, 2005 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The "diophantine" version is most often the most useful method for proof.
     
  4. May 26, 2005 #3
    What is the diophantine version? My professor mentioned it yesterday in class but he never formerly stated it. I feel like I'm missing so many important details.
     
  5. May 26, 2005 #4
    This seems to me to be all you really need. You know that gcd(a,b) divides d and a and b, same for gcd(b,d). Then there's a straight forward contradiction why gcd(a,b) can't be greater than gcd(b,d) and vice versa.
     
  6. May 26, 2005 #5
    Well, I did figure it out one way. gcd(a, b) = gcd(a + b, b) because gcd(a, b) | a and b therefore gcd(a, b) | a + b and b, and if x | a + b and x | b then x | a (x | a is what I was missing before) so x | a and x | b so by the definition of gcd, x | gcd(a, b). So gcd(a, b) = gcd(a + b, b), or gcd(a , b) = gcd(a + 1b, b).

    Then using induction, assume gcd(a, b) = gcd(a + b(c-1), b). Then since gcd(a + b(c-1), b) = gcd(a + b(c-1) + b, b) = gcd(a + bc, b), gcd(a, b) = gcd(a + bc, b) for all positive integers c. Since d = a + bc, gcd(a, b) = gcd(b, d).

    Snoble, I see. If gcd(a, b) > gcd(b, d) then gcd(b, d) does not divide gcd(a, b) (since they are positive) yet gcd(a, b) divides b and d, contradicting the definition of gcd, and the other way around.
     
  7. May 26, 2005 #6
    All I meant was that if gcd(a,b) > gcd(b,d) then gcd(a,b) is a common denominator of b and d that seems to greater than the greatest common denominator.
     
  8. May 26, 2005 #7
    I said that (paragraph 3). My book defined gcd in terms of "divides" rather than actually "greater than"; gcd(a, b) is the positive number x so that x | a and x | b, and for any y that divides a and b, y | x, so I have to translate.
     
  9. May 26, 2005 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I presume by "diophantine version" he means that the gcd(x, y) is the smallest positive integer of the form px + qy. (With p and q both integers)

    This problem is utterly trivial with this characterization. :smile:
     
  10. May 26, 2005 #9
    Well, that diophantine equation was how I learned that gcd(a, b) | d and gcd(b, d) | a. Can it be done more easily than that?

    My post #5 of this thread contained two different proofs--one in paragraphs 1 and 2 and the other in paragraph 3 based on snoble's suggestion.
     
  11. May 27, 2005 #10
    Oh sorry. Your definition is definitely the better definition since it is much more general... I should probably try to use it myself more often

    Thanks,
    Steven
     
  12. May 27, 2005 #11

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Applying the definition, the original question asks you to prove:


    The smallest positive number of the form:

    ap + bq

    is equal to the smallest positive number of the form:

    by + (a + bc)z = az + b(y+cz)
     
  13. May 27, 2005 #12
    I see. That is very simple.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Gcd proof
  1. GCD in PROOF? (Replies: 3)

  2. Gcd and lcm (Replies: 59)

  3. GCD question (Replies: 6)

Loading...