greatest common divisor of several integers

Theorem.  If the greatest common divisorMathworldPlanetmathPlanetmath of the nonzero integers a1,a2,,an is d, then there exist the integers x1,x2,,xn such that

d=x1a1+x2a2++xnan. (1)

Proof.  In the case  n=2  the Euclidean algorithmMathworldPlanetmath for two nonzero integers a,b always guarantees the integers x,y such that

gcd(a,b)=xa+yb. (2)

Make the induction hypothesis that the theorem is true whenever  n<k.
Since obviously


we may write by (2) that


and thus by the induction hypothesis that


Consequently, we have gotten an equation of the form (1), Q.E.D.

Note.  An analogous theorem concerns elements of any Bézout domain (

Title greatest common divisor of several integers
Canonical name GreatestCommonDivisorOfSeveralIntegers
Date of creation 2013-03-22 19:20:14
Last modified on 2013-03-22 19:20:14
Owner pahio (2872)
Last modified by pahio (2872)
Numerical id 5
Author pahio (2872)
Entry type Theorem
Classification msc 11A05
Synonym GCD of several integers
Related topic BezoutsLemma
Related topic IdealDecompositionInDedekindDomain