The greatest common divisor of n integers

[Ratpigeon]

Homework Statement

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

Homework Equations

Euclid's Algorithm?

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.

 

[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.

 

[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.

 

[who_]

This is done by induction.

Assume that gcd(a_1, a_2) = q_1 a_1 + q_2 a_2. This is indeed the case and is known as Bézout's identity (see below).

Now assume gcd(a_1, ..., a_n) = q_1 a_1 + ... + q_n a_n, and check for gcd(a_1, ..., a_n, a_{n + 1}).

It is trivial to show that gcd(a_1, ..., a_n, a_{n + 1}) = gcd(gcd(a_1, ..., a_n), a_{n + 1}), that is, gcd(a_1, ..., a_n, a_{n + 1}) = A gcd(a_1, ..., a_n) + B a_{n + 1} = A (q_1 a_1 + ... + q_n a_n) + B a_{n + 1} = A q_1 a_1 + ... + A q_n a_n + B a_{n + 1}, which is what we are looking for.

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

 

[Ratpigeon]

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