O algoritmo de Euclides dá o MDC e a receita para o fabricar
Publicado a 27/10/2026 · 3 min de leitura · Calculadoras do dia a dia
Daniel Okonkwo — Programador front-end e redator de Tecnologia na OneKitly
Desempenho web · Formatos de ficheiro
Verificado a partir de 2 fontes
O algoritmo comum substitui repetidamente o número maior pelo seu resto contra o menor: 252 deixa 42 contra 105, 105 deixa 21 contra 42, e 42 nada deixa contra 21, pelo que 21 é o máximo divisor comum. A versão estendida guarda registo de como cada resto foi construído pelo caminho e devolve dois inteiros que combinam os números originais nesse divisor — aqui −2 e 5, pois 252 × (−2) + 105 × 5 = −504 + 525 = 21. Essa combinação existe sempre, facto chamado identidade de Bézout, e é ela que produz um inverso modular: quando o divisor é um, o coeficiente do primeiro número é exatamente o inverso desse número módulo o segundo.
252 e 105 têm um máximo divisor comum de 21, e a versão estendida devolve também −2 e 5: 252 × (−2) + 105 × 5 = 21 exatamente.
Porque termina tão depressa
Cada passo substitui um par por um par menor, e o encolhimento é rápido: ao fim de dois passos o número maior vale no máximo metade do que era, porque um resto é sempre menor do que o divisor e um dos dois tem de ficar abaixo de metade. O número de passos é portanto proporcional ao número de algarismos e não aos números em si, daí a facilidade com que o método trata valores de centenas de algarismos. O pior caso vem a ser o dos números de Fibonacci consecutivos, pormenor agradável e razão por que o limite se enuncia normalmente em logaritmo.
Os coeficientes não são únicos
Para 240 e 46 o algoritmo devolve −9 e 47, dando 240 × (−9) + 46 × 47 = 2, e essa é uma resposta entre infinitas: somar vinte e três ao primeiro coeficiente e subtrair cento e vinte ao segundo dá outro par válido, e assim sem fim. O algoritmo devolve o par de menores magnitudes, representante útil, e toda a implementação que compare dois resultados deve normalizar antes de concluir que diferem. É um risco geral dos problemas cujas respostas formam uma família e não um ponto.
| Passo | Resto |
|---|---|
| 252 = 2 × 105 + 42 | 42 |
| 105 = 2 × 42 + 21 | 21 |
| 42 = 2 × 21 + 0 | 0 — fim |
Perguntas frequentes
- Que idade tem este método?
- Aparece nos Elementos de Euclides, escritos cerca de trezentos anos antes da nossa era, o que faz dele o algoritmo mais antigo ainda em uso corrente. Nada nele foi melhorado no sentido que conta: existem variantes que evitam a divisão ou assentam melhor em hardware binário, mas o número de passos e a ideia subjacente não mudaram. Que um procedimento escrito para geometria em papiro esteja dentro de todo o aparelho que faz criptografia de chave pública é uma das continuidades mais marcantes do campo.
- Para que servem os coeficientes além dos inversos?
- Para resolver equações em números inteiros, que é o uso para que primeiro se quiseram. Uma equação que pede quantidades inteiras de duas grandezas que devem totalizar uma terceira tem solução exatamente quando o máximo divisor comum das duas divide a terceira, e os coeficientes dão uma diretamente; as restantes seguem-se somando múltiplos de um passo fixo. Isso cobre compor um montante com dois valores de moeda, sincronizar dois ciclos repetitivos, e qualquer pergunta análoga onde respostas fracionárias não sejam permitidas. É também a maquinaria por trás de reconstituir um valor a partir de vários restos ao mesmo tempo.
Artigos que podem interessar-lhe
Todos os guias →Ferramentas relacionadas
Fontes
Detetaste um erro neste artigo?