greatest common divisor of several integers

Theorem. If the greatest common divisor of the nonzero integers $a_{1},\,a_{2},\,\ldots,\,a_{n}$ is $d$ , then there exist the integers $x_{1},\,x_{2},\,\ldots,\,x_{n}$ such that

\displaystyle d\;=\;x_{1}a_{1}\!+\!x_{2}a_{2}\!+\ldots+\!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

\displaystyle\gcd(a,\,b)\;=\;xa\!+\!yb.

(2)

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

d\;=\;\gcd(a_{1},\,a_{2},\,\ldots,\,a_{k})\;=\;\gcd(\gcd(a_{1},\,a_{2},\,% \ldots,\,a_{k-1}),\,a_{k}),

we may write by (2) that

d\;=\;x\gcd(a_{1},\,a_{2},\,\ldots,\,a_{k-1})+ya_{k}

and thus by the induction hypothesis that

d\;=\;x(x_{1}a_{1}\!+\!x_{2}a_{2}\!+\ldots+\!x_{k-1}a_{k-1})\!+\!ya_{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