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

Greatest commen divisor question

  1. Sep 27, 2005 #1
    Hi got basic question:

    I'm suppose to prove that gcd(a,b) = ax+by,

    What is the best way of proving this?

    Is that by claiming if d = gcd(a,b) can be devide a,b then
    gcd(a,b) = ax +by ??

  2. jcsd
  3. Sep 27, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    What's x and y then?

    I`m sure the question is: Prove that there exist x and y, such that ax+by=gcd(a,b), for positive integers a,b.

    Whar do you know about the gcd?
  4. Sep 27, 2005 #3


    User Avatar
    Science Advisor

    A really good way to begin any problem is by stating it clearly!

    You are asked to prove that GCD(a,b)= ax+ by for SOME specific integer values of x and y.
    (And typically one of x and y will be positive, the other negative.)

    To answer your question- No, "claiming if d = gcd(a,b) can be devide a,b then
    gcd(a,b) = ax +by " is not a good way to prove that same statement!

    What theorems or properties of integers do you know that you can use?
  5. Sep 27, 2005 #4


    User Avatar
    Science Advisor
    Homework Helper

    What you have to prove is that there are integers x and y such that gcd(a,b) = ax + by. Well if d = gcd(a,b) then d | a and d | b, so we can say a = dm, b = dn. We then get for ANY x and y:

    ax + by = dmx + dny = d(mx + ny), and d clearly divides this expression, so d divides ax + by. Since d | (ax + by) for any x and y, then choosing x and y so that (ax + by) is as small (but positive) as possible, you know that d divides it, so you have that d divides the smallest "linear combination" of a and b. What you want to end up proving is that d is the smallest linear combination of a and b, so you might want to proceed by showing that the smallest linear combination of a and b, whatever it may be, divides gcd(a,b). Have you done any group theory?
  6. Sep 27, 2005 #5
    Hi AKG,

    No I haven't done any group theory yet! Please bear with me,
    So basicly what You are saying is that if I need to show is that if one choose an 'x' and 'y' small enough and d can be devide 'a' and 'b'. Then this proofs that there the gcd(a,b) equals the linear combinations "ax+by" ?

  7. Sep 27, 2005 #6
    Hello Hall and thank You for your answer,

    The only integer theorem I know, is that "Every integer n > 1 is either a prime or a product of primes". Is that what You are refering too ?


Share this great discussion with others via Reddit, Google+, Twitter, or Facebook