dimecres, 4 abril de 2012

Máximo común divisor e identidad de Bézout

Enunciado: Calcular el m.c.d. del par (267, 112). Calcular también el m.c.d. del par  (500, 11312) expresándolo según la identidad de Bézout.

Solución:  Usaremos el algoritmo de Euclides; con una hoja de cálculo, vemos que el valor devuelto para (267, 112) es 1:
Por tanto el mcd = 1. También lo podemos hacer descomponiendo los números en factores primos:
En la descomposición puede ser útil una tabla de números primos; la siguiente lista los menores que 200:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199.

Para encontrar el mcd de dos números tomamos los factores comunes elevados a la menor potencia, el producto de los cuales será el mcd; en este caso no ha factores comunes, luego mcd = 1.

Para el par (500, 11312) procedemos igual, pero además no piden expresar el mcd según la identidad de Bézout o Lema de Bézout, que  enuncia que si a y b son números enteros con máximo común divisor d, entonces existen enteros x e y tales que ax + by = d. El algoritmo extendido de Euclides permite encontrar los valores x, y: la tabla del algoritmo de Euclides se amplia añadiendo el cociente entero de cada par de números:

Esta tabla expresa las igualdades:
Ahora hacemos back-tracking para expresar el mcd = 4 como combinación lineal de 11312 y 500, empezando por la última igualdad, la [6], despejando del lado derecho los residuos y simplificando, y seguimos retrocediendo despejando el residuo usando la [5], y así sucesivamente hasta llegar a la [1]:
 Nos queda que mcd(11312,500) = 500x+1132y = 500·181-11312 = 4.



 








Cap comentari:

Publica un comentari a l'entrada