Livro de Matemática

As congruências lineares são fundamentais na teoria dos números porque:

1. São a base da aritmética modular
   Elas permitem resolver equações em que estamos interessados apenas no resto da divisão. Isso é crucial para trabalhar com ciclos, padrões repetitivos e propriedades dos números inteiros.
2. Aplicações em criptografia
   Congruências lineares aparecem:
   • no algoritmo RSA (criptografia assimétrica),
   • na geração de chaves públicas e privadas,
   • no cálculo de inversos modulares, que é essencial para decodificar mensagens com segurança.
3. Usadas em algoritmos e teoria computacional
   • Algoritmos de divisão rápida,
   • Algoritmos para encontrar mínimos múltiplos comuns ou máximo divisor comum,
   • Verificação de propriedades em programação competitiva ou matemática computacional.
4. Aplicações em problemas do cotidiano
   Elas ajudam a resolver:
   • Problemas de sincronização de horários,
   • Cálculos de códigos de verificação (ex: CPF, ISBN),
   • Questões envolvendo ciclos, rodízios, padrões periódicos.

Primeiras definições

Se n ∈ ℤ* tal que n > 1, os números a, b, ∈ ℤ são congruentes módulo n se n | (a – b).

Lê-se a é congruente a b módulo n, ou a deixa resto b na divisão por n.

Exemplos:

9 ≡ 5 (mod 2) → 2 | 9 – 5
23 ≡ 11 (mod 6) → 6 | 23 – 11

Propriedades

• Reflexividade: a ≡ a (mod n)
• Simetria: se a ≡ b (mod n), então b ≡ a (mod n)
• Transitividade: se a ≡ b (mod n) e b ≡ c (mod n), então a ≡ c (mod n)
• Se a ≡ b (mod n) e c ≡ d (mod n), então a + c ≡ b + d (mod n)
• Se a ≡ b (mod n) e c ≡ d (mod n), então ac ≡ bd (mod n)
• Se a ≡ b (mod n), então a^m ≡ b^m (mod n) ∀ n ∈ ℕ*