Teoria dos Números · Congruências · Gauss

Aritmética Modular e Congruências

A matemática do relógio — onde 13 = 1, primos ganham superpoderes e toda a criptografia moderna repousa.

✦ Congruência Modular
a ≡ b (mod n)  ⟺  n | (a − b)
Propriedades — preservadas pela congruência
a ≡ b  e  c ≡ d  ⟹  a+c ≡ b+d  e  a·c ≡ b·d (mod n)
Carl Friedrich Gauss sistematizou a aritmética modular nas Disquisitiones Arithmeticae (1801). É a linguagem da criptografia, dos códigos de verificação e da teoria dos números modernos.
1
Fundamentos

Definição e Intuição

A aritmética modular é a "aritmética do relógio": assim como 13h = 1h (mod 12), na matemática dizemos que dois números são congruentes módulo n se têm o mesmo resto na divisão por n.

a ≡ b (mod n)  ⟺  n | (a−b)  ⟺  a mod n = b mod n
Visualização — relógio mod 12
Módulo n =
2
Propriedades

A Álgebra das Congruências

A aritmética modular respeita as quatro operações básicas — com uma exceção importante na divisão.

🔷 Propriedades provadas
  1. Adição: Se a ≡ b e c ≡ d (mod n), então a+c ≡ b+d (mod n).
    Prova: n|(a−b) e n|(c−d) ⟹ n|((a+c)−(b+d)) ✓
  2. Subtração: a−c ≡ b−d (mod n). Analogamente.
  3. Multiplicação: a·c ≡ b·d (mod n).
    Prova: a·c − b·d = a(c−d) + d(a−b), e n divide ambos os termos.
  4. Potenciação: aᵏ ≡ bᵏ (mod n) para k ∈ ℕ. Segue por indução da multiplicação.
  5. Divisão — apenas quando mdc(c,n)=1: a·c ≡ b·c (mod n) ⟹ a ≡ b (mod n). Se mdc(c,n) > 1, isso pode falhar.
⚠ Cuidado com divisão

6 ≡ 2 (mod 4). Dividindo por 2: 3 ≡ 1 (mod 4)? Não! 3 mod 4 = 3 ≠ 1. A divisão só funciona quando o divisor é coprimo com o módulo.

3
Inverso Modular

Divisão em ℤₙ

O inverso modular de a módulo n é o número a⁻¹ tal que a·a⁻¹ ≡ 1 (mod n). Existe se e somente se mdc(a, n) = 1.

Encontrar a⁻¹: Algoritmo de Euclides Estendido

Exemplo: inverso de 3 módulo 7. Procuramos x tal que 3x ≡ 1 (mod 7):

3·1=3, 3·2=6, 3·3=9≡2, 3·4=12≡5, 3·5=15≡1 ✓

Logo 3⁻¹ ≡ 5 (mod 7). Verificação: 3·5 = 15 = 2·7 + 1 ≡ 1 (mod 7) ✓

Aplicação — resolução de equações lineares modulares

Para resolver 3x ≡ 4 (mod 7): multiplicar ambos os lados pelo inverso 3⁻¹ = 5:

x ≡ 5·4 ≡ 20 ≡ 6 (mod 7)
4
Teorema Chinês dos Restos

TRC — Sistemas de Congruências

O Teorema Chinês dos Restos (Sun Tzu, ~300 d.C.) garante que sistemas de congruências com módulos coprimos têm solução única:

x ≡ a₁ (mod n₁),   x ≡ a₂ (mod n₂),   …

Se mdc(nᵢ, nⱼ) = 1 para i ≠ j, existe solução única módulo n₁·n₂·····nₖ.

Exemplo clássico

x ≡ 2 (mod 3) e x ≡ 3 (mod 5). Candidatos: x = 2, 5, 8, 11, 14, 17, 23…
Verificação: 11 mod 3 = 2 ✓ e 11 mod 5 = 1 — ops. Ajustando: 8 mod 3 = 2 ✓ e 8 mod 5 = 3 ✓. Solução: x ≡ 8 (mod 15).

⚡ Aplicação — calendário e ciclos

O calendário Maia usava ciclos de 260 e 365 dias. Pelo TRC, os dois ciclos se sincronizam exatamente a cada 260·365/mdc(260,365) = 18.980 dias ≈ 52 anos — o "Século Maia".

5
Interativo

Calculadora Modular

Calcule a mod n, aᵏ mod n e o inverso de a módulo n.

Configure e clique em Calcular.