Bézout's identity

In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout who proved it for polynomials, is a theorem which relates two arbitrary integers with their greatest common divisor. The theorem's statement is as follows: Template:Math theorem

(The greatest common divisor of 0 and 0 is taken to be 0.) The integers x and y are called Bézout coefficients for (a, b); they are not unique. The extended Euclidean algorithm can be used to compute a minimal pair of Bézout coefficients, meaning they satisfy $|x|\le |b/d|$ and $|y|<|a/d|$; equality occurs only if one of a and b is a multiple of the other, and otherwise there exist exactly two minimal pairs.

As an example, the greatest common divisor of $a=15$ and $b=69$ is $d=3$, which can be written as the linear combination $ax+by=15(-9)+69(2)=3$ with Bézout coefficients $(x,y)=(-9,2)$, which are minimal since $9<69/3=23$ and $2<15/3=5$. The other minimal Bézout coefficients are $(x,y)=(-9+23,2-5)=(14,-3)$.

Many other theorems in elementary number theory, such as Euclid's lemma or the Chinese remainder theorem, can be formally deduced 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 a and b are not both zero and one pair of Bézout coefficients (x, y) has been computed (for example, using the extended Euclidean algorithm), all pairs can be represented in the form $$(x-k\frac{b}{d},y+k\frac{a}{d}),$$ where k is an arbitrary integer, d is the greatest common divisor of a and b, and the fractions simplify to integers.

If Template:Mvar and Template:Mvar are both nonzero and none of them divides the other, then exactly two of the pairs of Bézout coefficients satisfy $$|x|<\left|\frac{b}{d}\right|\text{and}|y|<\left|\frac{a}{d}\right|.$$ If Template:Mvar and Template:Mvar are both positive, one has $x>0$ and $y<0$ for one of these pairs, and $x<0$ and $y>0$ for the other. If a > 0 is a divisor of Template:Mvar (including the case $b=0$), then one pair of Bézout coefficients is (1, 0).

This relies on a property of Euclidean division: given two non-zero integers c and d, if Template:Mvar does not divide Template:Mvar, there is exactly one pair (q, r) such that c = dq + r and 0 < r < Template:Abs, and another one such that c = dq + r and −Template:Abs < r < 0.

The two pairs of minimal Bézout coefficients are obtained from the given one (x, y) by choosing for Template:Mvar in the above formula either of the two integers nearest to Template:Sfrac.

The extended Euclidean algorithm always produces one of these two minimal pairs.

Example

Let a = 12 and b = 42, then gcd (12, 42) = 6. Then the following Bézout's identities are [had] held, with the Bézout coefficients written in red for the minimal pairs and in blue for the other ones.

$$\begin{array}{r}⋮\\ 12& \times (-10)& +42& \times 3& =6\\ 12& \times (-3)& +42& \times 1& =6\\ 12& \times 4& +42& \times (-1)& =6\\ 12& \times 11& +42& \times (-3)& =6\\ 12& \times 18& +42& \times (-5)& =6\\ ⋮\end{array}$$

If (x, y) = (18, −5) is the original pair of Bézout coefficients, then Template:Sfrac ∈ [2, 3] yields the minimal pairs via k = 2, respectively k = 3; that is, (18 − 2 ⋅ 7, −5 + 2 ⋅ 2) = (4, −1), and (18 − 3 ⋅ 7, −5 + 3 ⋅ 2) = (−3, 1).

Existence proof

Given any nonzero integers Template:Mvar and Template:Mvar, let S = Template:Mset. The set Template:Mvar is nonempty since it contains either Template:Mvar or –a (with x = ±1 and y = 0). Since Template:Mvar is a nonempty set of positive integers, it has a minimum element d = as + bt, by the well-ordering principle. To prove that Template:Mvar is the greatest common divisor of Template:Mvar and Template:Mvar, it must be proven that Template:Mvar is a common divisor of Template:Mvar and Template:Mvar, and that for any other common divisor Template:Mvar, one has c ≤ d.

The Euclidean division of Template:Mvar by Template:Mvar may be written as $$a=dq+r\text{with}0\le r<d.$$ The remainder Template:Mvar is in S ∪ Template:Mset, because $$\begin{array}{rl}r& =a-qd\\ & =a-q(as+bt)\\ & =a(1-qs)-bqt.\end{array}$$ Thus Template:Mvar is of the form ax + by, and hence r ∈ S ∪ Template:Mset. However, 0 ≤ r < d, and Template:Mvar is the smallest positive integer in Template:Mvar: the remainder Template:Mvar can therefore not be in Template:Mvar, making Template:Mvar necessarily 0. This implies that Template:Mvar is a divisor of Template:Mvar. Similarly Template:Mvar is also a divisor of Template:Mvar, and therefore Template:Mvar is a common divisor of Template:Mvar and Template:Mvar.

Now, let Template:Mvar be any common divisor of Template:Mvar and Template:Mvar; that is, there exist Template:Mvar and Template:Mvar such that a = cu and b = cv. One has thus $$\begin{array}{rl}d& =as+bt\\ & =cus+cvt\\ & =c(us+vt).\end{array}$$ That is, Template:Mvar is a divisor of Template:Mvar. Since d > 0, this implies c ≤ d.

Corollaries

Writing any integer as a linear combination

An immediate corollary of Bézout's identity is that any integer Template:Mvar can be written as a linear combination of any two coprime integers. Indeed, if Template:Mvar and Template:Mvar are coprime, then Bézout's identity guarantees the existence of integers Template:Mvar and Template:Mvar such that ax + by = 1. Multiplying both sides by Template:Mvar gives $a(xn)+b(yn)=n$.

Generalizations

For three or more integers

Bézout's identity can be extended to more than two integers: if $$\gcd (a_1,a_2,\dots ,a_n)=d$$ then there are integers $x_1,x_2,\dots ,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 does not always hold for polynomials with coefficients in a ring. For example, when working in the polynomial ring with integer coefficients: the greatest common divisor of 2x and x² is x, but there are no integer-coefficient polynomials $p(x)$ and $q(x)$ satisfying $2xp(x)+x^{2}q(x)=x$.

However, Bézout's identity works for univariate polynomials with coefficients in a field, exactly as for the original case of 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 the fundamental theorem of algebra imply the following result: Template:Block indent

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 Template:Mvar and Template:Mvar are elements of R, and Template:Mvar is a greatest common divisor of Template:Mvar and Template:Mvar, 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 and attribution

The French mathematician Étienne Bézout (1730–1783) proved this identity for polynomials. The statement for integers can be found already in the work of an earlier French mathematician, Claude Gaspard Bachet de Méziriac (1581–1638). Andrew Granville traced the association of Bézout's name with the identity to Bourbaki, arguing that it is a misattribution since the identity is implicit in Euclid's Elements.

See also

• Template:Annotated link, an analogue of Bézout's identity for homogeneous polynomials in three indeterminates
• Template:Annotated link
• Template:Annotated link
• Template:Annotated link

External links

• Online calculator for Bézout's identity