Algoritmo de Euclides estendido

O Algoritmo de Euclides estendido é uma das formas de se encontrar o máximo divisor comum (MDC) de dois números inteiros. Nele, ao invés de retornar um valor único, fornece a combinação linear, muito útil quando os inteiros são primos entre si. Por exemplo:

MDC(120,23) = 1

120 e 23 são inteiros primos entre si porque não existe um divisor maior do que 1 que divida ambos. O Algoritmo de Euclides estendido retorna:

ax + by = MDC(a, b)

ou seja:

MDC(120,23) $=120*(-9)+23*47$

Entendendo o algoritmo

Para encontrar o MDC(120,23) usando o Algoritmo de Euclides, coloca-se da seguinte forma:

(1)    120/23 = 5 resta 5
(2)      23/5 = 4 resta 3
(3)       5/3 = 1 resta 2
(4)       3/2 = 1 resta 1
(5)       2/1 = 2 resta 0 

MDC(120,23) = 1

Levando-se em conta apenas os restos encontrados, pode-se dizer que:

(1)     5 = 1*120 - 5*23
(2)     3 = 1*23 - 4*5   Substituindo o 5 temos
        3 = 1*23 - 4*(1*120 - 5*23)
        3 = -4*120 + 21*23
(3)     2 = 1*5 - 1*3    Substituindo o valor de 5 e 3 temos
        2 = 1(1*120 - 5*23) - 1(-4*120 + 21*23)
        2 = 5*120 - 26*23
(4)     1 = 1*3 - 1*2   Novamente substituindo 3 e 2
        1 = 1(-4*120 + 21*23) - 1(5*120 - 26*23)
        1 = -9*120 + 47*23

portanto, x = -9 e y = 47 e temos:

MDC(120,23) = $120*(-9)+47*23$

Referências

• Coutinho, Severino Coullier. Números inteiros e criptografia RSA. Rio de Janeiro: IMPA, 2005. 226 p. ISBN 8524401249
• Knuth, D. E. The art of computer programming. Vol. 2. Seminumerical algorithms, 2ed. Addilson-Wesley Publishing Company, Reading