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 seja, a e b deixam o mesmo resto 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 ∈ ℕ*
• a^p ≡ a (mod p) com p primo. → Pequeno Teorema de Fermat
• Se p ∤ a, então p | a^{p – 1} – 1, com p primo
• se p é primo, então (p – 1)! ≡ – 1 (mod p) → Teorema de Wilson

Classes de congruência

Classes de congruência são conjuntos de números inteiros que são “congruentes entre si” módulo 𝑚, ou seja, que deixam o mesmo resto quando divididos por um número inteiro 𝑚.

Definição formal

Dado um número inteiro m > 1 (o módulo), e um inteiro a, a classe de congruência de a módulo m é o conjunto de todos os inteiros que são congruentes a a módulo m. Notamos isso por:

[a]_m = {x ∈ Z | x ≡ a (mod m)}

ou seja, é o conjunto de todos os inteiros x tais que x – a é múltiplo de m.

Exemplo

Se m = 5, temos as seguintes classes de congruência possíveis:

[0]₅ = {…, -10, -5, 0, 5, 10, 15, …} deixam resto 0 na divisão por 5.
[1]₅ = {…, -9, -4, 1, 6, 11, …} deixam resto 1 na divisão por 5.
[2]₅ = {…, -8, -3, 2, 7, 12, …} deixam resto 2 na divisão por 5.
[3]₅ = {…, -7, -2, 3, 8, 13, …} deixam resto 3 na divisão por 5.
[4]₅ = {…, -6, -1, 4, 9, 14 …} deixam resto 4 na divisão por 5.

Qualquer número inteiro pertence a uma dessas 5 classes. Por exemplo, o número 17 pertence a classe [2]₅, porque 17 ≡ 2 (mod 5).

Isso nos leva a querer entender o que são conjuntos completos de resíduos.
Note que o conjunto S={0,1,2,3,4} é um conjunto completo de resíduos módulo 5. Da mesma forma o conjunto T = {5,11,22,33,44} também é um conjunto completo de resíduos módulo 5.
Percebemos que um conjunto de resíduos módulo n possui exatamente n elementos.

Portanto, um conjunto M = {r₀, r₁, …, r_k} é um sistema completo de resíduos módulo n se:

• r_i ≡ r_j (mod n) ⇔ i = j, ou seja, todos os elementos dois a dois são incongruentes módulo n.
• Para qualquer inteiro a, tivermos a ≡ r_i (mod n) para algum r_i de M.

Congruência linear

Chamamos de congruência linear a toda equação da forma ax ≡ b (mod m). Todo inteiro x₀, tal que ax₀ ≡ b (mod m) é uma solução da equação ax ≡ b (mod m).

Se x₀ é uma solução da equação ax ≡ b (mod m), então m | (ax₀ – b), logo ax₀ – b = my₀. Fazendo algumas manipulações chegamos em ax₀ + (-m)y₀ = b. Por fim, encontrar a solução da equação ax ≡ b (mod m) significa encontrar a solução da equação diofantina ax₀ + (-m)y₀ = b. E já sabemos de textos anteriores que uma equação diofantina tem solução se o mdc dos seus coeficientes dividir o termo independente, ou seja, se o mdc(a,-m) = mdc(a,m) dividir b.