Bézout's identity

Structure of solutions

When 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

( x + k b gcd ( a , b ) ,   y − k a gcd ( a , b ) ) ,

where k is an arbitrary integer and the fractions simplify to integers.

Among these pairs of Bézout coefficients, exactly two of them satisfy

| x | ≤ | b gcd ( a , b ) | and | y | ≤ | a gcd ( a , b ) | ,

and equality may occur only if one of a and b 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 (q,r) such that c = dq + r and 0 < r < |d|, and another one such that c = dq + r and 0 < -r < |d|. The two pairs of small Bézout's coefficients are obtained by choosing k in the above formula for getting either remainder of the division of x by b / gcd ( a , b ) .

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

Example

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

⋮ 12 × − 10 + 42 × 3 = 6 12 × − 3 + 42 × 1 = 6 12 × 4 + 42 × − 1 = 6 12 × 11 + 42 × − 3 = 6 12 × 18 + 42 × − 5 = 6 ⋮

Proof

(proof adapted from 'proofwiki.org')

Bézout's lemma is a consequence of the defining property of Euclidean division, namely: that dividing a positive integer p by a positive integer q yields a remainder greater than or equal to zero and strictly less than q .

i.e. p = n q + r , 0 ≤ r < q

To begin the proof of Bézout's lemma, let d be the smallest positive integer of the form a x + b y . Specifically,

let d = a s + b t

let n = a x + b y , n > d

If n is not divisible by d, then according to Euclidean division,

which of course is of the form a x + b y

But r < d which violates the original premise that d is the smallest number in that form, therefore r = 0 and

n is divisible by d

Since n can be any number of the form a x + b y lets look at the following specific examples:

Therefore, d is a common divisor to both a and b

If there exists another common divisor ( c ) of a and b , then it also divides d

If c divides d, then c ≤ d

Therefore, (finally) d is the greatest common divisor.

This proof does not provide a method for computing Bézout's coefficients. However, Bézout's lemma is also a corollary of the proof of the Extended Euclidean algorithm and this algorithm does provide an efficient method of computing these coefficients. This algorithm and the associated proof may also be extended to any Euclidean domain.

For three or more integers

Bézout's identity can be extended to more than two integers: if

gcd ( a 1 , a 2 , … , a n ) = d

then there are integers x 1 , x 2 , … , x n such that

d = a 1 x 1 + a 2 x 2 + ⋯ + a n x n

has the following properties:

d is the smallest positive integer of this form

every number of this form is a multiple of d

For polynomials

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:

For univariate polynomials f and g with coefficients in a field, there exist polynomials a and b such that af + bg = 1 if and only if f and g have no common root in any algebraically closed field (commonly the field of complex numbers).

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 (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: the ideal Ra+Rb is principal and indeed is equal to Rd.

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

History

French mathematician Étienne Bézout (1730–1783) 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 (1581–1638).