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: 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