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


    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


    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

  12. May 27, 2005 #11


    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook