Algoritmo de Euclides Extendido

Este sitio ya tiene El máximo común divisor de dos números enteros, que utiliza el algoritmo de Euclides. Como resultado (para mí), existe un algoritmo de Euclides Extendido. Este algoritmo calcula, además del máximo común divisor de los números enteros a y b, los coeficientes de la identidad de Bézout, que son los números enteros x e y tal que

Entonces permite calcular los cocientes de a y b por su máximo común divisor.

Puede ver la siguiente calculadora, y la teoría, como de costumbre, abajo de la calculadora.

Algoritmo de Euclides extendido

Primer número entero

Segundo número entero

Calcular

Máximo Común Divisor

 

Coeficiente para número entero mayor

 

Coeficiente para número entero menor

 

 Enlace  Guardar  Widget

El algoritmo extendido usa la recursión y calcula los coeficientes en su retroceso. Las fórmulas para los cálculos se pueden obtener a partir de las siguientes consideraciones:

Háganos saber los coeficientes para el par , como por ejemplo:

,

y necesitamos calcular los coeficientes para el par , como por ejemplo:

Primero, reemplazamos con:

, donde

- cociente de la división de enteros de b a a,

y lo usamos como sustituto en:

Luego, después de reagruparnos obtenemos:

Al comparar esto con la ecuación inicial podemos expresar x e y:

El inicio del retroceso de recursión es el final del algoritmo de Euclides, cuando a = 0 y GCD = b, por lo que primero x e y son 0 y 1 respectivamente. Los coeficientes adicionales se calculan utilizando las fórmulas anteriores.