- máximo divisor comum
- redução por restos
- algoritmo estendido
- base para aritmética modular
Você tem 252 peças vermelhas e 105 azuis e quer formar o maior número de grupos idênticos, sem sobrar nenhuma. Em vez de testar divisor por divisor, o algoritmo de Euclides reduz o problema preservando a resposta.
Divida 252 por 105: sobra 42. Depois divida 105 por 42: sobra 21. Como 42 dividido por 21 não deixa resto, 21 é o máximo divisor comum.
Por que funciona? Qualquer número que divide 252 e 105 também divide a diferença produzida ao retirar grupos de 105 de 252 — o resto 42. Repetir a redução preserva os divisores comuns até a resposta ficar visível.
Procedimentos equivalentes aparecem nos Livros VII e X dos Elementos. O nome homenageia a obra que o preservou; não prova que Euclides tenha sido seu primeiro inventor.
RELEVÂNCIA HISTÓRICAÉ um dos algoritmos mais antigos ainda usados. Versões estendidas encontram coeficientes úteis para aritmética modular, que integra sistemas criptográficos modernos.