O Algoritmo de Euclides é uma das formas de se encontrar o MDC - máximo divisor comum de dois números inteiros. O MDC é uma combinação linear destes dois números. O Algoritmo de Euclides estendido, 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 números 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,
    120*-9 + 23*47 = MDC(120,23)

Um pouco de álgebra para entender o Algoritmo de Euclides estendido

Para encontrar o MDC(120,23) usando o Algoritmo de Euclides, procede-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
              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 ................ e, como 5 = 1*120 - 5*23
            3 = 1*23 - 4(1*120 - 5*23)
            3 = -4*120 + 21*23

    (3)     2 = 1*5 - 1*3 ................. como 5 = 1*120 - 5*23 e
                                                 3 = -4*120 + 21*23
            2 = 1(1*120 - 5*23) - 1(-4*120 + 21*23)
            2 = 5*120 - 26*23

    (4)     1 = 1*3 - 1*2
            1 = 1(-4*120 + 21*23) - 1(5*120 - 26*23)
            1 = -9*120 + 47*23

    portanto, x = -9 e y = 47 e -9*120 + 47*23 = MDC(120,23)

Esta ferramenta é muito útil nas nossas lidas criptológicas!

vovó Vicki