Algoritmo de Euclides em Zig: MDC, MMC e Inverso Modular

Para calcular o MDC em Zig, aplique repetidamente a transformação (a, b) = (b, a % b) até que b seja zero. O valor restante em a é o máximo divisor comum. Essa é a forma iterativa do algoritmo de Euclides, tem complexidade O(log(min(a, b))) e precisa de espaço constante.

pub fn mdc(a_inicial: u64, b_inicial: u64) u64 {
    var a = a_inicial;
    var b = b_inicial;

    while (b != 0) {
        const resto = a % b;
        a = b;
        b = resto;
    }

    return a;
}

Por exemplo, mdc(252, 105) retorna 21. A mesma base permite calcular o MMC, simplificar frações, testar coprimalidade e encontrar inversos modulares.

O que é o máximo divisor comum?

O máximo divisor comum, abreviado como MDC, é o maior número inteiro positivo que divide dois inteiros sem deixar resto. Os divisores comuns de 48 e 18 são 1, 2, 3 e 6; portanto, MDC(48, 18) = 6.

Uma solução ingênua poderia testar todos os divisores até o menor dos dois números. Euclides é muito mais eficiente porque usa a propriedade:

MDC(a, b) = MDC(b, a mod b)
MDC(a, 0) = a

O resto remove múltiplos de b sem alterar os divisores compartilhados. Se um número divide a e b, também divide a - q × b, que é justamente o resto da divisão inteira.

Passo a passo do algoritmo de Euclides

Considere MDC(252, 105):

252 = 2 × 105 + 42  → MDC(252, 105) = MDC(105, 42)
105 = 2 × 42  + 21  → MDC(105, 42)  = MDC(42, 21)
 42 = 2 × 21  + 0   → MDC(42, 21)   = MDC(21, 0)

Resultado: MDC(252, 105) = 21

Em cada iteração, o segundo valor diminui. O processo termina quando o resto chega a zero.

Implementação iterativa em Zig

Esta versão aceita inteiros sem sinal. Assim, o contrato fica simples: qualquer entrada u64 é válida, inclusive zero.

/// Retorna o máximo divisor comum de dois inteiros não negativos.
/// Convenções: mdc(0, n) == n e mdc(0, 0) == 0.
pub fn mdc(a_inicial: u64, b_inicial: u64) u64 {
    var a = a_inicial;
    var b = b_inicial;

    while (b != 0) {
        const resto = a % b;
        a = b;
        b = resto;
    }

    return a;
}

A variável resto torna a troca explícita e evita perder o valor antigo de b. Também facilita a inspeção no depurador.

Casos de borda

A função já trata os casos mais importantes:

Se o domínio da sua aplicação não admite MDC(0, 0), valide as entradas antes de chamar a função em vez de esconder essa regra dentro do algoritmo.

Versão recursiva

A definição matemática se traduz diretamente para uma função recursiva:

pub fn mdcRecursivo(a: u64, b: u64) u64 {
    if (b == 0) return a;
    return mdcRecursivo(b, a % b);
}

A versão recursiva é curta e didática. Para código de biblioteca, a iterativa costuma ser preferível porque usa O(1) de memória e não depende da pilha de chamadas. As duas executam o mesmo número de divisões.

Como calcular o MMC usando o MDC

O mínimo múltiplo comum satisfaz a relação MDC(a, b) × MMC(a, b) = a × b para valores positivos. Em código, divida antes de multiplicar:

pub fn mmc(a: u64, b: u64) u64 {
    if (a == 0 or b == 0) return 0;
    return (a / mdc(a, b)) * b;
}

Para a = 48 e b = 18, o MDC é 6 e o resultado é (48 / 6) × 18 = 144.

Dividir primeiro reduz o tamanho do valor intermediário, mas não elimina todo risco de overflow: o MMC verdadeiro ainda pode ser maior que u64. Se os números vierem de entrada externa, use multiplicação verificada com std.math.mul ou um tipo maior adequado ao problema.

Testando MDC e MMC em Zig

Testes pequenos cobrem propriedades mais úteis do que apenas um exemplo feliz:

const std = @import("std");

test "MDC com valores comuns e casos de borda" {
    try std.testing.expectEqual(@as(u64, 21), mdc(252, 105));
    try std.testing.expectEqual(@as(u64, 6), mdc(48, 18));
    try std.testing.expectEqual(@as(u64, 6), mdc(18, 48));
    try std.testing.expectEqual(@as(u64, 1), mdc(17, 13));
    try std.testing.expectEqual(@as(u64, 9), mdc(0, 9));
    try std.testing.expectEqual(@as(u64, 9), mdc(9, 0));
    try std.testing.expectEqual(@as(u64, 0), mdc(0, 0));
}

test "MMC usa o MDC" {
    try std.testing.expectEqual(@as(u64, 144), mmc(48, 18));
    try std.testing.expectEqual(@as(u64, 0), mmc(0, 18));
}

Salve a implementação em euclides.zig e execute:

zig test euclides.zig

Uma propriedade importante é a simetria: mdc(a, b) == mdc(b, a). Outra é que, para d = mdc(a, b), tanto a % d quanto b % d devem ser zero quando d != 0.

Algoritmo de Euclides estendido

O algoritmo estendido não encontra apenas o MDC. Ele também calcula x e y para a identidade de Bézout:

a × x + b × y = MDC(a, b)

Para 252 e 105:

21 = 105 - 2 × 42
42 = 252 - 2 × 105
21 = 105 - 2 × (252 - 2 × 105)
21 = 252 × (-2) + 105 × 5

Logo, x = -2, y = 5 e MDC = 21.

const ResultadoEstendido = struct {
    divisor: i64,
    x: i64,
    y: i64,
};

/// Requer a >= 0 e b >= 0.
pub fn euclidesEstendido(a: i64, b: i64) ResultadoEstendido {
    if (b == 0) {
        return .{ .divisor = a, .x = 1, .y = 0 };
    }

    const anterior = euclidesEstendido(b, @rem(a, b));
    return .{
        .divisor = anterior.divisor,
        .x = anterior.y,
        .y = anterior.x - @divTrunc(a, b) * anterior.y,
    };
}

O uso de i64 é necessário porque os coeficientes de Bézout podem ser negativos mesmo quando as entradas são positivas. Para entradas muito grandes, as multiplicações dos coeficientes também podem exceder i64; escolha o tipo conforme os limites reais da aplicação.

Inverso modular em Zig

Um inteiro a possui inverso módulo m somente quando MDC(a, m) = 1. Se o algoritmo estendido produz:

a × x + m × y = 1

então, tomando os dois lados módulo m, obtemos a × x ≡ 1 (mod m). Portanto, x é o inverso procurado.

pub fn inversoModular(a: i64, modulo: i64) ?i64 {
    if (a < 0 or modulo <= 1) return null;

    const resultado = euclidesEstendido(a, modulo);
    if (resultado.divisor != 1) return null;

    return @mod(resultado.x, modulo);
}

Exemplos:

• inversoModular(3, 7) retorna 5, pois 3 × 5 mod 7 = 1;
• inversoModular(6, 9) retorna null, pois MDC(6, 9) = 3;
• o retorno opcional ?i64 obriga o chamador a tratar a ausência de inverso.

test "inverso modular existe apenas para coprimos" {
    try std.testing.expectEqual(@as(?i64, 5), inversoModular(3, 7));
    try std.testing.expectEqual(@as(?i64, null), inversoModular(6, 9));
}

MDC de vários números

Para uma lista, acumule o resultado dois a dois. Se o acumulador chegar a 1, é possível encerrar cedo porque nenhum processamento posterior diminuirá o MDC abaixo de 1.

pub fn mdcDeVarios(numeros: []const u64) u64 {
    if (numeros.len == 0) return 0;

    var resultado = numeros[0];
    for (numeros[1..]) |numero| {
        resultado = mdc(resultado, numero);
        if (resultado == 1) break;
    }

    return resultado;
}

Assim, mdcDeVarios(&.{ 12, 18, 24, 36 }) retorna 6.

Complexidade

O pior padrão clássico ocorre com números de Fibonacci consecutivos, mas a quantidade de iterações ainda cresce apenas de forma logarítmica.

Erros comuns

Trocar as variáveis na ordem errada

Este código perde o valor necessário:

// Incorreto
b = a % b;
a = b;

Depois da primeira linha, o b antigo desapareceu. Guarde o resto e só então atualize a e b.

Multiplicar antes de dividir no MMC

(a * b) / mdc(a, b) pode transbordar mesmo quando o resultado final cabe no tipo. Prefira (a / mdc(a, b)) * b e ainda considere multiplicação verificada.

Ignorar zero e sinais

Defina o contrato da função. Usar u64 elimina entradas negativas, mas não decide sozinho o significado de (0, 0). Na versão estendida, normalize ou rejeite valores negativos de forma explícita.

Confundir %, @rem e @mod

Com números sem sinal, % é suficiente. Para coeficientes assinados, @rem acompanha a divisão truncada, enquanto @mod produz um resultado não negativo quando o módulo é positivo — comportamento desejável ao normalizar um inverso modular.

Aplicações práticas

• Simplificação de frações: divida numerador e denominador pelo MDC.
• Coprimalidade: dois números são coprimos quando o MDC é 1.
• Criptografia e aritmética modular: o Euclides estendido encontra inversos usados por diversos algoritmos matemáticos.
• Equações diofantinas: a identidade de Bézout ajuda a decidir e construir soluções inteiras para ax + by = c.
• Sincronização de ciclos: o MMC encontra quando períodos diferentes voltam a coincidir.
• Programação competitiva: MDC e MMC aparecem em problemas de divisibilidade, frações, congruências e teoria dos números.

Qual versão usar?

Use a versão iterativa como padrão para calcular apenas o MDC: ela é curta, previsível e usa espaço constante. Use a recursiva quando a prioridade for ensinar a recorrência. Escolha o Euclides estendido quando você também precisar dos coeficientes de Bézout, de um inverso modular ou de uma solução para equações lineares inteiras.

Recursos relacionados

• Crivo de Eratóstenes — encontre todos os primos até um limite.
• Exponenciação rápida — calcule potências e potências modulares em tempo logarítmico.
• Fibonacci por matriz — outra aplicação de algoritmos logarítmicos.
• Testes em Zig — organize testes unitários e casos de borda em projetos reais.