# 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

$\mathrm{gcd}(a,b)=xa+yb.$ | (2) |

Make the induction hypothesis that the theorem is true whenever $$.

Since obviously

$$d=\mathrm{gcd}({a}_{1},{a}_{2},\mathrm{\dots},{a}_{k})=\mathrm{gcd}(\mathrm{gcd}({a}_{1},{a}_{2},\mathrm{\dots},{a}_{k-1}),{a}_{k}),$$ |

we may write by (2) that

$$d=x\mathrm{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 |