Bézout's identity


In elementary number theory, Bézout's identity is the following theorem:
The integers x and y are called Bézout coefficients for ; they are not unique. A pair of Bézout coefficients can be computed by the extended Euclidean algorithm. If both a and b are nonzero, the extended Euclidean algorithm produces one of the two pairs such that and
.
Many other theorems in elementary number theory, such as Euclid's lemma or 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 these domains.

Structure of solutions

When one pair of Bézout coefficients has been computed, all pairs can be represented in the form
where is an arbitrary integer and the fractions simplify to integers.
Among these pairs of Bézout coefficients, exactly two of them satisfy
and equality may occur only if one of and divides the other.
This relies on a property of Euclidean division: given two integers c and d, if d does not divide c, there is exactly one pair such that and, and another one such that and.
The two pairs of small Bézout's coefficients are obtained from the given one by choosing for in the above formula either of the two integers next to.
The Extended Euclidean algorithm always produces one of these two minimal pairs.

Example

Let a = 12 and b = 42, gcd = 6. Then we have the following Bézout's identities, with the Bézout coefficients written in red for the minimal pairs and in blue for the other ones.
If is the original pair of Bézout coefficients, then yields the minimal pairs via, respectively :, and.

Proof

Given any nonzero integers and, let The set is nonempty since it contains either or . Since is a nonempty set of positive integers, it has a minimum element, by the Well-ordering principle. To prove that is the greatest common divisor of and, we must prove that is a common divisor of and, and that for any other common divisor, one has.
The Euclidean division of by may be written
The remainder is in, because
Thus is of the form, and hence. However,, and is the smallest positive integer in : the remainder can therefore not be in, making necessarily 0. This implies that is a divisor of. Similarly is also a divisor of, and is a common divisor of and.
Now, let be any common divisor of and ; that is, there exist and such that
and. One has thus
That is is a divisor of, and, therefore

Generalizations

For three or more integers

Bézout's identity can be extended to more than two integers: if
then there are integers such that
has the following properties:
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:
The generalization of this result to any number of polynomials and indeterminates is Hilbert's Nullstellensatz.

For principal ideal domains

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.
That is, if R is a PID, and a and b are elements of R, and d is a greatest common divisor of a and b,
then there are elements x and y in R such that ax + by = d. The reason is that the ideal Ra+Rb is principal and equal to Rd.
An integral domain in which Bézout's identity holds is called a Bézout domain.

History

proved this identity for polynomials. However, this statement for integers can be found already in the work of another French mathematician, Claude Gaspard Bachet de Méziriac.