Английская Википедия: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 the following theorem: Шаблон:Math theorem

Here the greatest common divisor of Шаблон:Math and Шаблон:Math is taken to be Шаблон:Math. The integers Шаблон:Math and Шаблон:Math are called Bézout coefficients for Шаблон:Math; 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>|x|\le | b/d |</math> and <math>|y|\le | a/d |;</math> equality occurs only if one of Шаблон:Math and Шаблон:Math 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 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 and Шаблон:Math are not both zero and one pair of Bézout coefficients Шаблон:Math has been computed (for example, using the extended Euclidean algorithm), all pairs can be represented in the form <math display=block>\left(x-k\frac{b}{d},\ y+k\frac{a}{d}\right),</math> where Шаблон:Math is an arbitrary integer, Шаблон:Math is the greatest common divisor of Шаблон:Math and Шаблон:Math, and the fractions simplify to integers.

If Шаблон:Mvar and Шаблон:Mvar are both nonzero, then exactly two of these pairs of Bézout coefficients satisfy <math display="block"> |x| \le \left |\frac{b}{d}\right |\quad \text{and}\quad |y| \le \left |\frac{a}{d}\right |,</math> and equality may occur only if one of Шаблон:Math and Шаблон:Math divides the other.

This relies on a property of Euclidean division: given two non-zero integers Шаблон:Math and Шаблон:Math, if Шаблон:Mvar does not divide Шаблон:Mvar, there is exactly one pair Шаблон:Math such that <math>c = d q + r</math> and <math>0 < r < |d|,</math> and another one such that <math>c = d q + r</math> and <math>-|d| < r < 0.</math>

The two pairs of small Bézout's coefficients are obtained from the given one Шаблон:Math by choosing for Шаблон:Mvar in the above formula either of the two integers next to <math>\frac{x}{b/d}</math>.

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

Example

Let Шаблон:Math and Шаблон:Math, then Шаблон:Math. 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.

<math display="block">\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}</math>

If <math>(x, y) = (18, -5)</math> is the original pair of Bézout coefficients, then <math>\frac{18}{42/6} \in [2, 3]</math> yields the minimal pairs via Шаблон:Math, respectively Шаблон:Math; that is, Шаблон:Math, and Шаблон:Math.

Proof

Given any nonzero integers Шаблон:Mvar and Шаблон:Mvar, let <math>S = \{ax+by : x, y \in \Z \text{ and } ax+by > 0\}.</math> The set Шаблон:Mvar is nonempty since it contains either Шаблон:Mvar or Шаблон:Math (with <math>x = \pm 1</math> and <math>y = 0</math>). Since Шаблон:Mvar is a nonempty set of positive integers, it has a minimum element <math>d = as + bt</math>, by the well-ordering principle. To prove that Шаблон:Mvar is the greatest common divisor of Шаблон:Mvar and Шаблон:Mvar, it must be proven that Шаблон:Mvar is a common divisor of Шаблон:Mvar and Шаблон:Mvar, and that for any other common divisor Шаблон:Mvar, one has <math>c \leq d.</math>

The Euclidean division of Шаблон:Mvar by Шаблон:Mvar may be written as <math display="block">a=dq+r\quad\text{with}\quad 0\le r<d.</math> The remainder Шаблон:Mvar is in <math>S\cup \{0\}</math>, because <math display="block">\begin{align} r & = a - qd \\ & = a - q(as+bt)\\ & = a(1-qs) - bqt. \end{align}</math> Thus Шаблон:Mvar is of the form <math>ax+by</math>, and hence <math>r \in S \cup \{0\}.</math> However, <math>0 \leq r < d,</math> and Шаблон:Mvar is the smallest positive integer in Шаблон:Mvar: the remainder Шаблон:Mvar can therefore not be in Шаблон:Mvar, making Шаблон:Mvar necessarily 0. This implies that Шаблон:Mvar is a divisor of Шаблон:Mvar. Similarly Шаблон:Mvar is also a divisor of Шаблон:Mvar, and therefore Шаблон:Mvar is a common divisor of Шаблон:Mvar and Шаблон:Mvar.

Now, let Шаблон:Mvar be any common divisor of Шаблон:Mvar and Шаблон:Mvar; that is, there exist Шаблон:Mvar and Шаблон:Mvar such that <math>a = c u</math> and <math>b = c v.</math> One has thus <math display="block">\begin{align} d&=as + bt\\ & =cus+cvt\\ &=c(us+vt). \end{align} </math> That is, Шаблон:Mvar is a divisor of Шаблон:Mvar. Since <math>d > 0,</math> this implies <math>c \leq d.</math>

Generalizations

For three or more integers

Bézout's identity can be extended to more than two integers: if <math display="block">\gcd(a_1, a_2, \ldots, a_n) = d</math> then there are integers <math>x_1, x_2, \ldots, x_n</math> such that <math display="block">d = a_1 x_1 + a_2 x_2 + \cdots + a_n x_n</math> 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

Шаблон:Main 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 and Шаблон:Math is x, but there does not exist any integer-coefficient polynomials p and q satisfying Шаблон:Math.

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

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 is a PID, and Шаблон:Mvar and Шаблон:Mvar are elements of Шаблон:Math, and Шаблон:Mvar is a greatest common divisor of Шаблон:Mvar and Шаблон:Mvar, then there are elements Шаблон:Math and Шаблон:Math in Шаблон:Math such that <math>a x + b y = d.</math> The reason is that the ideal <math>R a + R b</math> is principal and equal to <math>R d.</math>

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. This statement for integers can be found already in the work of an earlier French mathematician, Claude Gaspard Bachet de Méziriac (1581–1638).

See also

• Шаблон:Annotated link, an analogue of Bézout's identity for homogeneous polynomials in three indeterminates
• Шаблон:Annotated link
• Шаблон:Annotated link
• Шаблон:Annotated link

External links

• Online calculator for Bézout's identity.
• Шаблон:Mathworld