Algoritmo euclidiano estendido

Esta calculadora implementa o algoritmo euclidiano estendido, que computa, além do maior divisor comum dos números inteiros a e b, o coeficiente da identidade de Bézout

O site já possui O maior divisor comum de dois números inteiros, que utiliza o algoritmo euclidiano. No fim das contas, existe o algoritmo euclidiano estendido. Este algoritmo computa, além do maior divisor comum dos números inteiros a e b, os coeficientes da identidade de Bézout, que são os números inteiros x e y conforme

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

Então, ela permite computar os quocientes de a e b através do seu maior divisor comum.

Você pode ver a calculadora, assim como a teoria, que como de costume, se encontra abaixo

PLANETCALC, Algoritmo de Euclides Estendido

Algoritmo de Euclides Estendido

Maior Divisor Comum
 
Coeficiente para maior número inteiro
 
Coeficiente para menor número inteiro
 

O algoritmo estendido utiliza a recursão e computa os coeficientes no seu retorno. As fórmulas dos cálculos podem ser obtidas a partir das seguintes considerações:

Sabendo dos coeficientes (x_1,y_1) para o par (b\%a,a), tais como:

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

e precisamos calcular os coeficientes do par (a,b), tais como:

 ax + by = g

Primeiro, substituímos b\%a com:

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

\left\lfloor \frac{b}{a} \right\rfloor - quociente da divisão do número inteiro de b ao a,

e usa-o como substituto em:

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

Em seguida, após agrupar, obtemos:

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

Ao comparar esta com a equação inicial, podemos expressar x e y:

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

O começo do retorno da recursão é o final do algoritmo euclidiano, quando a = o e o MDC = b, então os primeiros x e y são 0 e 1 respectivamente. Os coeficientes posteriores são computador utilizando as fórmulas acima.

URL copiado para a área de transferência
PLANETCALC, Algoritmo euclidiano estendido

Comentários