# The greatest common divisor of n integers

1. Jul 29, 2012

### Ratpigeon

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$\in${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. Jul 30, 2012

### who_

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.

3. Jul 30, 2012

### voko

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
4. Jul 30, 2012

### who_

You shouldn't merely give the answer - next time, try to lead the OP toward the correct solution. :)

5. Jul 30, 2012

### Ratpigeon

Thanks, i didnt catch the counterexample which set me off on the wrong track. Should be fine now