Identidad de Bézout
La identidad de Bézout o Lema de Bézout es un teorema elemental de teorías de números el cual 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:
.
Dicho de otra manera, para todo a y b, existen un x y un y tales que:
.
Donde d es el máximo común divisor de (a,b).
Más aún, 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:
.
Para todo a, b, x, y y k. Así dando a k cualquier valor entero y definiendo:
,
se tiene que:
.
Demostración
La demostración clásica inicia considerando el conjunto de las combinaciones lineales enteras ax + by de los enteros a, b dados, y elige el mínimo elemento positivo, digamos d, de ese conjunto. Procede entonces a demostrar que ese elemento mínimo es el MCD(a,b). La demostración de esto se basa en el algoritmo de la división: primero se demuestra que d divide a ambos números y, como d es del conjunto S, se llega a que cualquier otro divisor común de a y b tiene que dividir a d; de aquí que d sea el MCD(a,b) .
Sea d el mínimo positivo de S={ax + by|x,y∈Z}. Consideremos ahora la división d|a. Por el algoritmo de la división deben existir q y r enteros, con 0 ≤ r y menor que d, tales que a=qd + r . Es decir, r=a - qd. Pero, como a y d son de S , r es también de S. Y se tiene que concluir que r=0 , pues d es el mínimo positivo. Esto demuestra que d divide a a. De manera similar, d divide a b .
Finalmente, sea d' cualquier otro divisor común de a y b. Debería ser claro que d' divide a cada uno de los elementos de S. En particular divide a d. Por tanto, d'≤d . Es decir, d es el MCD(a,b)=ax0+by0, para algunos enteros x0,y0.
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:
.
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
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 es un DIP, y y son elementos de , y es el máximo común divisor de y entonces existen e elementos de tales que .
Véase también
Enlaces externos
- (en inglés) Online calculator of Bézout's identity.
- Sencilla calculadora en línea de la identidad de Bézout.