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: Here the greatest common divisor of and is taken to be . The integers or polynomials and are called Bézout coefficients for ; they are not unique. A pair of Bézout coefficients can be computed by the extended Euclidean algorithm, and this pair is, in the case of integers one of the two pairs such that formula_1 and formula_2 equality occurs only if one of and is a multiple of the other. In the polynomial case, the extended Euclidean algorithm produces  the unique pair such that formula_3 or formula_4 (both inequalities are verified except one of and is a multiple of the other). 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 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. Structure of solutions. If and are not both zero and one pair of Bézout coefficients has been computed (e.g., using extended Euclidean algorithm), all pairs can be represented in the form where is an arbitrary integer, is the greatest common divisor of and , and the fractions simplify to integers. If and are both nonzero, then exactly two of these pairs of Bézout coefficients satisfy formula_6 and equality may occur only if one of and divides the other. This relies on a property of Euclidean division : given two non-zero integers and , if does not divide , there is exactly one pair such that and , and another one such that and . The two pairs of small Bézout's coefficients are obtained from the given one by choosing for in the above formula either of the two integers next to formula_7. The extended Euclidean algorithm always produces one of these two minimal pairs. Example. Let and , then . 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. formula_8 If is the original  pair of Bézout coefficients, then formula_9 yields the minimal pairs via , respectively ; that is, , and . Proof. Given any nonzero integers and , let formula_10 The set is nonempty since it contains either or (with and ). Since is a nonempty set of positive integers, it has a minimum element formula_11. To prove that is the greatest common divisor of and , it must be proven that is a common divisor of and , and that for any other common divisor , one has . The Euclidean division of by may be written formula_12 The remainder is in formula_13, because formula_14 Thus is of the form formula_15 , and hence formula_16. However, , and is the smallest positive integer in : the remainder can therefore not be in , making necessarily 0. This implies that is a divisor of . Similarly is also a divisor of , and is a common divisor of and . Now, let be any common divisor of and ; that is, there exist and such that formula_17 That is, is a divisor of . Since , this implies . Generalizations. For three or more integers. Bézout's identity can be extended to more than two integers: if formula_18 then there are integers formula_19 such that formula_20 has the following properties: 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: 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 is a PID, and and are elements of , and is a greatest common divisor of and , then there are elements and in such that . The reason is that the ideal is principal and equal to . 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. This statement for integers can be found already in the work of an earlier French mathematician, Claude Gaspard Bachet de Méziriac (1581–1638).