É um dos algoritmos mais antigos do mundo, escrito há cerca de 300 AC. Ele nada mais é do que repetidas divisões com resto que encontram o mdc.
Exemplo do algoritmo na linguagem python:
Algoritmo Estendido de Euclides:
Pode ser usado para expressar o mdc(a,b) como uma combinação linear de inteiros a e b: ax+by=mdc(a,b). Ex:
2024=748(2)+528
748=528(1)+220
528=220(2)+88
220=88(2)+44 * o último resto diferente de zero é a resposta.
88=44(2)+0
Concluímos que o mdc(2024,748)=44.
Agora usamos a substituição para expressar que 44 é a combinação linear de a=2024 e b=748, calculado o resto com: r=a-b*q.
528=2024-748(2)
528=a-2b
Sub. na 2 linha:
b=(a-2b)*1+220 , então, 220=-a+3b
Sub. na 3 linha:
a-2b=(-a+3b)*2+88, então, 88=3a-8b
Sub. na penúltima linha:
-a+3b=(3a-8b)*2+44 , então, 44=-7a+19b
Ficando:
44=-7*2024+19*748=44=mdc(2024,748)
Concluímos que a solução inteira de 2024x+748y=mdc(2024,748) é: x=-7, y=19.
Algoritmo estendido de Euclides em python:
Se x0, y0 são a solução inteira de ax+by=mdc(a,b), então para cada inteiro k:
x=x0+ bk e y=y0+ ak
mdc(a,b) mdc(a,b)
também é uma solução.
No exemplo acima, concluímos que x=-7+17k e y=19+46k são soluções para cada inteiro k.
Números Relativamente Primos:
Se o mdc(a,b)=1, dizemos que a e b são relativamente primos. Por exemplo, 2091 e 2143 são relativamente primos:
2143=2091+52
2091=40(52)+11
52=4(11)+8
11=8+3
8=2(3)+2
3=2+1
Então, o mdc(2091,2143)=1.
Podemos usar a função de Euler para encontrar os números relativamente primos. Ex:
φ(420): Fatorando os primos 420 = 2²*3*5*7, então os divisores primos de 420 são 2, 3, 5, 7. Aplicando a função phi de Euler: n*(p-1/p1)*(p-1/p2)*...*(p-1/pk):
φ(420): 420*1/2*2/3*4/5*6/7=96, encontramos φ(420)=96.
Exemplo da função phi de Euler em python:
* Referências:
http://www.shsu.edu/kws006/Professional/Concepts_files/EuclideanAlgorithm.pdf
http://www3.nd.edu/~sevens/13150unit10.pdf
http://pages.pacificcoast.net/~cazelais/222/xeuclid.pdf
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=primeNumbers
