Bézout's identity

Bézout's identity

In number theory, Bézout's identity for two integers a, b is an expression

$ax+by=d \,$

where x and y are integers (called Bézout coefficients for (a,b)), such that d is a common divisor of a and b. Bézout's lemma states that such coefficients exist for every pair of nonzero integers (a,b). In addition d > 0 is their greatest common divisor and the smallest positive integer that can be written, in this form, for any integers x,y. This value of d is therefore uniquely determined by a and b, but the Bézout coefficients 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. The identity, coefficients and lemma are named after the French mathematician Étienne Bézout.

In abstract algebra, certain pairs of elements of an integral domain may also admit such an identity, but this need not be the case for all pairs of nonzero elements. Bézout's lemma does however remain valid in any principal ideal domain.

History

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

Algorithm

The Bézout numbers x and y as above can be determined with the extended Euclidean algorithm. However, they are not unique. If one solution is given by (x, y), then there are infinitely many solutions. These are given by

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

Example

The greatest common divisor of 12 and 42 is 6. Bézout's identity states that there must exist an integer solution for x and y in the following equation:

$12x + 42y = 6. \,$

One of its solutions is x = −3 and y = 1: indeed, we have (−3)·12 + 1·42 = 6. Another solution is x = 4 and y = −1.

Generalizations

Bézout's identity can be extended to linear combinations of more than two numbers. For any numbers $a_1, \ldots, a_n$ with greatest common divisor d there exist integers $x_1, \ldots, x_n$ such that

$a_1 x_1 + \cdots + a_n x_n = d.$

The greatest common divisor of $a_1, \ldots, a_n$ is in fact the smallest positive integer that can be written as a linear combination of $a_1, \ldots, a_n$.

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

A proof of Bézout's lemma can be given using of the fact that the integers form a Euclidean domain (for the absolute value), as affirmed by the defining property of Euclidean division of integers, namely that the remainder of a division by a nonzero integer b has a remainder strictly less than |b|. For given nonzero integers a and b there is a nonzero integer d = as + bt of minimal absolute 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, which means that d is the greatest common divisor of a and b; this completes the proof.

Notes

1. ^ Tignol, Jean-Pierre (2001). Galois' Theory of Algebraic Equations. Singapore: World Scientific. ISBN 981-02-4541-6.
2. ^ Claude Gaspard Bachet, sieur de Méziriac, Problèmes plaisants et délectables… , 2nd ed. (Lyons, France: Pierre Rigaud & Associates, 1624), pages 18-33. (Available on-line from the Bavarian State Library at: http://www.bsb-muenchen-digital.de/~web/web1008/bsb10081407/images/index.html?digID=bsb10081407&pimage=38&v=100&nav=0&l=de ) 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.
3. ^ See also: Maarten Bullynck (February 2009) "Modular arithmetic before C.F. Gauss. Systematisations and discussions on remainder problems in 18th century Germany," Historica Mathematica, volume 36, number 1, pages 48-72. Available on-line at: http://www.kuttaka.org/Gauss_Modular.pdf .

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Bézout domain — In mathematics, a Bézout domain is an integral domain which is, in a certain sense, a non Noetherian analogue of a principal ideal domain. More precisely, a Bézout domain is a domain in which every finitely generated ideal is principal. A… …   Wikipedia

• Étienne Bézout — (March 31, 1730 September 27, 1783) was a French mathematician who was born in Nemours, Seine et Marne, France, and died in Basses Loges (near Fontainebleau), France.WorkIn 1758 Bézout was elected an adjoint in mechanics of the French Academy of… …   Wikipedia

• Identidad de Bézout — La identidad de Bézout o Lema de Bézout enuncia que si a y b son números enteros con máximo común divisor d, entonces existen enteros x e y tales que Los números x e y pueden determinarse mediante el algoritmo extendido de Euclides, pero no se… …   Wikipedia Español

• List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

• Smith normal form — The Smith normal form is a normal form that can be defined for any matrix (not necessarily square) with entries in a principal ideal domain (PID). The Smith normal form of a matrix is diagonal, and can be obtained from the original matrix by… …   Wikipedia

• Coprime — In number theory, a branch of mathematics, two integers a and b are said to be coprime (also spelled co prime) or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common …   Wikipedia

• Generating set of a group — In abstract algebra, a generating set of a group is a subset that is not contained in any proper subgroup of the group. Equivalently, a generating set of a group is a subset such that every element of the group can be expressed as the combination …   Wikipedia

• List of number theory topics — This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic …   Wikipedia

• Group (mathematics) — This article covers basic notions. For advanced topics, see Group theory. The possible manipulations of this Rubik s Cube form a group. In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines …   Wikipedia

• Diophantine equation — In mathematics, a Diophantine equation is an indeterminate polynomial equation that allows the variables to be integers only. Diophantine problems have fewer equations than unknown variables and involve finding integers that work correctly for… …   Wikipedia