Calcular O Máximo Divisor Comum

O que eu faço quando preciso calcular o máximo divisor comum de dois números grandes

A primeira coisa que as pessoas aprendem no colégio é o algoritmo de Euclides, mas raramente explicam por que ele funciona ou quando ele se torna problemático na prática. Vou começar pela parte que realmente importa: como calcular o máximo divisor comum de forma eficiente, sem perder tempo fatorando números até não aguentar mais. O algoritmo de Euclides funciona assim. Você pega dois números, digamos a e b, onde a é maior que b. Você divide a por b e pega o resto. Se o resto for zero, b é o MDC. Se não for zero, você repete o processo com b e o resto. Continue até o resto ser zero. O último divisor não-nulo é o resultado. Peguem 48 e 18 como exemplo rápido. 48 dividido por 18 dá resto 12. Agora dividem 18 por 12, resto 6. Agora dividem 12 por 6, resto 0. O MDC é 6. Isso leva três passos. Fatorar 48 e 18 em primos daria o mesmo resultado, mas com muito mais trabalho manual.

Por que o algoritmo de Euclides domina na prática

A razão pela qual todo mundo usa Euclides em vez de fatoração primária não é só economia de passos. É estabilidade computacional. Fatoração de números grandes é um problema computationalmente duro. O algoritmo de Euclides roda em tempo polinomial em relação ao número de dígitos. Para números de até 64 bits, ele executa em microssegundos em qualquer máquina moderna. Existe uma variante chamada algoritmo de Euclides binário que substitui divisões por deslocamentos de bit e subtrações. Em implementações de baixo nível, isso pode ser 20 a 30 por cento mais rápido porque evita divisão inteira, que é a operação aritmética mais cara em hardware. A diferença é menor em Python com números pequenos, mas quando você está processando milhares de pares de números, esses microssegundos se acumulam.

O problema que eu encontrei e como contornei

Eu precisei calcular o máximo divisor comum para frações em um sistema que processava milhares de parcelas de um empréstimo com termos muito específicos. O problema era que alguns números tinham fatores primos muito grandes — chegamos a ter números na casa dos bilhões com fatores como 999983, que é primo. A fatoração trial division simplesmente travava. Leva cerca de sqrt(n) operações no pior caso, o que para n próximo de 10^9 significa bilhões de iterações. A solução foi usar o algoritmo de Euclides recursivo com memoização quando havia chamadas repetidas. Em Python, a função fica algo assim: def mdc(a, b):
    while b:
        a, b = b, a % b
    return abs(a)

Isso resolveu o gargalo. O cálculo que antes levava minutos por parcela caiu para microseconds. Mas há um detalhe que muitas bibliotecas tradicionais ignoram: o módulo em Python com números negativos. -48 % 18 retorna 6 em Python, mas em algumas linguagens C-like retorna -12. Isso quebra a lógica do algoritmo se você não normalizar os sinais primeiro. Por isso eu sempre uso abs() no resultado.

Limitações e armadilhas que ninguém conta

O algoritmo de Euclides não é universal. Ele funciona perfeitamente para inteiros, mas quando você transita para polinômios ou números complexos, a coisa muda de figura. Para polinômios, você precisa do algoritmo de Euclides dividido por coeficientes no corpo dos coeficientes, o que introduz frações racionais e instabilidade numérica em coeficientes de ponto flutuante. Outro problema prático: para números extremamente grandes, como aqueles usados em criptografia RSA com 2048 bits, o algoritmo de Euclides padrão ainda funciona, mas versões otimizadas como o binary GCD ou o subtrativo podem se sair melhor dependendo da arquitetura. Em Python puro, a diferença é mínima. Em C com gmp library, pode haver ganho significativo. Existe também o caso dos números coprimos. Quando o MDC de dois números é 1, eles são coprimos. Isso é fundamental em criptografia, mas também é um cenário onde o algoritmo pode levar mais iterações do que o esperado. O pior caso para o algoritmo de Euclides ocorre com números consecutivos de Fibonacci. MDC(F(n+1), F(n)) leva exatamente n passos. Para F(50), que é cerca de 12 bilhões, você faria 50 divisões. Ainda é rápido, mas é o limite teórico.

Quando eu não uso o algoritmo de Euclides

Se você precisa calcular o máximo divisor comum para milhões de pares de números pequenos — digamos, todos abaixo de 1000 — pré-computar uma tabela usando o crivo de Eratóstenes para fatoração rápida pode ser mais eficiente. A fatoração prévia de todos os números até 1000 leva menos de um milissegundo, e cada consulta de MDC vira uma interseção de multiconjuntos de fatores primos. Para quem quer calcular o máximo divisor comum em scripts do dia a dia, Python já traz math.gcd na biblioteca padrão desde a versão 3.5. A função lida com inteiros positivos e negativos automaticamente e é implementada em C, então é rápida. A versão 3.9+ também suporta múltiplos argumentos, o que elimina a necessidade de reduzir com functools.reduce. A versão mais recente que eu testei, a 3.12, ainda mantém a mesma assinatura simples. Se você está usando uma versão mais antiga ou uma linguagem diferente, a implementação manual com while e módulo é trivial e evita dependências externas.

Uma última observação prática: nunca confie cegamente em bibliotecas que retornam MDC negativo. O máximo divisor comum é definido como positivo por convenção matemática. Se sua função retornar um valor negativo, normalize com abs(). Eu vi esse erro propagar-se por código de produção em várias ocasiões, causando divergências silenciosas em cálculos financeiros.