Identidad de Bézout

Los números ${\displaystyle x}$ e ${\displaystyle y}$ de la identidad de Bézout pueden determinarse mediante el algoritmo extendido de Euclides, pero no se determinan de forma unívoca, ya que:

${\displaystyle a\left(x-k{\frac {b}{d}}\right)+b\left(y+k{\frac {a}{d}}\right)=ax-k{\frac {ab}{d}}+by+k{\frac {ab}{d}}=ax+by\,}$

con ${\displaystyle d=\operatorname {MCD} (a,b)}$ para todo ${\displaystyle a,b,x,y}$ y ${\displaystyle k}$. Así dando a ${\displaystyle k}$ cualquier valor entero y definiendo:

${\displaystyle x^{\prime }=x-kb\qquad y^{\prime }=y+ka\,}$,

se tiene que:

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

De hecho, el conjunto de todas las soluciones ${\displaystyle (x,y)}$ se puede construir como:

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

con ${\displaystyle d=\operatorname {MCD} (a,b)}$ y ${\displaystyle (x,y)}$ una solución particular.

La demostración clásica inicia considerando el conjunto de las combinaciones lineales enteras ${\displaystyle ax+by}$ de los enteros ${\displaystyle a,b}$ dados: ${\displaystyle S=\{ax+by:x,y\in \mathbb {Z} {\text{ y }}ax+by>0\}}$. El conjunto ${\displaystyle S}$ es no vacío, pues contiene a ${\displaystyle a}$ o a ${\displaystyle -a}$ en función del signo de ${\displaystyle a}$ (para ${\displaystyle x=\pm 1}$, ${\displaystyle y=0}$). Como ${\displaystyle S}$ es un conjunto no vacío de enteros positivos, por el principio de buena ordenación, tiene un mínimo.Sea pues ${\displaystyle d}$ el mínimo elemento (positivo) de ese conjunto. Como ${\displaystyle d\in S}$, tenemos que es de la forma ${\displaystyle d=as+bt}$, con ${\displaystyle s,t\in \mathbb {Z} }$. Veremos ahora que, de hecho, ${\displaystyle d=\operatorname {MCD} (a,b)}$. Para demostrarlo, debemos ver que ${\displaystyle d}$ divide a ${\displaystyle a}$ y a ${\displaystyle b}$ y que para cualquier otro divisor común ${\displaystyle c}$, se tiene que ${\displaystyle c\leq d}$.

La demostración de esto se basa en el algoritmo de la división euclídea.

Consideremos la división euclídea de ${\displaystyle a}$ entre ${\displaystyle d}$. Tenemos que existen ${\displaystyle q,r\in \mathbb {Z} }$ (el cociente y el resto, respectivamente) tales que ${\displaystyle a=qd+r,\quad 0\leq r<d}$. Observamos que ${\displaystyle r\in S\cup \{0\}}$, pues ${\displaystyle 0\leq r=a-qd=a-q(as+bt)=a(1-qs)-b(qt)}$ y ${\displaystyle 1-qs,qt\in \mathbb {Z} }$, pues ${\displaystyle q,s,t\in \mathbb {Z} }$. Sin embargo, ${\displaystyle 0\leq r<d}$ y ${\displaystyle d}$ es el entero positivo más pequeño de ${\displaystyle S}$, por lo que ${\displaystyle r\notin S}$ y, necesariamente, ${\displaystyle r=0}$. Esto demuestra que ${\displaystyle d}$ divide a ${\displaystyle a}$, pues ${\displaystyle r}$ era el resto de la divisón. De manera similar, se demuestra que ${\displaystyle d}$ divide a ${\displaystyle b}$.

Finalmente, sea ${\displaystyle c}$ cualquier otro divisor común de ${\displaystyle a}$ y ${\displaystyle b}$, esto es, existen ${\displaystyle u,v\in \mathbb {Z} }$ tales que ${\displaystyle a=cu,b=cv}$. Se tiene entonces que ${\displaystyle d=as+bt=cus+cvt=c(us+vt)}$, es decir, ${\displaystyle c}$ divide a ${\displaystyle d}$, pero como ${\displaystyle d>0}$ por ser un elemento de ${\displaystyle S}$, se tiene que ${\displaystyle c\leq d}$.

Así, se concluye que ${\displaystyle d=\operatorname {MCD} (a,b)}$, de forma que ${\displaystyle \exists x,y\in \mathbb {Z} }$ tales que ${\displaystyle \operatorname {MCD} (a,b)=ax+by}$. ${\displaystyle \quad \square }$

A este teorema lo podemos asociar con el algoritmo de Euclides, el cual es un procedimiento para poder calcular el m.c.d. de dos números.

Los pasos son:

1. Se divide el número mayor entre el menor.
2. Si:

1. La división es exacta, el divisor es el m.c.d.

2. La división no es exacta: dividimos el divisor entre el resto obtenido y se continúa de esta forma hasta obtener una división exacta, siendo el último divisor el m.c.d.

El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común divisor (MCD).

Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal.

Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación entre otras. Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido a su gran eficiencia.

El algoritmo de Euclides extendido permite, además de encontrar un m.c.d. de dos números enteros y expresarlo como la mínima combinación lineal de esos números, es decir, encontrar números enteros. Esto se generaliza también hacia cualquier dominio euclidiano.

Existen varias maneras de explicar el algoritmo de Euclides extendido, una de las más comunes consiste en la siguiente:

Usar el algoritmo tradicional de Euclides. En cada paso, en lugar de "a dividido entre b es q y de resto r" se escribe la ecuación a = bq + r.

Se despeja el resto de cada ecuación, se sustituye el resto de la última ecuación en la penúltima, y la penúltima en la antepenúltima y así sucesivamente hasta llegar a la primera ecuación, y en todo paso se expresa cada resto como combinación lineal.

Dados dos números naturales, el dividendo, m, y el divisor, d, (que debe ser mayor que cero), llamamos cociente, q al mayor de los números que multiplicado por el divisor es menor o igual que el dividendo.

Llamamos resto, r, a la diferencia entre el dividendo y el producto del cociente y el divisor.

Ejemplo:

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

8 4 0 2

Se puede ilustrar la no unicidad con un ejemplo:

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

El máximo común divisor de 12 y 42 es 6. Una solución de la expresión anterior es:

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

Pero hay otras tales como:

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

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

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

etc.

El conjunto de soluciones se puede expresar como:

x = −3 + 7·k

y = 1 − 2·k

para cualquier valor entero de k.

Dados dos números naturales m y n, coprimos entre sí, existen dos números enteros a y b tales que

a • m + b • n = 1

Esta identidad se demuestra fácilmente usando por ejemplo el algoritmo de Euclides: se trata de hacer la división entera de m entre n (supongamos por ejemplo que m>n), e ir repitiendo esta división ahora entre n y el resto obtenido anteriormente, hasta llegar a resto 1. Esto es posible exactamente si los números m y n son coprimos entre sí. Volviendo para atrás los pasos dados obtenemos la identidad de Bezout buscada.

Vamos a hacerlo con un ejemplo concreto:

Tomemos m=30 y n=13. Entonces

30=13•2+4

13=4•3+1

Por lo tanto

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

Luego los valores de a y b buscados son -3 y 7 respectivamente.

Dados dos números (502,110) hallar el par x,y:

Mediante el Algoritmo de Euclides expresamos la división como una combinación lineal.

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)

El matemático francés Étienne Bézout (1730-1783) demostró esta identidad para polinomios. El mismo resultado para enteros ya se puede encontrar en los trabajos de un matemático francés anterior, Claude Gaspard Bachet de Méziriac.

• Ecuación diofántica lineal

• (en inglés) Online calculator of Bézout's identity.
• Sencilla calculadora en línea de la identidad de Bézout.