greatest common divisor of several integers

Theorem.  If the greatest common divisor of the nonzero integers $a_1,a_2,\mathrm{\dots },a_n$ is $d$, then there exist the integers $x_1,x_2,\mathrm{\dots },x_n$ such that

$d=x_1{a}_1+x_2{a}_2+\mathrm{\dots }+x_n{a}_n.$ (1)

Proof.  In the case  $n=2$  the Euclidean algorithm 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  .
Since obviously

$$d=\gcd (a_1,a_2,\mathrm{\dots },a_k)=\gcd (\gcd (a_1,a_2,\mathrm{\dots },a_{k-1}),a_k),$$

we may write by (2) that

$$d=x\gcd (a_1,a_2,\mathrm{\dots },a_{k-1})+y{a}_k$$

and thus by the induction hypothesis that

$$d=x(x_1{a}_1+x_2{a}_2+\mathrm{\dots }+x_{k-1}{a}_{k-1})+y{a}_k.$$

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

Note.  An analogous theorem concerns elements of any Bézout domain (http://planetmath.org/BezoutDomain).

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