Bézout's identity

{{Short description|Relating two numbers and their greatest common divisor}}

{{About|Bézout's theorem in arithmetic|Bézout's theorem in algebraic geometry|Bézout's theorem}}

In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout who proved it for polynomials, is the following theorem:

{{math_theorem

| name = Bézout's identity

| math_statement = Let {{math|a}} and {{math|b}} be integers with greatest common divisor {{math|d}}. Then there exist integers {{math|x}} and {{math|y}} such that {{math|1=ax + by = d}}. Moreover, the integers of the form {{math|az + bt}} are exactly the multiples of {{math|d}}.

}}

Here the greatest common divisor of {{math|0}} and {{math|0}} is taken to be {{math|0}}. The integers {{math|x}} and {{math|y}} are called Bézout coefficients for {{math|(a, b)}}; 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 {{math|{{abs|x}} ≤ {{abs|b/d}}}} and {{math|{{abs|y}} ≤ {{abs|a/d}}}}; equality occurs only if one of {{math|a}} and {{math|b}} 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 {{math|1=3 = 15 × (−9) + 69 × 2}}, 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 {{math|a}} and {{math|b}} are not both zero and one pair of Bézout coefficients {{math|(x, y)}} has been computed (for example, using the extended Euclidean algorithm), all pairs can be represented in the form

$\left(x-k\frac{b}{d},\ y+k\frac{a}{d}\right),$

where {{math|k}} is an arbitrary integer, {{math|d}} is the greatest common divisor of {{math|a}} and {{math|b}}, and the fractions simplify to integers.

If {{mvar|a}} and {{mvar|b}} 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 |\quad \text{and}\quad |y| < \left |\frac{a}{d}\right |.$ If {{mvar|a}} and {{mvar|b}} 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 {{math|a > 0}} is a divisor of {{mvar|b}} (including the case $b=0$ ), then one pair of Bézout coefficients is {{math|(1, 0)}}.

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

The two pairs of small Bézout's coefficients are obtained from the given one {{math|(x, y)}} by choosing for {{mvar|k}} in the above formula either of the two integers next to {{math|{{sfrac|x|b/d}}}}.

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

= Example =

Let {{math|1=a = 12}} and {{math|1=b = 42}}, then {{math|1=gcd (12, 42) = 6}}. 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 {{math|1=(x, y) = (18, −5)}} is the original pair of Bézout coefficients, then {{math|{{sfrac|18|42/6}} ∈ [2, 3]}} yields the minimal pairs via {{math|1=k = 2}}, respectively {{math|1=k = 3}}; that is, {{math|1=(18 − 2 ⋅ 7, −5 + 2 ⋅ 2) = (4, −1)}}, and {{math|1=(18 − 3 ⋅ 7, −5 + 3 ⋅ 2) = (−3, 1)}}.

Existence proof

Given any nonzero integers {{mvar|a}} and {{mvar|b}}, let {{math|1=S = {{mset|ax + by | x, y ∈ Z and ax + by > 0}}}}. The set {{mvar|S}} is nonempty since it contains either {{mvar|a}} or {{math|–a}} (with {{math|1=x = ±1}} and {{math|1=y = 0}}). Since {{mvar|S}} is a nonempty set of positive integers, it has a minimum element {{math|1=d = as + bt}}, by the well-ordering principle. To prove that {{mvar|d}} is the greatest common divisor of {{mvar|a}} and {{mvar|b}}, it must be proven that {{mvar|d}} is a common divisor of {{mvar|a}} and {{mvar|b}}, and that for any other common divisor {{mvar|c}}, one has {{math|c ≤ d}}.

The Euclidean division of {{mvar|a}} by {{mvar|d}} may be written as

$a=dq+r\quad\text{with}\quad 0\le r$

The remainder {{mvar|r}} is in {{math|S ∪ {{mset|0}}}}, because

$\begin{align}
r & = a - qd \\
& = a - q(as+bt)\\
& = a(1-qs) - bqt.
\end{align}$

Thus {{mvar|r}} is of the form {{math|ax + by}}, and hence {{math|r ∈ S ∪ {{mset|0}}}}. However, {{math|0 ≤ r < d}}, and {{mvar|d}} is the smallest positive integer in {{mvar|S}}: the remainder {{mvar|r}} can therefore not be in {{mvar|S}}, making {{mvar|r}} necessarily 0. This implies that {{mvar|d}} is a divisor of {{mvar|a}}. Similarly {{mvar|d}} is also a divisor of {{mvar|b}}, and therefore {{mvar|d}} is a common divisor of {{mvar|a}} and {{mvar|b}}.

Now, let {{mvar|c}} be any common divisor of {{mvar|a}} and {{mvar|b}}; that is, there exist {{mvar|u}} and {{mvar|v}} such that {{math|1=a = cu}} and {{math|1=b = cv}}. One has thus

$\begin{align}
d&=as + bt\\
& =cus+cvt\\
&=c(us+vt).
\end{align}$

That is, {{mvar|c}} is a divisor of {{mvar|d}}. Since {{math|d > 0}}, this implies {{math|c ≤ d}}.

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:

{{math|d}} is the smallest positive integer of this form
every number of this form is a multiple of {{math|d}}

= For polynomials =

{{main|Polynomial greatest common divisor#Bézout's identity and extended GCD algorithm}}

Bézout's identity does not always hold for polynomials. For example, when working in the polynomial ring of integers: the greatest common divisor of {{math|2x}} and {{math|x²}} is x, but there does not exist any integer-coefficient polynomials {{math|p}} and {{math|q}} satisfying {{math|1=2xp + x²q = x}}.

However, 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:

{{block indent|em=1.5|text=For univariate polynomials {{mvar|f}} and {{mvar|g}} with coefficients in a field, there exist polynomials {{math|a}} and {{math|b}} such that {{math|1=af + bg = 1}} if and only if {{mvar|f}} and {{mvar|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 {{math|R}} is a PID, and {{mvar|a}} and {{mvar|b}} are elements of {{math|R}}, and {{mvar|d}} is a greatest common divisor of {{mvar|a}} and {{mvar|b}},

then there are elements {{math|x}} and {{math|y}} in {{math|R}} such that {{math|1=ax + by = d}}. The reason is that the ideal {{math|Ra + Rb}} is principal and equal to {{math|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.{{cite book |author=Bézout, É.|author-link=Étienne Bézout|url=https://archive.org/details/bub_gb_RDEVAAAAQAAJ |title=Théorie générale des équations algébriques |place=Paris, France |publisher=Ph.-D. Pierres |year=1779}} The statement for integers can be found already in the work of an earlier French mathematician, Claude Gaspard Bachet de Méziriac (1581–1638).

{{cite book | last=Tignol | first=Jean-Pierre | author-link=Jean-Pierre Tignol | title=Galois' Theory of Algebraic Equations | publisher=World Scientific| location=Singapore | year=2001 | isbn=981-02-4541-6}}{{cite book|author=Claude Gaspard Bachet (sieur de Méziriac)|title=Problèmes plaisants & délectables qui se font par les nombres|edition=2nd|location=Lyons, France|publisher=Pierre Rigaud & Associates|year=1624|pages= 18–33|url=http://www.bsb-muenchen-digital.de/~web/web1008/bsb10081407/images/index.html?digID=bsb10081407&pimage=38&v=100&nav=0&l=de}} 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, {{math|1=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: {{cite journal|date=February 2009|author=Maarten Bullynck |title=Modular arithmetic before C.F. Gauss: Systematizations and discussions on remainder problems in 18th-century Germany |doi=10.1016/j.hm.2008.08.009|journal=Historia Mathematica|volume=36|issue=1|pages=48–72| url=http://hal.inria.fr/docs/00/66/32/92/PDF/Gauss_Modular_Oct2008.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://hal.inria.fr/docs/00/66/32/92/PDF/Gauss_Modular_Oct2008.pdf |archive-date=2022-10-09 |url-status=live| doi-access=free}}

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.{{cite arXiv |last=Granville |first=Andrew |date=2024 |title=It is not "Bézout's identity" |arxiv=2406.15642 |class=math.HO}}

Notes

External links

[http://wims.unice.fr/wims/wims.cgi?module=tool/arithmetic/bezout.en Online calculator] for Bézout's identity.
{{mathworld|urlname=BezoutsIdentity|title=Bézout's Identity}}

Category:Articles containing proofs

Category:Diophantine equations

Category:Lemmas in number theory