Algoritmo de Euclides Extendido
Esta calculadora implementa el algoritmo de Euclides extendido, que calcula, además del máximo común divisor de números enteros a y b, los coeficientes de la identidad de Bézout
Esta página existe gracias a los esfuerzos de las siguientes personas:
 | Timur
|
 | Juan Manuel Gimenez
|
Este contenido está bajo licencia de Creative Commons Attribution/Share-Alike License 3.0 (Unported). Esto significa que puedes redistribuirlo o modificar su contenido en forma libre bajo las mismas condiciones de licencia y debes mantener la atribución del mismo al autor original de este trabajo colocando un hipervínculo en tu sitio web a este trabajo https://es.planetcalc.com/3298/. Así mismo, por favor no modifiques o alteres ninguna de las referencias al trabajo original (si hubiera alguna) que se encuentre en este contenido.
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
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.
Comentarios