Bézout's identity

From Wikipedia, the free encyclopedia

In number theory, Bézout's identity or Bézout's lemma is a linear diophantine equation. It states that if a and b are nonzero integers with greatest common divisor d, then there exist integers x and y (called Bézout numbers or Bézout coefficients) such that

$ax+by=d. \,$

1 History
2 Algorithm
3 Example
4 Generalizations
5 Proof
6 See also
7 Reference
8 External links

[edit] History

Bézout's identity is named after Étienne Bézout, who proved it for polynomials. However, this statement for integers can be found already in the work of French mathematician Claude Gaspard Bachet de Méziriac.^[1]

[edit] 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\}.$

[edit] Example

The greatest common divisor of 12 and 42 is 6. So the Bézout's identity is

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

[edit] 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 g there exist integers $x_1, \ldots, x_n$ such that

$a_1 x_1 + \cdots + a_n x_n = g$

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.

[edit] Proof

Let d denote the greatest common divisor of a and b. Set p = a / d and q = b / d, then p and q are coprime. Now, consider the numbers p, 2p, …, (q−1)p. None of these numbers is congruent to 0 modulo q, and they are also all distinct modulo q. This means that (p, 2p, …, (q−1)p) is a permutation of (1, 2, …, q − 1) modulo q. Therefore, there has to be a number x with 1 ≤ x ≤ q − 1 such that px ≡ 1 (mod q). This means that there is an integer y such that px + qy = 1 and by multiplying this equation by d we find ax + by = d.

Another proof ^[2] of Bézout's identity makes use of the division algorithm and the fact that the set of positive integers is well ordered. We can assume WLOG that a and b are positive. Consider that set S of all positive integers of the form am + bn, where m and n are integers. This set is nonempty and so by the well-ordering principle there is a least member, d = ax + by. By the division algorithm, there are also integers q and r such that a = qd + r with 0 ≤ r < d. But r = a − qd = a − q*(ax + by) = a(1 − qx) + b(−qy). It follows that r = 0, otherwise $r \in S$ contradicting the fact that d is the least element in S. Hence a = qd, i.e. d divides a. Similarly (by applying the division algorithm to b in lieu of a) we find that d divides b. So d is a common divisor of a and b. If c is another common divisor of a and b, then c also divides ax + by = d. By definition, d is the greatest common divisor of a and b, and the proof is complete.