# Bézout's identity

In elementary number theory, **Bézout's identity** (also called **Bézout's lemma**) is the following theorem:

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

The integers *x* and *y* are called **Bézout coefficients** for (*a*, *b*); 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
(equality may occur only if one of *a* and *b* is a multiple of the other).

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.

## Contents

## Structure of solutionsEdit

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

where *k* 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 *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 -|*d*| < *r* < 0.

The two pairs of small Bézout's coefficients are obtained from the given one (*x*, *y*) by choosing for *k* in the above formula either of the two integers next to .

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

### ExampleEdit

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.

If (x, y) = (18, -5) is the original pair of Bézout coefficients, then yields the minimal pairs via *k* = -3 resp. *k* = -2: (18-3⋅7, -5+3⋅2) = (-3, 1) and (18-2⋅7, -5+2⋅2) = (4, -1).

## ProofEdit

Given any nonzero integers a and b, let and The set S is nonempty since it contains either a or –*a* (with *x* = ±1 and *y* = 0). Since S is a nonempty set of positive integers, it has a minimum element , by the Well-ordering principle. To prove that d is the greatest common divisor of a and b, we must prove that d is a common divisor of a and b, and that for any other common divisor c, one has *c* < *d*.

The Euclidean division of a by d may be written

The remainder r is in , because

As d is the smallest positive integer in S, the remainder r is necessarily 0, and this implies that d is a divisor of a. Similarly d is also a divisor of b, and d is a common divisor of a and b.

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

That is c is a divisor of d, and, therefore *c* ≤ *d*

## GeneralizationsEdit

### For three or more integersEdit

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

then there are integers such that

has the following properties:

*d*is the smallest positive integer of this form- every number of this form is a multiple of
*d*

### For polynomialsEdit

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

## HistoryEdit

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 another French mathematician, Claude Gaspard Bachet de Méziriac (1581–1638).^{[2]}^{[3]}^{[4]}

## See alsoEdit

- AF+BG theorem, an analogue of Bézout's identity for homogeneous polynomials in three indeterminates
- Fundamental theorem of arithmetic
- Euclid's lemma

## NotesEdit

**^**Bézout, É. (1779).*Théorie générale des équations algébriques*. Paris, France: Ph.-D. Pierres.**^**Tignol, Jean-Pierre (2001).*Galois' Theory of Algebraic Equations*. Singapore: World Scientific. ISBN 981-02-4541-6.**^**Claude Gaspard Bachet (sieur de Méziriac) (1624).*Problèmes plaisants & délectables qui se font par les nombres*(2nd ed.). Lyons, France: Pierre Rigaud & Associates. pp. 18–33. 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, ax - by = 1) is a special case of Bézout's equation and was used by Bachet to solve the problems appearing on pages 199 ff.**^**See also: Maarten Bullynck (February 2009). "Modular arithmetic before C.F. Gauss: Systematizations and discussions on remainder problems in 18th-century Germany" (PDF).*Historia Mathematica*.**36**(1): 48–72. doi:10.1016/j.hm.2008.08.009.

## External linksEdit

- Online calculator for Bézout's identity.
- Weisstein, Eric W. "Bézout's Identity".
*MathWorld*.