Algoritmo de Euclides estendido
# Algoritmo de Euclides estendido

O Algoritmo de Euclides estendido é uma extensão do algoritmo de Euclides, que, além de calcular o máximo divisor comum (MDC) entre $a,b\in \mathbb {Z} ,$ fornece os coeficientes $\alpha ,\beta \in \mathbb {Z}$ tais que $\alpha a+\beta b=mdc(a,b).$
O algoritmo é utilizado, em especial, para o cálculo de inverso modular. Se $a$ e $b$ são coprimos, então $\alpha$ é o inverso modular de $a$ módulo $b$ e $\beta$ é o inverso modular de $b$ módulo $a.$ Essa propriedade é amplamente utilizada no estudo em Criptografia, mais especificamente, no processo de quebra de chaves privadas do método de encriptação RSA.

## Entendendo o algoritmo

O Algoritmo de Euclides nos fornece a seguinte propriedade: na k-ésima iteração, vale que
$r_{k+1}=r_{k-1}-r_{k}q_{k}$
em que $q_{k}={\frac {r_{k-1}}{r_{k}}}$ é uma divisão inteira.
O algoritmo acaba quando $r_{k+1}=0,$ definindo o resto atual como o máximo divisor comum: $r_{k}=MDC(a,b).$
Para estender o algoritmo, queremos também manter a seguinte propriedade:
$r_{k}=au_{k}+bv_{k}$
dessa forma, quando o algoritmo acabar, teremos valores $u_{k}$ e $v_{k}$ que satisfazem o teorema de Bézout.
Para isso, assuma que nós temos esses valores para a iteração $k$ e para a iteração anterior, $k-1:$ ou seja, assuma que já temos os valores que satisfazem as duas igualdades a seguir:
$r_{k}=au_{k}+bv_{k}$ e $r_{k-1}=au_{k-1}+bv_{k-1}$
então, para o próximo resto, teremos
${\begin{aligned}r_{k+1}&=r_{k-1}-r_{k}q_{k}\\&=(au_{k-1}+bv_{k-1})-(au_{k}+bv_{k})q_{k}\\&=au_{k-1}-au_{k}q_{k}+bv_{k-1}-bv_{k}q_{k}\\&=a(u_{k-1}-u_{k}q_{k})+b(v_{k-1}-v_{k}q_{k})\\&=au_{k+1}+bv_{k+1}\\\end{aligned}}$
Ou seja, se a igualdade de Bézout vale para a iteração atual do algoritmo e para a iteração anterior, então, ela vale para a próxima e os valores de Bézout são
$u_{k+1}=u_{k-1}-u_{k}q_{k}$
e
$v_{k+1}=v_{k-1}-v_{k}q_{k}$
Perceba que os valores de Bézout também estão sendo totalmente definidos pelos valores das duas últimas iterações do algoritmo.
Dessa forma, para estender o Algoritmo de Euclides original, só precisamos guardar os valores referentes à essas duas sequências ($v_{k}$ e $u_{k}$) além da que o original já guarda (a sequência $r_{k}$) e definir valores para que tenhamos igualdades válidas para $k=0$ e para $k=1$ (já que cada sequência é definida em termos de duas iterações anteriores).
No entanto, definir esses valores é fácil: podemos tomar
$(r_{0},u_{0},v_{0})=(a,1,0),$
o que torna válida a igualdade para $k=0$ (ou seja, $r_{0}=au_{0}+bv_{0}$) e
$(r_{1},u_{1},v_{1})=(b,0,1),$
o que torna válida a igualdade para $k=1$ (ou seja, $r_{1}=au_{1}+bv_{1}$)

## Um exemplo

Para encontrar o MDC(120,23) usando o Algoritmo de Euclides, vamos efetuando divisões da seguinte forma:
Levando-se em conta apenas os restos encontrados, pode-se dizer que:
portanto, x = -9 e y = 47 e temos:

## O algoritmo

Uma implementação do algoritmo em JavaScript: