## You are here

Homegreatest common divisor of several integers

## Primary tabs

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

Keywords:

linear combination

Related:

BezoutsLemma, IdealDecompositionInDedekindDomain

Synonym:

GCD of several integers

Type of Math Object:

Theorem

Major Section:

Reference

Parent:

Groups audience:

## Mathematics Subject Classification

11A05*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections