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: The greatest common divisor of n integers

  1. Jul 29, 2012 #1
    1. The problem statement, all variables and given/known data
    define the gcd of a set of n integers, S={a_1...a_n}
    Prove that exists and can be written as
    q_1 a_1+...+q_n a_n for some integers, q_1....q_n

    2. Relevant equations

    Euclid's Algorithm?

    3. The attempt at a solution

    I have the statement that gcd(a_1....a_n) = min( gcd(a_i, a_j) i,j[itex]\in[/itex]{1...n})

    and then I know that I can say since any two numbers have a gcd, the gcd exists, and can be represented as a linear combination of the a_i and a_j that have the minimal gcd, but I don't know how to prove the first statement.
  2. jcsd
  3. Jul 30, 2012 #2
    I say this should be moved to the Precalculus help page...

    Anyhow... :) Well, for a start, your statement is NOT true.
    Consider {6,10,15}. Then gcd (6,10,15) = 1, but gcd(6,10) = 2, gcd(6,15) = 3, and gcd(10,15) = 10.

    Try solving it for n = 3. See if that gives you any ideas on how to approach the general case.
  4. Jul 30, 2012 #3
    This is easily done by induction (over the number of arguments) from gcd(a_1, a_2) = q_1 a_1 + q_2 a_2.
    Last edited: Jul 30, 2012
  5. Jul 30, 2012 #4
    You shouldn't merely give the answer - next time, try to lead the OP toward the correct solution. :)
  6. Jul 30, 2012 #5
    Thanks, i didnt catch the counterexample which set me off on the wrong track. Should be fine now
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook