Identidad de Bézout

La identidad de Bézout o Lema de Bézout es un teorema elemental de teorías de números que enuncia que si $a$ y $b$ son números enteros diferentes de cero con máximo común divisor $d$ , entonces existen enteros $x$ e $y$ tales que:

$ax+by=d\,$ .

Dicho de otra manera, para todo $a$ y $b$ , existen un $x$ y un $y$ tales que:

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

Más aún, $\operatorname {MCD} (a,b)$ es el elemento mínimo positivo del conjunto de combinaciones lineales enteras $\{ax+by\}$ .

La identidad fue nombrada en honor del matemático francés Étienne Bézout (1730-1783).

Algoritmo

Los números $x$ e $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:

$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 $d=\operatorname {MCD} (a,b)$ para todo $a,b,x,y$ y $k$ . Así dando a $k$ cualquier valor entero y definiendo:

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

se tiene que:

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

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

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

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

Demostración

La demostración clásica inicia considerando el conjunto de las combinaciones lineales enteras $ax+by$ de los enteros $a,b$ dados: $S=\{ax+by:x,y\in \mathbb {Z} {\text{ y }}ax+by>0\}$ . El conjunto $S$ es no vacío, pues contiene a $a$ o a $-a$ en función del signo de $a$ (para $x=\pm 1$ , $y=0$ ). Como $S$ es un conjunto no vacío de enteros positivos, por el principio de buena ordenación, tiene un mínimo.Sea pues $d$ el mínimo elemento (positivo) de ese conjunto. Como $d\in S$ , tenemos que es de la forma $d=as+bt$ , con $s,t\in \mathbb {Z}$ . Veremos ahora que, de hecho, $d=\operatorname {MCD} (a,b)$ . Para demostrarlo, debemos ver que $d$ divide a $a$ y a $b$ y que para cualquier otro divisor común $c$ , se tiene que $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 $a$ entre $d$ . Tenemos que existen $q,r\in \mathbb {Z}$ (el cociente y el resto, respectivamente) tales que $a=qd+r,\quad 0\leq r<d$ . Observamos que $r\in S\cup \{0\}$ , pues $0\leq r=a-qd=a-q(as+bt)=a(1-qs)-b(qt)$ y $1-qs,qt\in \mathbb {Z}$ , pues $q,s,t\in \mathbb {Z}$ . Sin embargo, $0\leq r<d$ y $d$ es el entero positivo más pequeño de $S$ , por lo que $r\notin S$ y, necesariamente, $r=0$ . Esto demuestra que $d$ divide a $a$ , pues $r$ era el resto de la división. De manera similar, se demuestra que $d$ divide a $b$ .

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

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

Algoritmo de Euclides

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:

Se divide el número mayor entre el menor.
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

Ejemplo

Se puede ilustrar la no unicidad con un ejemplo:

$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.

Ejemplos

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)

Generalizaciones

Para más de dos enteros

La identidad de Bézout se puede extender a más de dos enteros: si

$\operatorname {MCD} (a_{1},a_{2},\dots ,a_{n})=d$ ,

entonces existen enteros $x_{1},\dots ,x_{n}$ tales que

$d=a_{1}x_{1}+a_{2}x_{2}+\dots +a_{n}x_{n}$ .

Se tienen las siguientes propiedades:

$d$ es el entero más pequeño de esta forma.
Cualquier otro entero de esta forma es múltiplo de $d$ .

Para polinomios

Artículo principal: Máximo común divisor polinómico

La identidad de Bézout no siempre es cierta para polinomios. Por ejemplo, en el anillo polinómico de los enteros: el máximo común divisor de $x^{2}$ y $2x$ es $x$ , pero no existen polinomios enteros $pq\in \mathbb {Z} [x]$ tales que $x^{2}p+2xq=x$ .

Sin embargo, la identidad de Bézout sí que funciona para polinomios en una variable sobre un cuerpo de la misma forma en que lo hace para los enteros. En particular, los coeficientes de Bézout y el máximo común divisor se pueden calcular mediante el algoritmo de Euclides extendido.

Como las raíces comunes de dos polinomios son las raíces de su máximo común divisor, la identidad de Bézout y el teorema fundamental del álgebra implican el siguiente resultado:

Para polinomios en una variable $p$ y $q$ con coeficientes en un cuerpo, existen polinomios $a$ y $b$ tales que $ap+bq=1$ si y sólo si $p$ y $q$ no tienen ninguna raíz en común en ningún cuerpo algebraicamente cerrado (habitualmente el cuerpo de los complejos).

La generalización de este teorema a cualquier número de polinomios y variables es el teorema de los ceros de Hilbert.

Para dominios de ideales principales

La identidad de Bézout no sólo funciona en el anillo de los enteros, sino que también es válido en cualquier otro dominio de ideales principales (DIP). Es decir, si $R$ es un DIP, y $a$ y $b$ son elementos de $R$ , y $d$ es el máximo común divisor de $a$ y $b$ entonces existen $x$ e $y$ elementos de $R$ tales que $ax+by=d\,$ .

Historia

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.

Véase también

Ecuación diofántica lineal

Enlaces externos

Datos: Q513028