Algoritmo de Euclides (MDC) em Rust

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.

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):

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

/// 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<i64> {
    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

=== 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):

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.

/// 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

/// 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.

/// 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

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.
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).
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.
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 — encontrar primos e fatorar números
Exponenciação Rápida em Rust — exponenciação modular para criptografia
Tipos Numéricos — i64, u64 e cuidados com overflow
Iterator — Iteradores — reduce para MDC de múltiplos números
Option — Valores Opcionais — representar ausência de inverso modular