Bézout's identity

From Wikipedia, the free encyclopedia

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

1 History
2 Algorithm
3 Example
4 Generalizations
5 Proof
6 External links

[edit] History

Bézout's identity is named after Étienne Bézout. However, this identity has also been attributed to French mathematician Claude Gaspard Bachet de Méziriac.^{[citation needed]}

[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

<math> \{ (x+kb, y-ka) \mid k \in \mathbb{Z} \}. </math>

[edit] Example

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

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 <math>a_1, \ldots, a_n</math> with greatest common divisor g there exist integers <math>x_1, \ldots, x_n</math> such that

<math>a_1 x_1 + \cdots + a_n x_n = g</math>

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

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.