# greatest common divisor of several integers

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.
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 GreatestCommonDivisorOfSeveralIntegers 2013-03-22 19:20:14 2013-03-22 19:20:14 pahio (2872) pahio (2872) 5 pahio (2872) Theorem msc 11A05 GCD of several integers BezoutsLemma IdealDecompositionInDedekindDomain