O Algoritmo de Euclides serve para achar o máximo divisor comum entre números de um modo rápido e no mínimo curioso.
Consideremos por exemplo os números 42783 e 9857 (escolhidos aleatoriamente), qual será o máximo divisor comum entre eles, sem recorrer à factorização?
Fazemos então a igualdade: 42783 = 9857 x a + b (algoritmo da divisão de 42783 por 9857, em que ‘a’ é o maior número natural que permita que ‘b’ também seja um número natural).
Se fizermos a divisão, obtemos a=4 e b=3355.
Começa então um procedimento iterativo:
Pegamos no 9857 e colocámo-lo no sítio do 42783, o ‘b’ toma o lugar do 9857, (o ‘a’ deixa de ter interesse). Deste modo obtemos:
9857 = 3355 x c + d , (c e d são números naturais).
Obtém-se: c = 2 e d = 3147.
De modo análogo:
O máximo divisor comum será o 1 neste caso (o que significa que os números em causa são primos entre si), ou seja, o máximo divisor comum aparece neste procedimento na igualdade anterior à que der resto (b) zero.
Deixo um desafio: tentem provar o porquê do método funcionar deste modo, ou seja, qual a lógica subjacente.
Euclides de Alexandria (325 a.C. – 265 a.C.). É considerado o “pai” da Geometria. Escreveu um dos mais influentes livros de matemática: “Os Elementos”.
Marinho Lopes (colaborador do Ciência com Todos e doutorando em Física) - texto primeiramente publicado no Blog do autor: Sophia of Nature.
Ver original em: http://sophiaofnature.wordpress.com/2011/05/09/algoritmo-de-euclides/
