Algoritmo de Euclides

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\times 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 coloca-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\times c + d , (c e d são números naturais).

Obtém-se: c = 2 e d = 3147.

De modo análogo:
3355 = 3147\times 1 + 208\\ 3147 = 208\times 15 + 27\\ 208 = 27\times 7 + 19\\ 27 = 19\times 1 + 8\\ 19 = 8\times 2 + 3\\ 8 = 3\times 2 + 2\\ 3 = 2\times 1 + \textbf{1}\\ 2 = 1\times 2 + 0

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 é o “resto” da penúltima igualdade (a igualdade anterior à que der resto (b) zero).

Deixo um desafio: tentem descobrir qual a lógica subjacente ao método (o porquê de funcionar).

Euclid1

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

Anúncios

2 thoughts on “Algoritmo de Euclides

  1. Pingback: O Fascínio dos Números – Parte II | Sophia of Nature

  2. Pingback: Índice de Artigos | Sophia of Nature

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s