Ir para o conteúdo
OneKitly

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

Daniel Okonkwo — Programador front-end e redator de Tecnologia na OneKitly

Desempenho web · Formatos de ficheiro

Verificado a partir de 2 fontes

Ver perfil →
Em resumo

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.

Publicidade

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.

Os passos de divisão para 252 e 105
PassoResto
252 = 2 × 105 + 4242
105 = 2 × 42 + 2121
42 = 2 × 21 + 00 — fim
Calculadora do algoritmo de Euclides estendidoExecuta o algoritmo de Euclides estendido sobre dois inteiros a e b: devolve o seu máximo divisor comum junto com os coeficientes de Bézout x e y que satisfazem a·x + b·y = mdc(a, b). Para além do mdc, esses coeficientes são exatamente o que precisas para construir inversos modulares e resolver equações diofantinas lineares. É mostrada a tabela completa de divisões para seguir cada redução.Experimentar a ferramenta →
Publicidade

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?