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 |x|\le | b/d | and |y|\le | a/d |; 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 \deg x < \deg b or \deg y < \deg a (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
\left(x-k\frac{b}{d},\ y+k\frac{a}{d}\right),
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 pairs of Bézout coefficients satisfy
|x| \le \left |\frac{b}{d}\right |\quad \text{and}\quad |y| \le \left |\frac{a}{d}\right |,
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 \frac{x}{b/d}.
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.
\begin{align} \vdots \\ 12 &\times ({\color{blue}{-10}}) & + \;\; 42  &\times \color{blue}{3} &= 6 \\ 12 &\times ({\color{red}{-3}}) & + \;\;42  &\times \color{red}{1} &= 6 \\ 12 &\times \color{red}{4}  & + \;\;42  &\times({\color{red}{-1}}) &= 6 \\ 12 &\times \color{blue}{11} & + \;\;42  &\times ({\color{blue}{-3}}) &= 6 \\ 12 &\times \color{blue}{18} & + \;\;42  &\times ({\color{blue}{-5}}) &= 6 \\ \vdots \end{align}
If  is the original pair of Bézout coefficients, then \frac{18}{42/6} \in [2, 3] yields the minimal pairs via , respectively ; that is, , and .
Proof
Given any nonzero integers  and , let S=\{ax+by \mid x,y\in\mathbb{Z} \text{ and } ax+by>0\}.
The set  is nonempty since it contains either  or  (with  and ).
Since  is a nonempty set of positive integers, it has a minimum element d = as + bt, by the Well-ordering principle.
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
a=dq+r\quad\text{with}\quad 0\le r<d.
The remainder  is in S\cup \{0\}, because
\begin{align} r  & = a - qd \\ & = a - q(as+bt)\\ & = a(1-qs) - bqt.
\end{align}
Thus  is of the form ax+by, and hence r\in S\cup \{0\}.
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  and .
One has thus
\begin{align}d&=as + bt\\ & =cus+cvt\\ &=c(us+vt).
\end{align}
That is  is a divisor of , and, therefore Generalizations
For three or more integers
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
d = a_1 x_1 + a_2 x_2 + \cdots + a_n x_n
has the following properties:
d is the smallest positive integer of this form
every number of this form is a multiple of d
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:
For univariate polynomials f and g with coefficients in a field, there exist polynomials a and b such that af + bg = 1 if and only if f and g have no common root in any algebraically closed field (commonly the field of complex numbers).
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 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 is that the ideal Ra+Rb is principal and equal to Rd.
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.
However, this statement for integers can be found already in the work of an earlier French mathematician, Claude Gaspard Bachet de Méziriac (1581–1638).
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.
See also:
See also
AF+BG theorem, an analogue of Bézout's identity for homogeneous polynomials in three indeterminates
Fundamental theorem of arithmetic
Euclid's lemma
Notes
External links
Online calculator for Bézout's identity.
