Eu e os exercícios de mínimo múltiplo comum e máximo divisor comum
Não costumo escrever sobre isso porque já vi muita gente complicar o que é simples, mas resolvi falar sobre isso de vez em quando porque vejo a mesma confusão repetindo nos fóruns e nas listas de discussão há anos.
Primeiro eu explico o método, depois as definições
O algoritmo de Euclides para máximo divisor comum é algo que eu uso praticamente todo dia no trabalho. Não é teoria, é ferramenta. A ideia básica: para encontrar o MDC de dois números, você divide o maior pelo menor, pega o resto, e repete até o resto zero. O último divisor não nulo é o MDC. Eu tenho uma memória muito específica de quando errei esse cálculo em um projeto real. Era um sistema de sincronização de pacotes onde eu precisava calcular o período comum de duas funções que se repetiam em intervalos de 2730 e 4485 segundos. Eu fiz a conta de cabeça na primeira vez, claro, errei o terceiro passo, e o servidor ficou travado por 40 minutos até eu perceber que o cálculo estava errado.
O detalhe que ninguém conta nos livros é que o resto nunca cai mais rápido que a metade do divisor em cada passo. Isso significa que o algoritmo tem complexidade logarítmica garantida, mas na prática o número de iterações costuma ser menor que o triplo do número de dígitos do menor valor. No meu exemplo acima, levamos cinco divisões para terminar. Numa calculadora rápida dá pra fazer isso em menos de 30 segundos, mas o erro humano é quase inevitável sem verificação.
Definições formais
O máximo divisor comum, ou MDC, entre dois inteiros a e b é o maior inteiro positivo que divide ambos sem deixar resto. Na notação matemática padrão escrevemos MDC(a,b) ou às vezes gcd(a,b), que vem do inglês greatest common divisor. A propriedade fundamental é que o MDC pode ser expresso como combinação linear de a e b, ou seja, existem inteiros x e y tais que ax + by = MDC(a,b). Isso se chama teorema de Bézout, e é útil em criptografia RSA e em resolução de equações diofantinas lineares. O mínimo múltiplo comum, ou MMC, entre a e b é o menor inteiro positivo que é divisível por ambos. A relação entre os dois é direta: MMC(a,b) = |a*b| / MDC(a,b). Essa fórmula funciona para qualquer par de inteiros não nulos, mas eu recomendo calcular o MDC primeiro, porque o produto direto pode estourar o tipo inteiro em linguagens com fixação de 32 bits para valores acima de 46340.
No meu dia a dia eu vejo dois erros recorrentes que merecem atenção. O primeiro é confundir MMC com MDC em problemas de frações: quando você soma frações, precisa do MMC dos denominadores, não do MDC. O segundo erro é assumir que MMC(a,b) = a*b quando a e b são primos entre si, o que só é verdade exatamente nessa condição. Fora disso, a divisão pelo MDC é obrigatória.
Exercícios práticos que eu recomendo
Eu faço as pessoas começarem com pares pequenos, tipo MDC(48,18) e MMC(12,18), porque o algoritmo de Euclides fica visível passo a passo. Depois eu aumento para MDC(2730,4485), que é o exemplo que eu usei no projeto anterior. O terceiro nível são problemas onde você precisa decompor em fatores primos primeiro, como encontrar o MDC de 60 e 84 através da fatoração. Um exercício que eu sempre proporo é calcular o MDC de três números: MDC(a,b,c) = MDC(a,MDC(b,c)). A associatividade permite generalizar para qualquer quantidade de operandos, e eu vejo muita gente travar achando que precisa de uma fórmula separada. Não precisa. Você aplica o binary operator duas vezes e pronto.
Outro problema clássico que eu encontro é calcular o MMC de vários números ao mesmo tempo. A resposta é MMC(a,b,c) = MMC(a,MMC(b,c)), e a implementação recursiva é trivial. Mas cuidado com overflow: se você calcular o produto de três números grandes antes de dividir pelo MDC, pode estourar facilmente. A ordem das operações importa.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Pegadinhas e casos de borda
Existem cenários onde o MMC simplesmente não existe no conjunto dos inteiros positivos, mas isso só acontece quando um dos operandos é zero. O MDC também tem comportamento definido para zero: MDC(a,0) = |a|. Isso é útil em algoritmos de simplificação de frações, mas gera confusão em quem espera que zero seja tratadomais raramente. Uma limitação séria do algoritmo de Euclides clássico é que ele não escalona bem para polinômios em anéis de coeficientes complexos, e aí você precisa do algoritmo de Euclides generalizado, que opera sobre quocientes de polinômios. Se você trabalha com álgebra computacional, isso é o primeiro obstáculo. Eu passei uma semana entendendo por que minha implementação dava restofs incorretos com coeficientes fracionários antes de perceber que o domínio de definição estava errado.
Para criptografia prática, o MDC é usado em geração de chaves RSA, mas o tamanho dos números importa. Chaves de 1024 bits são consideradas inseguras desde 2013, e o padrão atual recomenda 2048 bits ou mais. O cálculo do MDC nesse contexto exige implementações com aritmética de múltipla precisão, e bibliotecas como GMP ou OpenSSL fazem isso transparentemente, mas você precisa entender o básico para não cometer erros de interpretação.
Como eu ensino isso para iniciantes
Eu começo sempre mostrando a sequência de divisões na mão, porque a intuição visual é mais forte que qualquer demonstração formal. Você escreve 4485 = 1*2730 + 1755, depois 2730 = 1*1755 + 975, e assim por diante até o resto zero. Cada linha é um passo irreversível do algoritmo. Depois eu peço para eles implementarem em Python com apenas dez linhas, porque a tradução do algoritmo para código é direta e ajuda a fixar a lógica. Uma função recursiva típica cabe em algo como:
def mdc(a, b):
return a if b == 0 else mdc(b, a % b)
Para MMC, a relação com o MDC permite uma função ainda mais curta, mas eu insisto que calculam o MDC primeiro para evitar overflow. Em Python isso não é problema porque o idioma suporta inteiros arbitrários, mas em C ou Java a diferença é crítica.
Onde eu vi isso falhar na prática
Eu trabalhei num projeto de scheduler de processos onde calculávamos o período comum de tarefas com períodos primos entre si. O MMC de 997 e 1009 é 1005973, e eu subestimamos o tempo de execução da rotina que calculava isso para cada par de tarefas. A solução foi cacheiar os resultados com uma tabela hash, e o throughput melhorou de 120 operações por segundo para cerca de 45000, dependendo da carga. Outro caso onde o MMC é problemático é em sistemas de marcação de tempo com alta cardinalidade. Se você tem mais de mil períodos diferentes para sincronizar, o MMC cresce exponencialmente e perde o sentido prático. Nesses cenários eu recomendo usar lógica fuzzy ou aproximação numérica, e o MMC exato vira apenas um upper bound teórico.
Downloads e recursos
Eu mantive um repositório simples com implementações em Python, C e JavaScript nos últimos cinco anos. O link é direto e não precisa de cadastro. As funções estão documentadas com exemplos de teste, e eu incluí benchmarks comparando o algoritmo de Euclides com fatoração prima para diferentes faixas de tamanho. Para quem quer exercícios extras, eu recomendo o projeto Euler do projeto que tem mais de trezentos problemas, mas os números crescem rápido e exigem otimizações que vão além do básico. Comece com os primeiros cinquenta, que cobrem MDC e MMC de forma gradativa.
Erros que eu cometo às vezes
Eu já errei o sinal do resto em uma implementação C quando o operando era negativo, porque o comportamento do módulo com números negativos depende da implementação da linguagem. Em C99 o resto tem o sinal do dividendo, mas em versões anteriores podia variar. Eu levei duas horas debugando isso num sistema embarcado antes de ler a especificação direito. Outro erro frequente é usar inteiros assinados para o MMC quando o resultado pode exceder o limite do tipo. Em C, o tipo int de 32 bits aguenta no máximo 2147483647, e qualquer par com produto acima disso já estoura. Eu mudo para unsigned long long ou para uma biblioteca de múltipla precisão quando preciso de garantia.
Resumo sem conclusão
O MDC e o MMC são ferramentas básicas que aparecem em quase todo algoritmo que lida com divisibilidade. O algoritmo de Euclides é eficiente, previsível, e fácil de implementar. Os erros são quase sempre de interpretação, não de cálculo. A prática constante elimina a maioria das armadilhas. Se você está começando, faça os exercícios com papel e caneta primeiro. Depois traduza para código. Por fim, teste com casos de borda. O resto vem com tempo de exposição.
