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
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
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.
Comentários