Algoritmo de Euclides extendido
Calcula el MCD y los coeficientes de Bézout que cumplen ax+by=MCD(a,b).
Algoritmo de Euclides extendido: magnitud y alcance
Calcula el máximo común divisor y coeficientes de Bézout.
Euclides extendido conserva, además de los restos, combinaciones lineales de a y b hasta alcanzar el máximo común divisor.
Las divisiones son 30=1·18+12, 18=1·12+6 y 12=2·6. Sustituir hacia atrás da 6=18−(30−18)=2·18−30, exactamente los coeficientes mostrados.
Fórmula ax+by=mcd(a,b).
Retroceder las divisiones produce coeficientes de Bézout x,y con ax+by=mcd(a,b).
Campos visibles: Dos enteros a b. ax+by=mcd(a,b).
Ejemplo numérico: MCD = 6
Dos enteros a b: «30 18».
Para 30 y 18, 6=−1·30+2·18, así que el mcd es 6 y los coeficientes son −1 y 2.
Resultado completo: MCD = 6; Coeficiente x = -1; Coeficiente y = 2.
El último resto no nulo de Euclides es el mcd porque divide los restos anteriores al reconstruir las ecuaciones. Los coeficientes de Bézout certifican el resultado: cualquiera puede multiplicar 30 por −1 y 18 por 2 para recuperar 6. Esta identidad aporta más información que listar únicamente el máximo divisor común.
Lectura matemática de MCD, Coeficiente x, Coeficiente y
Los coeficientes no son únicos: sumar b/g a x y restar a/g a y conserva la identidad.
Si el mcd es 1, x actúa como inverso de a módulo b: ax+by=1 implica ax≡1 mod b. Por eso el algoritmo sirve para congruencias y criptografía además de calcular el mcd.
Restricciones propias de algoritmo de Euclides extendido
Las entradas son enteras y sus signos influyen en los coeficientes; el mcd se presenta no negativo.
Con una entrada cero, la identidad sigue teniendo casos definidos, pero ambos valores cero no proporcionan un máximo común divisor positivo ni coeficientes informativos bajo todas las convenciones.
Fuentes y referencias
Continúa con estas herramientas
Preguntas frecuentes
¿Qué supuesto impide extender este resultado a otro caso?
El signo de los coeficientes depende de los signos de entrada.
¿Qué representan los controles «Dos enteros a b»?
Devuelve mcd y coeficientes que cumplen la identidad de Bézout. Cada valor ocupa la posición indicada por la fórmula ax+by=mcd(a,b).
¿Cómo se llega a MCD = 6?
Con Dos enteros a b: «30 18», se sustituyen las magnitudes en ax+by=mcd(a,b). El cálculo da MCD = 6; Coeficiente x = -1; Coeficiente y = 2.
¿Qué entradas quedan fuera del dominio de algoritmo de Euclides extendido?
Devuelve mcd y coeficientes que cumplen la identidad de Bézout. Los cocientes se calculan con enteros. El signo de los coeficientes depende de los signos de entrada.
¿Qué indica el resultado dentro de este modelo?
Los cocientes se calculan con enteros.
Herramienta de OCC Tools