Algoritmo de Euclides

19-05-2013 15:48

 

    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/

 

Tópico: Comentários

Não foram encontrados comentários.

Novo comentário