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
Esta página existe graças aos esforços das seguintes pessoas:
 | Timur
|
Clecius Brandao
| |
Julia Gomes
|
Este conteúdo é licenciado de acordo com a Licença Creative Commons de Atribuição/CompartilhaIgual 3.0 (Unported). Isso significa que você pode redistribuir ou modificar livremente este conteúdo sob as mesmas condições de licença e precisa atribuir ao autor original colocando um hyperlink para este trabalho no seu site. Além disto, favor não modificar qualquer referência ao trabalho original (caso houver) que estiverem contidas neste conteúdo.
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
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