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:
(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:
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 é 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).
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”.
2 comentários
1 ping
Não ficou bem clara a explicação, não consegui entender tudo.
Author
O que não ficou bem claro? A forma mais simples de compreenderem será inventarem um exemplo vosso e tentarem seguir o algoritmo.
Dou aqui outro exemplo:
Qual o maior divisor comum de 70 e 75?
75=70 x 1 + 5
70 = 5 x 14 + 0
Tendo em conta o que refiro no artigo: 5 é o maior divisor comum (porque é o “resto” na igualdade anterior àquela em que o resto é 0).
[…] podem ser considerados “primos entre si” caso o máximo divisor comum entre eles seja 1 (ver o Algoritmo de Euclides). No caso da demonstração de cima, o “truque” está em definir o número N que é primo em […]