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

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

ax + by = {\rm gcd} (a, b)

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.

PLANETCALC, Algoritmo de Euclides extendido

Algoritmo de Euclides extendido

Máximo Común Divisor
 
Coeficiente para número entero mayor
 
Coeficiente para número entero menor
 

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 (x_1,y_1) para el par (b\%a,a), como por ejemplo:

 (b \% a)x_1 + ay_1 = g,

y necesitamos calcular los coeficientes para el par (a,b), como por ejemplo:

 ax + by = g

Primero, reemplazamos b\%a con:

b\%a = b - \left\lfloor \frac{b}{a} \right\rfloor a, donde

\left\lfloor \frac{b}{a} \right\rfloor - cociente de la división de enteros de b a a,

y lo usamos como sustituto en:

g = (b \% a) x_1 + a  y_1 = \left( b -\left\lfloor \frac{b}{a} \right\rfloor a\right) x_1 + ay_1

Luego, después de reagruparnos obtenemos:

g = bx_1 + a \left( y_1 - \left\lfloor \frac{b}{a} \right\rfloor x_1\right)

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

x = y_1 - \left\lfloor \frac{b}{a} \right\rfloor x_1y = x_1

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.

Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Algoritmo de Euclides Extendido

Comentarios