Bézout's identity

Bézout's identity (also called Bezout's lemma) is a theorem in the elementary theory of numbers: let a and b be integers, not both zero, and let d be their greatest common divisor. Then there exist integers x and y such that

$ax+by=d$

In addition, i) d is the smallest positive integer that can be written as ax + by, and ii) every integer of the form ax + by is a multiple of d. x and y are called Bézout coefficients for (a, b); they are not unique. A pair of Bézout coefficients (in fact the ones that are minimal in absolute value) can be computed by the extended Euclidean algorithm.

Bézout's lemma is true in any principal ideal domain, but there are integral domains in which it is not true.

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

Non-uniqueness of solutions

After one pair of Bézout coefficients (x, y) has been computed (using extended Euclid or some other algorithm), all pairs may be found using the formula

$\left\{\left(x+{\frac {kb}{\gcd(a,b)}},\ y-{\frac {ka}{\gcd(a,b)}}\right)\mid k\in \mathbb {Z} \right\}.$

Example

Let a = 12 and b = 42, gcd(12, 42) = 6. Then

${\begin{aligned}\vdots \\12&\times -10&+\;\;42&\times 3&=6\\12&\times -3&+\;\;42&\times 1&=6\\12&\times 4&+\;\;42&\times -1&=6\\12&\times 11&+\;\;42&\times -3&=6\\12&\times 18&+\;\;42&\times -5&=6\\\vdots \end{aligned}}$

Generalizations

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

$\gcd(a_{1},a_{2},\ldots ,a_{n})=d$

then there are integers $x_{1},x_{2},\ldots ,x_{n}$

such that

$a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}=d,$

and 1) d is smallest positive integer of this form, and 2) every number of this form is a multiple of d.

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.

Proof

Bézout's lemma is a consequence of the Euclidean division defining property, namely that the division by a nonzero integer b has a remainder strictly less than |b|. The proof that follows may be adapted for any Euclidean domain. For given nonzero integers a and b there is a nonzero integer d = as + bt of minimal absolute value among all those of the form ax + by with x and y integers; one can assume d > 0 by changing the signs of both s and t if necessary. Now the remainder of dividing either a or b by d is also of the form ax + by since it is obtained by subtracting a multiple of d = as + bt from a or b, and on the other hand it has to be strictly smaller in absolute value than d. This leaves 0 as only possibility for such a remainder, so d divides a and b exactly. If c is another common divisor of a and b, then c also divides as + bt = d. Since c divides d but is not equal to it, it must be less than d. This means that d is the greatest common divisor of a and b; this completes the proof.

See also

• AF+BG theorem, an analogue of Bézout's identity for polynomials
• Fundamental theorem of arithmetic
• Euclid's lemma

External links

• Online calculator of Bézout's identity.
• Weisstein, Eric W. "Bezouts Identity". MathWorld.