World Library  
Flag as Inappropriate
Email this Article

Bézout's identity

Article Id: WHEBN0000004947
Reproduction Date:

Title: Bézout's identity  
Author: World Heritage Encyclopedia
Language: English
Subject: Euclidean algorithm, Euclidean domain, Coprime integers, Youla–Kucera parametrization, Étienne Bézout
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Bézout's identity

Bézout's identity (also called Bézout's lemma) is a theorem in the elementary theory of numbers: let a and b be nonzero integers and let d be their greatest common divisor. Then there exist integers x and y such that

ax+by=d

In addition,

  • the greatest common divisor d is the smallest positive integer that can be written as ax + by
  • every integer of the form ax + by is a multiple of the greatest common divisor d.

The integers x and y are called Bézout coefficients for (a, b); they are not unique. A pair of Bézout coefficients can be computed by the extended Euclidean algorithm. If both a and b are nonzero, the extended Euclidean algorithm produces one of the two pairs such that |x|<\left |\frac{b}{d}\right | and |y|<\left |\frac{a}{d}\right |.

Bézout's lemma is true in any principal ideal domain, but there are integral domains in which it is not true.

Structure of solutions

When one pair of Bézout coefficients (x, y) has been computed (e.g., using extended Euclidean algorithm), all pairs can be represented in the form

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

where k is an arbitrary integer and the fractions simplify to integers.

Among these pairs of Bézout coefficients, exactly two of them satisfy

|x| < \left |\frac{b}{\gcd(a,b)}\right |\quad \text{and}\quad |y| < \left |\frac{a}{\gcd(a,b)}\right |.

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

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

Example

Let a = 12 and b = 42, gcd (12, 42) = 6. Then we have the following Bézout's identities, 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}

Proof

Bézout's lemma is a consequence of the defining property of Euclidean division, namely: that dividing a positive integer a by a positive integer b yields a remainder greater than or equal to zero and strictly less than b. For given positive integers a and b there is a smallest positive integer d = as + bt among all those of the form ax + by with x and y integers. Now the remainder yielded by dividing either a or b by d is also of the form ax + by since it is obtained by subtracting a multiple of d = as + bt from a or b; so the remainder must be greater than or equal to zero and strictly smaller than d. This leaves 0 as only possibility for such a remainder, so d divides both a and b exactly.

If c is a common divisor of a and b, then c also divides d = as + bt. Since c divides d, c must be less than or equal to d, thus d is the greatest common divisor of a and b; the proof is complete.

This proof may be adapted for any Euclidean domain, and even for any principal ideal domain.

This proof does not provide a method for computing Bézout's coefficients. However, Bézout's lemma is also a corollary of the proof of the Extended Euclidean algorithm and this algorithm does provide an efficient method of computing these coefficients. This algorithm may also be extended to any Euclidean domain.

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:

  1. d is smallest positive integer of this form
  2. every number of this form is a multiple of d
  3. d is a greatest common divisor of a1, ..., an, meaning that every common divisor of a1, ..., an divides 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: 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.

History

French mathematician Étienne Bézout (1730–1783) proved this identity for polynomials.[1] However, this statement for integers can be found already in the work of another French mathematician, Claude Gaspard Bachet de Méziriac (1581–1638).[2][3][4]

See also

Notes

  1. ^
  2. ^
  3. ^ 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.
  4. ^ See also:

External links

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.