Algoritmo Euclidiano Estendido

O algoritmo Euclidiano Estendido é um algoritmo para calcular números inteiros xxx e yyy tal que

ax+by=gcd(a,b)ax + by = \gcd(a,b)ax+by=gcd(a,b)

given aaaa e bbb.

A existência de tais inteiros é garantida pelo lema de Bézout.

O algoritmo Euclidiano estendido pode ser visto como o recíproco da exponenciação modular.

A existência de tais inteiros é garantida pelo lema de Bézout.

O algoritmo Euclidiano estendido pode ser visto como o recíproco da exponenciação modular.

A reversão dos passos no algoritmo Euclidiano permite encontrar estes inteiros xxx e yyyy. A ideia é começar com o GCD e trabalhar recursivamente o nosso caminho para trás. Isto pode ser feito tratando os números como variáveis até que terminemos com uma expressão que é uma combinação linear dos nossos números iniciais. Vamos fazer isso com o exemplo que usamos acima.

Começamos com o nosso DCB. Reescrevemo-lo em termos dos dois termos anteriores:

2=26-2×12,2 = 26 – 2 \ vezes 12 .2=26-2×12.

Substituímos para 121212 tomando a nossa linha anterior (38=1×26+12)(38 = 1 \ vezes 26 + 12)(38=1×26+12) e escrevendo-a em termos de 12:

2=26-2×(38-1×26).2 = 26 – 2 \ vezes (38 – 1\ vezes 26). 2=26-2×(38-1×26).

Colher como termos, os 262626, e temos

2=3×26-2×38.2 = 3 \ vezes 26 – 2 \ vezes 38. 2=3×26-2×38,

Repetir o processo:

2=3×(102-2×38)-2×38,2 = 3 \ vezes (102 – 2\ vezes 38) – 2\ vezes 38,2=3×(102-2×38)-2×38,

O resultado final é a nossa resposta:

2=3×102-8×38.2 = 3 \ vezes 102 – 8 \ vezes 38,2=3×102-8×38,

Tu xxx e yyyy são 333 e -8-8-8,

>

De tal forma que 1914a+899b=gcd(1914,899).1914a + 899b = \gcd(1914,899). 1914a+899b=gcd(1914,899).

Primeiro uso do algoritmo de Euclid para encontrar o GCD:

1914=2×899+116899=7×116+87116=1×87+2987=3×29+0.\1914 &= 2\\posições 899 + 116\899 &= 7\posições 116 + 87\116 &= 1\posições 87 + 29\\87 &= 3\posições 29 + 0.\\\a1}final{alinhado}191489911687=2×899+116=7×116+87=1×87+29=3×29+0,

Deste último, o último remanescente não-zero (GCD) é 292929.Agora usamos o algoritmo estendido:

29=116+(-1)×8787=899+(-7)×116.\begin{alinhado} 29 &= 116 + (-1)\\87 &= 899 + (-7)\ \ \ \end{alinhado}2987=116+(-1)×87=899+(-7)×116.

Substituindo 878787 na primeira equação, temos

29=116+(-1)×(899+(-7)×116)=(-1)×899+8×116=(-1)×899+8×(1914+(-2)×899)=8×1914+(-17)×899=8×1914-17×899.\begin{alinhado}29&= 116 + (-1)\ vezes (899 + (-7)\ vezes 116) \\= (-1)|vezes 899 + 8\\postos 116 \postos 116 \postos (-1)\postos 899 + 8\postos ( 1914 + (-2)\postos 899 )\postos 899 + (-17) \postos 899 \postos 899 \postos 1914 – 17 \postos 899.\end{aligned}29=116+(−1)×(899+(−7)×116)=(−1)×899+8×116=(−1)×899+8×(1914+(−2)×899)=8×1914+(−17)×899=8×1914−17×899.

Desde que agora escrevemos o GCD como uma combinação linear de dois números inteiros, terminamos o algoritmo e concluímos

a=8,b=-17. □ a = 8, b =-17. _\\squarea=8,b=-17. □