Algoritmo euclidiano estendido

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

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

Algoritmo de Euclides Estendido

Primeiro número inteiro

Segundo número inteiro

Calcular

Maior Divisor Comum

 

Coeficiente para maior número inteiro

 

Coeficiente para menor número inteiro

 

 Link  Salvar  Widget

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 para o par , tais como:

,

e precisamos calcular os coeficientes do par , tais como:

Primeiro, substituímos com:

, onde

- quociente da divisão do número inteiro de b ao a,

e usa-o como substituto em:

Em seguida, após agrupar, obtemos:

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

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.