Bézout's identity

In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout, is the following theorem:

Bézout's identity — Let a and b be integers or polynomials with greatest common divisor d. Then there exist integers or polynomials x and y such that ax + by = d. Moreover, the integers or polynomials of the form az + bt are exactly the multiples of d.

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 3 = 15 × (−9) + 69 × 2, 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.

If a and b are not both zero and one pair of Bézout coefficients (x, y) has been computed (e.g., using extended Euclidean algorithm), all pairs can be represented in the form

where k is an arbitrary integer, d is the greatest common divisor of a and b, and the fractions simplify to integers.

If a and b are both nonzero, then exactly two of these pairs of pairs of Bézout coefficients satisfy

This relies on a property of Euclidean division: given two non-zero integers c and d, if d does not divide c, there is exactly one pair (q, r) such that c = dq + r and 0 < r < |d|, and another one such that c = dq + r and -|d| < r < 0.

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

Let a = 12 and b = 42, then gcd (12, 42) = 6. 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.

Now, let c be any common divisor of a and b; that is, there exist u and v such that a = cu and b = cv. One has thus

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.

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

French mathematician Étienne Bézout (1730–1783) proved this identity for polynomials.[1] However, this statement for integers can be found already in the work of an earlier French mathematician, Claude Gaspard Bachet de Méziriac (1581–1638).[2][3][4]