--- title: "Algoritmo de Euclides (MDC) em Rust" url: "https://rustlang.com.br/algoritmos/gcd-euclides/" markdown_url: "https://rustlang.com.br/algoritmos/gcd-euclides.MD" description: "Implemente o Algoritmo de Euclides para MDC em Rust. Versão estendida, inverso modular, MMC e aplicações em criptografia." date: "2026-02-24" author: "Equipe Rust Brasil" --- # Algoritmo de Euclides (MDC) em Rust Implemente o Algoritmo de Euclides para MDC em Rust. Versão estendida, inverso modular, MMC e aplicações em criptografia. O **Algoritmo de Euclides** é um dos algoritmos mais antigos que ainda é amplamente utilizado, datando dos Elementos de Euclides por volta de 300 a.C. Ele calcula o **Máximo Divisor Comum** (MDC, ou GCD em inglês) de dois números inteiros de forma extraordinariamente eficiente, usando apenas divisões sucessivas. O MDC de dois números a e b é o maior inteiro que divide ambos sem deixar resto. O algoritmo é fundamental em diversas áreas: simplificação de frações, criptografia RSA (cálculo de inverso modular), aritmética modular, e resolução de equações diofantinas. Sua versão estendida permite encontrar os coeficientes da identidade de Bezout, abrindo portas para aplicações em criptografia e teoria dos números. ## Como Funciona O algoritmo se baseia em uma observação simples mas poderosa: `mdc(a, b) = mdc(b, a mod b)`. Repetindo essa operação até que o segundo número se torne zero, o primeiro número restante é o MDC. ```text Calcular MDC(252, 105): Passo 1: mdc(252, 105) 252 = 2 × 105 + 42 → mdc(105, 42) Passo 2: mdc(105, 42) 105 = 2 × 42 + 21 → mdc(42, 21) Passo 3: mdc(42, 21) 42 = 2 × 21 + 0 → mdc(21, 0) Passo 4: mdc(21, 0) = 21 ← segundo argumento é 0, retorna 21 Resultado: MDC(252, 105) = 21 Verificação: 252 = 21 × 12, 105 = 21 × 5 ✓ Visualização do processo: 252 │ 105 │───── 252 = 2 × 105 + 42 quociente: 2, resto: 42 │ 105 │ 42 │───── 105 = 2 × 42 + 21 quociente: 2, resto: 21 │ 42 │ 21 │───── 42 = 2 × 21 + 0 quociente: 2, resto: 0 ← FIM │ MDC = 21 ``` O **Algoritmo de Euclides Estendido** encontra, além do MDC, os coeficientes x e y tais que `a*x + b*y = mdc(a, b)` (Identidade de Bezout): ```text Euclides Estendido para MDC(252, 105): Fase descendente (mesma que o algoritmo básico): 252 = 2 × 105 + 42 105 = 2 × 42 + 21 42 = 2 × 21 + 0 → MDC = 21 Fase ascendente (reconstruir x e y): 21 = 105 - 2 × 42 42 = 252 - 2 × 105 ↓ substituindo: 21 = 105 - 2 × (252 - 2 × 105) 21 = 105 - 2 × 252 + 4 × 105 21 = 5 × 105 + (-2) × 252 Resultado: 252 × (-2) + 105 × 5 = 21 = MDC(252, 105) ✓ x = -2, y = 5 Verificação: 252 × (-2) + 105 × 5 = -504 + 525 = 21 ✓ ``` ## Complexidade | Operação | Tempo | Espaço | |----------|-------|--------| | MDC (Euclides) | O(log(min(a,b))) | O(1) iterativo, O(log n) recursivo | | MDC estendido | O(log(min(a,b))) | O(log n) recursivo | | MMC | O(log(min(a,b))) | O(1) | | Inverso modular | O(log m) | O(log m) | - **O(log(min(a,b))):** o número de passos é proporcional ao número de dígitos do menor número. No pior caso (números de Fibonacci consecutivos), são necessários exatamente log_phi(n) passos, onde phi é a razão áurea. - **Pior caso:** os números de Fibonacci são o pior caso para o algoritmo de Euclides. MDC(F_{n+1}, F_n) exige n passos. ## Implementação em Rust ```rust /// MDC pelo Algoritmo de Euclides (versão iterativa). /// Funciona para quaisquer inteiros não negativos. fn mdc(mut a: u64, mut b: u64) -> u64 { while b != 0 { let temp = b; b = a % b; a = temp; } a } /// MDC pelo Algoritmo de Euclides (versão recursiva). fn mdc_recursivo(a: u64, b: u64) -> u64 { if b == 0 { a } else { mdc_recursivo(b, a % b) } } /// Mínimo Múltiplo Comum usando a relação MMC(a,b) = a * b / MDC(a,b). /// Usa divisão antes da multiplicação para evitar overflow. fn mmc(a: u64, b: u64) -> u64 { if a == 0 || b == 0 { return 0; } a / mdc(a, b) * b } /// Algoritmo de Euclides Estendido. /// Retorna (mdc, x, y) tais que a*x + b*y = mdc(a, b). fn mdc_estendido(a: i64, b: i64) -> (i64, i64, i64) { if b == 0 { return (a, 1, 0); } let (g, x1, y1) = mdc_estendido(b, a % b); let x = y1; let y = x1 - (a / b) * y1; (g, x, y) } /// Inverso modular de a módulo m. /// Retorna Some(x) onde a*x ≡ 1 (mod m), ou None se não existir. /// O inverso existe se e somente se mdc(a, m) = 1. fn inverso_modular(a: i64, m: i64) -> Option { let (g, x, _) = mdc_estendido(a, m); if g != 1 { None // a e m não são coprimos } else { // Garante resultado positivo Some(((x % m) + m) % m) } } fn main() { // MDC básico println!("=== MDC (Algoritmo de Euclides) ==="); let pares = [(252, 105), (48, 18), (100, 75), (17, 13), (0, 5)]; for (a, b) in pares { println!("MDC({}, {}) = {}", a, b, mdc(a, b)); } // MMC println!("\n=== MMC (Mínimo Múltiplo Comum) ==="); let pares_mmc = [(12, 18), (7, 5), (100, 75)]; for (a, b) in pares_mmc { println!("MMC({}, {}) = {}", a, b, mmc(a, b)); } // Euclides Estendido println!("\n=== Euclides Estendido ==="); let (g, x, y) = mdc_estendido(252, 105); println!("MDC(252, 105) = {}", g); println!("252 * ({}) + 105 * ({}) = {}", x, y, 252 * x + 105 * y); // Inverso modular println!("\n=== Inverso Modular ==="); let casos = [(3, 7), (5, 13), (7, 26), (6, 9)]; for (a, m) in casos { match inverso_modular(a, m) { Some(inv) => println!("Inverso de {} mod {} = {} (verificação: {} * {} mod {} = {})", a, m, inv, a, inv, m, (a * inv) % m), None => println!("Inverso de {} mod {} não existe (mdc={} ≠ 1)", a, m, mdc(a as u64, m as u64)), } } } ``` ## Exemplo de Execução ```text === MDC (Algoritmo de Euclides) === MDC(252, 105) = 21 MDC(48, 18) = 6 MDC(100, 75) = 25 MDC(17, 13) = 1 MDC(0, 5) = 5 === MMC (Mínimo Múltiplo Comum) === MMC(12, 18) = 36 MMC(7, 5) = 35 MMC(100, 75) = 300 === Euclides Estendido === MDC(252, 105) = 21 252 * (-2) + 105 * (5) = 21 === Inverso Modular === Inverso de 3 mod 7 = 5 (verificação: 3 * 5 mod 7 = 1) Inverso de 5 mod 13 = 8 (verificação: 5 * 8 mod 13 = 1) Inverso de 7 mod 26 = 15 (verificação: 7 * 15 mod 26 = 1) Inverso de 6 mod 9 não existe (mdc=3 ≠ 1) ``` Trace detalhado do MDC(48, 18): ```text mdc(48, 18): 48 = 2 × 18 + 12 → mdc(18, 12) mdc(18, 12): 18 = 1 × 12 + 6 → mdc(12, 6) mdc(12, 6): 12 = 2 × 6 + 0 → mdc(6, 0) mdc(6, 0): b == 0, retorna 6 Total: 3 passos (3 divisões) ``` ## Variações e Otimizações ### 1. MDC Binário (Algoritmo de Stein) Usa apenas subtrações e shifts (divisões por 2), evitando divisões que são mais lentas em hardware. ```rust /// MDC Binário (Algoritmo de Stein) — usa apenas subtração e shift. /// Mais eficiente que Euclides em hardware sem divisão rápida. fn mdc_binario(mut a: u64, mut b: u64) -> u64 { if a == 0 { return b; } if b == 0 { return a; } // Encontra o maior fator potência de 2 comum let shift = (a | b).trailing_zeros(); // Remove fatores de 2 de a a >>= a.trailing_zeros(); loop { // Remove fatores de 2 de b b >>= b.trailing_zeros(); // Garante a <= b if a > b { std::mem::swap(&mut a, &mut b); } b -= a; if b == 0 { return a << shift; } } } fn main() { let testes = [(48, 18), (252, 105), (1071, 462), (0, 42)]; for (a, b) in testes { let g1 = mdc_binario(a, b); println!("MDC_binário({}, {}) = {}", a, b, g1); } } ``` ### 2. MDC de Múltiplos Números e Simplificação de Frações ```rust /// MDC de um vetor de números. fn mdc_multiplos(numeros: &[u64]) -> u64 { numeros.iter().copied().reduce(mdc).unwrap_or(0) } /// MDC básico. fn mdc(mut a: u64, mut b: u64) -> u64 { while b != 0 { let temp = b; b = a % b; a = temp; } a } /// MMC de um vetor de números. fn mmc_multiplos(numeros: &[u64]) -> u64 { numeros.iter().copied().reduce(|a, b| a / mdc(a, b) * b).unwrap_or(0) } /// Fração simplificada. #[derive(Debug)] struct Fracao { numerador: i64, denominador: i64, } impl Fracao { fn nova(num: i64, den: i64) -> Self { assert!(den != 0, "Denominador não pode ser zero"); let g = mdc(num.unsigned_abs(), den.unsigned_abs()) as i64; let sinal = if den < 0 { -1 } else { 1 }; Fracao { numerador: sinal * num / g, denominador: sinal * den / g, } } fn somar(&self, outra: &Fracao) -> Fracao { let num = self.numerador * outra.denominador + outra.numerador * self.denominador; let den = self.denominador * outra.denominador; Fracao::nova(num, den) } fn multiplicar(&self, outra: &Fracao) -> Fracao { Fracao::nova( self.numerador * outra.numerador, self.denominador * outra.denominador, ) } } impl std::fmt::Display for Fracao { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { if self.denominador == 1 { write!(f, "{}", self.numerador) } else { write!(f, "{}/{}", self.numerador, self.denominador) } } } fn main() { // MDC de múltiplos números let nums = vec![12, 18, 24, 36]; println!("MDC({:?}) = {}", nums, mdc_multiplos(&nums)); // MMC de múltiplos números let nums2 = vec![4, 6, 10]; println!("MMC({:?}) = {}", nums2, mmc_multiplos(&nums2)); // Frações simplificadas let f1 = Fracao::nova(6, 8); println!("\n6/8 simplificado = {}", f1); let f2 = Fracao::nova(15, 25); println!("15/25 simplificado = {}", f2); let soma = f1.somar(&f2); println!("{} + {} = {}", Fracao::nova(6, 8), Fracao::nova(15, 25), soma); let produto = Fracao::nova(6, 8).multiplicar(&Fracao::nova(15, 25)); println!("{} × {} = {}", Fracao::nova(6, 8), Fracao::nova(15, 25), produto); } ``` ### 3. Equação Diofantina Linear Encontrar soluções inteiras para `ax + by = c` usando o Euclides Estendido. ```rust /// Resolve a equação diofantina ax + by = c. /// Retorna Some((x0, y0)) se existir solução, None caso contrário. /// A solução geral é: x = x0 + k*(b/g), y = y0 - k*(a/g) para qualquer inteiro k. fn resolver_diofantina(a: i64, b: i64, c: i64) -> Option<(i64, i64)> { if a == 0 && b == 0 { return if c == 0 { Some((0, 0)) } else { None }; } let (g, x, y) = mdc_estendido(a.abs(), b.abs()); // Solução existe sse g divide c if c % g != 0 { return None; } let fator = c / g; let mut x0 = x * fator; let mut y0 = y * fator; // Ajustar sinais if a < 0 { x0 = -x0; } if b < 0 { y0 = -y0; } Some((x0, y0)) } fn mdc_estendido(a: i64, b: i64) -> (i64, i64, i64) { if b == 0 { return (a, 1, 0); } let (g, x1, y1) = mdc_estendido(b, a % b); (g, y1, x1 - (a / b) * y1) } fn main() { // Resolver 3x + 5y = 1 match resolver_diofantina(3, 5, 1) { Some((x, y)) => { println!("3x + 5y = 1"); println!(" Solução: x={}, y={}", x, y); println!(" Verificação: 3*({}) + 5*({}) = {}", x, y, 3*x + 5*y); println!(" Solução geral: x = {} + 5k, y = {} - 3k", x, y); } None => println!("Sem solução"), } // Resolver 6x + 9y = 12 println!(); match resolver_diofantina(6, 9, 12) { Some((x, y)) => { println!("6x + 9y = 12"); println!(" Solução: x={}, y={}", x, y); println!(" Verificação: 6*({}) + 9*({}) = {}", x, y, 6*x + 9*y); } None => println!("6x + 9y = 12: Sem solução"), } // Resolver 6x + 9y = 11 (sem solução, pois mdc(6,9)=3 não divide 11) println!(); match resolver_diofantina(6, 9, 11) { Some((x, y)) => println!("Solução: x={}, y={}", x, y), None => println!("6x + 9y = 11: Sem solução (mdc(6,9)=3 não divide 11)"), } } ``` ## Aplicações Práticas - **Criptografia RSA:** o inverso modular calculado pelo Euclides Estendido é essencial para determinar a chave privada a partir da chave pública. - **Simplificação de frações:** dividir numerador e denominador pelo MDC produz a fração irredutível. - **MMC para sincronização:** determinar quando eventos cíclicos com períodos diferentes voltam a coincidir (engrenagens, semáforos, agendamento). - **Equações diofantinas:** resolver problemas de combinatória como "de quantas formas posso pagar R$ 17 usando moedas de R$ 3 e R$ 5?". - **Aritmética modular:** operações em criptografia, hashing e geração de números pseudo-aleatórios. - **Computação gráfica:** algoritmo de Bresenham para desenhar linhas usa conceitos relacionados ao MDC. ## Comparação com Alternativas | Método | Tempo | Quando usar | |---|---|---| | Euclides iterativo | O(log n) | MDC simples, mais eficiente | | Euclides recursivo | O(log n) | Mais legível, mesma complexidade | | Euclides estendido | O(log n) | Quando precisa de x, y (Bezout) | | MDC binário (Stein) | O(log n) | Hardware sem divisão rápida | | Fatoração + MDC | O(sqrt(n)) | Quando já tem a fatoração | | MDC via iterador (reduce) | O(k log n) | MDC de k números | ## Exercícios Práticos 1. **MDC de polinômios:** Implemente o algoritmo de Euclides para polinômios representados como vetores de coeficientes. O "resto da divisão" é substituído pela divisão polinomial. 2. **Frações contínuas:** Usando os quocientes do algoritmo de Euclides, construa a representação em fração contínua de um número racional. Exemplo: 252/105 = [2; 2, 2] pois 252/105 = 2 + 1/(2 + 1/2). 3. **Teorema Chinês do Resto:** Dados x ≡ a1 (mod m1) e x ≡ a2 (mod m2), encontre x mod (m1*m2) usando o Euclides Estendido. Generalize para k congruências. 4. **Contagem de pontos em segmento:** Quantos pontos com coordenadas inteiras existem no segmento de (0,0) a (a,b), excluindo as extremidades? A resposta é mdc(a,b) - 1. Verifique isso computacionalmente para vários valores de a e b. ## Veja Também - [Crivo de Eratóstenes em Rust](/algoritmos/crivo-eratostenes/) — encontrar primos e fatorar números - [Exponenciação Rápida em Rust](/algoritmos/exponenciacao-rapida/) — exponenciação modular para criptografia - [Tipos Numéricos](/stdlib/tipos-numericos/) — i64, u64 e cuidados com overflow - [Iterator — Iteradores](/stdlib/iterator/) — reduce para MDC de múltiplos números - [Option — Valores Opcionais](/stdlib/option/) — representar ausência de inverso modular