Bézout's identity

ImprimirCitar

The Bézout identity or Bézout's lemma is an elementary theorem of number theory which states that if a and b are non-zero integers with greatest common divisor d, then there exist integers x and y such that:

${displaystyle ax+by=d,}$ .

Put another way, for every a and b, there exists an x and an y such that:

${displaystyle ax+by=MCD(a,b),}$ .

Where d is the greatest common divisor of (a,b).

Furthermore, GCD(a,b) is the least positive element of the set of integer linear combinations {ax + by}.

The identity was named in honor of the French mathematician Étienne Bézout (1730-1783).

Algorithm

The numbers x and y of the Bézout identity can be determined by Euclid's extended algorithm, but they are not determined uniquely, since:

${displaystyle a(x-kb)+b(y+ka)=ax-kba+by+kba=ax+by,}$ .

For all a, b, x, y and k. Thus giving k any integer value and defining:

${displaystyle x^{prime }=x-kbqquad y^{prime }=y+ka,}$ ,

you have to:

${displaystyle ax^{prime }+by^{prime }=ax+by,}$ .

Demo

The classical proof starts by considering the set of integer linear combinations ax + by of the given integers a, b, and chooses the smallest positive element, say d, of that set. It then proceeds to show that this minimum element is the GCD(a,b). The proof of this is based on the division algorithm: first it is shown that d divides both numbers and, since d is from the set S, it turns out that any other common divisor of a and b has to divide d; hence d is the GCD(a,b).

Let d be the positive minimum of S={ax + by|x,y∈Z}. Let us now consider the division d|a. By the division algorithm there must exist q and r integers, with 0 ≤ r and less than d, such that a=qd + r. That is, r=a - qd. But, since a and d are from S, r is also from S. And we have to conclude that r=0 since d is the positive minimum. This shows that d splits a. Similarly, d splits b.

Finally, let d' be any other common divisor of a and b. It should be clear that d' divides each of the elements of S. In particular it splits d. Therefore, d'≤d. That is, d is the GCD(a,b)=ax0+by0, for some integers x0,y0.

Euclid's algorithm

We can associate this theorem with Euclid's algorithm, which is a procedure to calculate the g.c.d. of two numbers.

The steps are:

The largest number is divided among the minor.
Yes:

1. The division is exact, the divisor is the g.c.d.

2. The division is not exact: we divide the divisor by the remainder obtained and continue in this way until an exact division is obtained, the last divisor being the g.c.d.

Euclid's algorithm is an old and efficient method for calculating the greatest common divisor (GCD).

It was originally described by Euclid in his work Elements. The extended Euclid algorithm is a slight modification that also allows the greatest common divisor to be expressed as a linear combination.

This algorithm has applications in various areas such as algebra, number theory and computer science among others. With some slight modifications it is usually used in electronic computers due to its great efficiency.

The extended Euclid algorithm allows, in addition to finding a g.c.d. of two integers and express it as the smallest linear combination of those numbers, that is, find integers. This also generalizes to any Euclidean domain.

There are several ways to explain the extended Euclid algorithm, one of the most common is as follows:

Use the traditional Euclid algorithm. In each step, instead of "a divided by b is q and the remainder r" write the equation a = bq + r.

The remainder of each equation is cleared, the remainder of the last equation is substituted in the penultimate equation, and the penultimate in the antepenultimate equation, and so on until reaching the first equation, and in every step each remainder is expressed as a linear combination.

Given two natural numbers, the dividend, m, and the divisor, d, (which must be greater than zero), we call the quotient, q the largest of the numbers that multiplied by the divisor is less than or equal to the dividend.

We call the remainder, r, the difference between the dividend and the product of the quotient and the divisor.

Example:

72|16 → 16|8 → m.c.m. (72,16) = 8

8 4 0 2

Example

The non-uniqueness can be illustrated with an example:

${displaystyle 12x+42y=6,}$ .

The greatest common factor of 12 and 42 is 6. A solution of the previous expression is:

12·(-3) + 42·1 = 6

But there are others such as:

12·4 + 42·(-1) = 6

12·11 + 42·(-3) = 6

12·18 + 42·(-5) = 6

etc.

The set of solutions can be expressed as:

x = −3 + 7·k

and = 1 − 2·k

for any integer value of k.

Examples

Given two natural numbers m and n, coprime to each other, there exist two integers a and b such that

a • m + b • n = 1

This identity is easily demonstrated using, for example, Euclid's algorithm: it is about dividing m integer by n (suppose, for example, that m>n), and repeating this division now between n and the remainder obtained previously, until reaching remainder 1. This is possible exactly if the numbers m and n are coprime to each other. Going back the steps taken we obtain the sought identity of Bezout.

Let's do it with a concrete example:

Let's take m=30 and n=13. So

30=13•2+4

13=4•3+1

Therefore

1=13 + 4•(-3)=13+ (30+13•(-2))•(-3)=(-3)•30+7•13

Then the values of a and b sought are -3 and 7 respectively.

Given two numbers (502,110) find the pair x,y:

By Euclid's Algorithm we express the division as a linear combination.

502 = 110(4) + 62 → 62 = 502(1) - 110(4) → 62 = (502(1) + 110(-4)

110 = 62(1) + 48 → 48 = 110(1) - 62(1) → 48 = 110(1) + 62(-1)

62 = 48(1) + 14 → 14 = 62(1) - 48(1) → 14 = 62(1) + 48(-1)

48 = 14(3) + 6 → 6 = 48(1) - 14(3) → 6 = 48(1) + 14(-3)

14 = 6(2) + 2 → 2 = 14(1) - 6(2) → 2 = 14(1) + 6(-2)

Generalizations

Bézout's identity not only works on the entire ring, but it is also valid in any other major ideal domain (DIP). I mean, yeah. $R$ It's a DIP, and $a$ and $b$ are elements of $R$ and $d$ is the maximum common divider $a$ and $b$ then they exist. $x$ e $y$ elements $R$ such that ${displaystyle ax+by=d,}$ .

Contenido relacionado

Más resultados...