--- title: "Algoritmo de Euclides em Zig: MDC, MMC e Inverso Modular" url: "https://ziglang.com.br/algoritmos/euclides-mdc/" markdown_url: "https://ziglang.com.br/algoritmos/euclides-mdc.MD" description: "Aprenda a calcular MDC em Zig com o algoritmo de Euclides. Inclui versões iterativa, recursiva e estendida, MMC, testes e inverso modular." date: "2026-02-21" author: "Zig Brasil" --- # Algoritmo de Euclides em Zig: MDC, MMC e Inverso Modular Aprenda a calcular MDC em Zig com o algoritmo de Euclides. Inclui versões iterativa, recursiva e estendida, MMC, testes e inverso modular. # 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. ```zig 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: ```text 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)`: ```text 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. | Iteração | `a` | `b` | `a % b` | |---:|---:|---:|---:| | 1 | 252 | 105 | 42 | | 2 | 105 | 42 | 21 | | 3 | 42 | 21 | 0 | ## Implementação iterativa em Zig Esta versão aceita inteiros sem sinal. Assim, o contrato fica simples: qualquer entrada `u64` é válida, inclusive zero. ```zig /// 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: | Entrada | Resultado | Motivo | |---|---:|---| | `mdc(48, 18)` | 6 | caso comum | | `mdc(18, 48)` | 6 | a ordem não altera o MDC | | `mdc(17, 13)` | 1 | os números são coprimos | | `mdc(0, 9)` | 9 | todo divisor de 9 também divide zero | | `mdc(9, 0)` | 9 | condição de parada imediata | | `mdc(0, 0)` | 0 | convenção útil em código; matematicamente é indeterminado | 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: ```zig 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: ```zig 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: ```zig 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: ```bash 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: ```text a × x + b × y = MDC(a, b) ``` Para 252 e 105: ```text 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`. ```zig 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: ```text 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. ```zig 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. ```zig 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. ```zig 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 | Operação | Tempo | Espaço | |---|---|---| | MDC iterativo | `O(log(min(a, b)))` | `O(1)` | | MDC recursivo | `O(log(min(a, b)))` | `O(log(min(a, b)))` | | Euclides estendido | `O(log(min(a, b)))` | `O(log(min(a, b)))` nesta versão | | MMC de dois números | `O(log(min(a, b)))` | `O(1)` | | MDC de `n` números | soma dos custos de cada par | `O(1)` na versão iterativa | 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: ```zig // 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](/algoritmos/crivo-eratostenes/) — encontre todos os primos até um limite. - [Exponenciação rápida](/algoritmos/exponenciacao-rapida/) — calcule potências e potências modulares em tempo logarítmico. - [Fibonacci por matriz](/algoritmos/fibonacci-matrix/) — outra aplicação de algoritmos logarítmicos. - [Testes em Zig](/artigos/zig-testes-guia-completo/) — organize testes unitários e casos de borda em projetos reais.