Divisibilidade e Algoritmo de Euclides

O algoritmo de Euclides tem mais de dois mil anos e continua sendo executado bilhões de vezes por dia — toda conexão TLS depende dele. É provavelmente o algoritmo não trivial mais antigo ainda em uso.

Divisibilidade

$a \mid b$ significa que existe $k$ inteiro com $b = ak$.

Divisão euclidiana: para $a$ e $b > 0$ existem únicos $q$ e $r$ com

$$a = bq + r, \qquad 0 \le r < b$$

Atenção a um detalhe de implementação: a definição matemática exige $0 \le r < b$, mas o operador % de C, Java e Rust devolve resto com o sinal do dividendo. -7 % 3 dá -1 nessas linguagens e 2 em Python. Em código criptográfico, esse detalhe já causou vulnerabilidades reais — normalize sempre com ((a % b) + b) % b.

MDC e MMC

$$\gcd(a,b)\cdot\operatorname{lcm}(a,b) = |ab|$$

Dois números com $\gcd(a,b)=1$ são coprimos.

Algoritmo de Euclides

Baseia-se na identidade $\gcd(a,b) = \gcd(b, a \bmod b)$:

def mdc(a, b):
    while b:
        a, b = b, a % b
    return a

Complexidade: $O(\log \min(a,b))$ divisões. O pior caso ocorre com números de Fibonacci consecutivos — resultado conhecido como teorema de Lamé, e um dos primeiros exemplos de análise de pior caso de um algoritmo.

O algoritmo é notavelmente eficiente: calcular o MDC de dois números de 2048 bits leva alguns milhares de operações, e não bilhões.

Algoritmo estendido

Além do MDC, devolve coeficientes da identidade de Bézout:

$$\gcd(a,b) = ax + by$$

def mdc_estendido(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = mdc_estendido(b, a % b)
    return g, y1, x1 - (a // b) * y1

Esta é a peça mais importante da página, porque resolve o inverso modular. Se $\gcd(a,m)=1$, então $ax + my = 1$, e reduzindo módulo $m$:

$$ax \equiv 1 \pmod m$$

Logo $x$ é o inverso de $a$ módulo $m$.

def inverso_modular(a, m):
    g, x, _ = mdc_estendido(a % m, m)
    if g != 1:
        raise ValueError(f'{a} não é invertível módulo {m}')
    return x % m

O inverso modular é o que permite "dividir" em aritmética modular, e é usado na geração de chaves RSA, em curvas elípticas e em códigos corretores.

Onde aparece em computação

Frações. Reduzir $\frac{a}{b}$ à forma irredutível é dividir ambos pelo MDC.

Criptografia. O expoente privado do RSA é o inverso modular do expoente público.

Sincronização. Dois eventos com períodos $p$ e $q$ coincidem a cada $\operatorname{lcm}(p,q)$.

Hashing. Tabelas com sondagem por incremento fixo só percorrem todas as posições se o incremento for coprimo com o tamanho — motivo pelo qual tamanhos primos são preferidos.

Gráficos. O algoritmo de Bresenham para traçar retas é aparentado com Euclides.

Exemplo trabalhado

Calcular $\gcd(252, 198)$ e a identidade de Bézout.

Passo	$a$	$b$	$q$	$r$
1	252	198	1	54
2	198	54	3	36
3	54	36	1	18
4	36	18	2	0

Logo $\gcd = 18$. Voltando pelas equações:

$$18 = 54 - 36 = 54 - (198 - 3\cdot54) = 4\cdot54 - 198$$ $$= 4(252-198) - 198 = 4\cdot252 - 5\cdot198$$

Conferindo: $1008 - 990 = 18$. Correto.

Erros comuns

• Confiar no sinal de % em linguagens que seguem a convenção do C.
• Calcular inverso quando ele não existe. Exige $\gcd(a,m)=1$.
• Usar fatoração para calcular MDC. Fatorar é muito mais caro que Euclides.
• Recursão profunda no algoritmo estendido para números enormes; prefira versão iterativa.
• Estouro de inteiro ao calcular MMC como $ab/\gcd$; divida antes de multiplicar.

Leituras recomendadas

• Hardy e Wright, An Introduction to the Theory of Numbers — o clássico.
• Shoup, A Computational Introduction to Number Theory and Algebra — orientado a computação e gratuito no site do autor.
• Knuth, TAOCP volume 2, seção 4.5.2 — a análise definitiva do algoritmo de Euclides.

G. H. Hardy and E. M. Wright (2008). An Introduction to the Theory of Numbers. Oxford University Press. DOI: 10.1093/oso/9780199219858.001.0001. Victor Shoup (2009). A Computational Introduction to Number Theory and Algebra. Cambridge University Press. DOI: 10.1017/cbo9780511814549. Donald E. Knuth (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley. Página oficial.

Referências

1. G. H. Hardy; E. M. Wright (2008). An Introduction to the Theory of Numbers. Oxford University Press.
2. Victor Shoup (2009). A Computational Introduction to Number Theory and Algebra. Cambridge University Press.
3. Donald E. Knuth (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley.