Bézout's identity

Template:Short description Template:About

In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout who proved it for polynomials, is the following theorem: Template:Math theorem

Here the greatest common divisor of Template:Math and Template:Math is taken to be Template:Math. The integers Template:Math and Template:Math are called Bézout coefficients for Template:Math; they are not unique. A pair of Bézout coefficients can be computed by the extended Euclidean algorithm, and this pair is, in the case of integers one of the two pairs such that Template:Math and Template:Math; equality occurs only if one of Template:Math and Template:Math is a multiple of the other.

As an example, the greatest common divisor of 15 and 69 is 3, and 3 can be written as a combination of 15 and 69 as Template:Math, with Bézout coefficients −9 and 2.

Many other theorems in elementary number theory, such as Euclid's lemma or the Chinese remainder theorem, result from Bézout's identity.

A Bézout domain is an integral domain in which Bézout's identity holds. In particular, Bézout's identity holds in principal ideal domains. Every theorem that results from Bézout's identity is thus true in all principal ideal domains.

Structure of solutionsEdit

If Template:Math and Template:Math are not both zero and one pair of Bézout coefficients Template:Math has been computed (for example, using the extended Euclidean algorithm), all pairs can be represented in the form <math display=block>\left(x-k\frac{b}{d},\ y+k\frac{a}{d}\right),</math> where Template:Math is an arbitrary integer, Template:Math is the greatest common divisor of Template:Math and Template:Math, and the fractions simplify to integers.

If Template:Mvar and Template:Mvar are both nonzero and none of them divides the other, then exactly two of the pairs of Bézout coefficients satisfy <math display="block"> |x| < \left |\frac{b}{d}\right |\quad \text{and}\quad |y| < \left |\frac{a}{d}\right |.</math> If Template:Mvar and Template:Mvar are both positive, one has <math>x>0</math> and <math>y<0</math> for one of these pairs, and <math>x<0</math> and <math>y>0</math> for the other. If Template:Math is a divisor of Template:Mvar (including the case <math>b=0</math>), then one pair of Bézout coefficients is Template:Math.

This relies on a property of Euclidean division: given two non-zero integers Template:Math and Template:Math, if Template:Mvar does not divide Template:Mvar, there is exactly one pair Template:Math such that Template:Math and Template:Math, and another one such that Template:Math and Template:Math.

The two pairs of small Bézout's coefficients are obtained from the given one Template:Math by choosing for Template:Mvar in the above formula either of the two integers next to Template:Math.

The extended Euclidean algorithm always produces one of these two minimal pairs.

ExampleEdit

Let Template:Math and Template:Math, then Template:Math. Then the following Bézout's identities are had, with the Bézout coefficients written in red for the minimal pairs and in blue for the other ones.

<math display="block">\begin{align} \vdots \\ 12 &\times ({\color{blue}{-10}}) & + \;\; 42 &\times \color{blue}{3} &= 6 \\ 12 &\times ({\color{red}{-3}}) & + \;\;42 &\times \color{red}{1} &= 6 \\ 12 &\times \color{red}{4} & + \;\;42 &\times({\color{red}{-1}}) &= 6 \\ 12 &\times \color{blue}{11} & + \;\;42 &\times ({\color{blue}{-3}}) &= 6 \\ 12 &\times \color{blue}{18} & + \;\;42 &\times ({\color{blue}{-5}}) &= 6 \\ \vdots \end{align}</math>

If Template:Math is the original pair of Bézout coefficients, then Template:Math yields the minimal pairs via Template:Math, respectively Template:Math; that is, Template:Math, and Template:Math.

Existence proofEdit

Given any nonzero integers Template:Mvar and Template:Mvar, let Template:Math. The set Template:Mvar is nonempty since it contains either Template:Mvar or Template:Math (with Template:Math and Template:Math). Since Template:Mvar is a nonempty set of positive integers, it has a minimum element Template:Math, by the well-ordering principle. To prove that Template:Mvar is the greatest common divisor of Template:Mvar and Template:Mvar, it must be proven that Template:Mvar is a common divisor of Template:Mvar and Template:Mvar, and that for any other common divisor Template:Mvar, one has Template:Math.

The Euclidean division of Template:Mvar by Template:Mvar may be written as <math display="block">a=dq+r\quad\text{with}\quad 0\le r<d.</math> The remainder Template:Mvar is in Template:Math, because <math display="block">\begin{align} r & = a - qd \\ & = a - q(as+bt)\\ & = a(1-qs) - bqt. \end{align}</math> Thus Template:Mvar is of the form Template:Math, and hence Template:Math. However, Template:Math, and Template:Mvar is the smallest positive integer in Template:Mvar: the remainder Template:Mvar can therefore not be in Template:Mvar, making Template:Mvar necessarily 0. This implies that Template:Mvar is a divisor of Template:Mvar. Similarly Template:Mvar is also a divisor of Template:Mvar, and therefore Template:Mvar is a common divisor of Template:Mvar and Template:Mvar.

Now, let Template:Mvar be any common divisor of Template:Mvar and Template:Mvar; that is, there exist Template:Mvar and Template:Mvar such that Template:Math and Template:Math. One has thus <math display="block">\begin{align} d&=as + bt\\ & =cus+cvt\\ &=c(us+vt). \end{align} </math> That is, Template:Mvar is a divisor of Template:Mvar. Since Template:Math, this implies Template:Math.

GeneralizationsEdit

For three or more integersEdit

Bézout's identity can be extended to more than two integers: if <math display="block">\gcd(a_1, a_2, \ldots, a_n) = d</math> then there are integers <math>x_1, x_2, \ldots, x_n</math> such that <math display="block">d = a_1 x_1 + a_2 x_2 + \cdots + a_n x_n</math> has the following properties:

Template:Math is the smallest positive integer of this form
every number of this form is a multiple of Template:Math

For polynomialsEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Bézout's identity does not always hold for polynomials. For example, when working in the polynomial ring of integers: the greatest common divisor of Template:Math and Template:Math is x, but there does not exist any integer-coefficient polynomials Template:Math and Template:Math satisfying Template:Math.

However, Bézout's identity works for univariate polynomials over a field exactly in the same ways as for integers. In particular the Bézout's coefficients and the greatest common divisor may be computed with the extended Euclidean algorithm.

As the common roots of two polynomials are the roots of their greatest common divisor, Bézout's identity and fundamental theorem of algebra imply the following result: Template:Block indent

The generalization of this result to any number of polynomials and indeterminates is Hilbert's Nullstellensatz.

For principal ideal domainsEdit

As noted in the introduction, Bézout's identity works not only in the ring of integers, but also in any other principal ideal domain (PID). That is, if Template:Math is a PID, and Template:Mvar and Template:Mvar are elements of Template:Math, and Template:Mvar is a greatest common divisor of Template:Mvar and Template:Mvar, then there are elements Template:Math and Template:Math in Template:Math such that Template:Math. The reason is that the ideal Template:Math is principal and equal to Template:Math.

An integral domain in which Bézout's identity holds is called a Bézout domain.

History and attributionEdit

The French mathematician Étienne Bézout (1730–1783) proved this identity for polynomials.<ref>Template:Cite book</ref> The statement for integers can be found already in the work of an earlier French mathematician, Claude Gaspard Bachet de Méziriac (1581–1638).<ref> Template:Cite book</ref><ref>Template:Cite book On these pages, Bachet proves (without equations) "Proposition XVIII. Deux nombres premiers entre eux estant donnez, treuver le moindre multiple de chascun d’iceux, surpassant de l'unité un multiple de l'autre." (Given two numbers [which are] relatively prime, find the lowest multiple of each of them [such that] one multiple exceeds the other by unity (1).) This problem (namely, Template:Math) is a special case of Bézout's equation and was used by Bachet to solve the problems appearing on pages 199 ff.</ref><ref>See also: Template:Cite journal</ref> Andrew Granville traced the association of Bézout's name with the identity to Bourbaki, arguing that it is a misattribution since the identity is implicit in Euclid's Elements.<ref>Template:Cite arXiv</ref>