1. Equação de Congruência Linear ax ≡ b (mod m):
- Existência de Soluções:A equação tem solução se e somente se mdc(a, m) divide b (ou seja, b é divisível por mdc(a, m))
- Número de Soluções:Se soluções existirem, há d = mdc(a, m) soluções distintas módulo m
- Método de Solução:
- Calcular d = mdc(a, m)
- Verificar se d divide b; se não, não há solução
- Dividir ambos os lados da equação por d: (a/d)x ≡ (b/d) (mod m/d)
- Usar o Algoritmo de Euclides Estendido para encontrar o inverso de a/d módulo m/d
- Calcular x₀ = a' × (b/d) mod (m/d)
- Solução geral: x = x₀ + k(m/d), onde k = 0, 1, ..., d-1
2. Equação de congruência exponencial a^x ≡ b (mod m) (Problema do Logaritmo Discreto):
- Descrição do problema:Dados a, b, m, encontre o menor inteiro não negativo x tal que a^x ≡ b (mod m)
- Existência de Soluções:
- Se mdc(a, m) = 1 e b é um elemento do grupo cíclico gerado por a módulo m, então existe solução
- Método de verificação: enumere potências de a até encontrar b ou completar um ciclo completo
- Método de Solução:
- Busca por força bruta em um pequeno intervalo:Enumere x = 0, 1, 2, ... até encontrar uma solução ou atingir o limite de busca
- Algoritmo Baby-step Giant-step:Complexidade de tempo O(√m), adequado para problemas de médio porte
- Algoritmo de Pollard's rho:Aplicável para módulos primos grandes
- Periodicidade:Se x₀ é uma solução, então x = x₀ + kφ(m) também é uma solução (onde φ(m) é a função totiente de Euler)
3. Cenários de aplicação:
- Criptografia:RSA, troca de chaves Diffie-Hellman, criptografia ElGamal
- Pesquisa em teoria dos números:Raízes Primitivas, Resíduos Quadráticos, Teorema Chinês do Resto
- Geração de Números Aleatórios:Gerador Linear Congruencial (LCG)
- Funções Hash:Aplicação da Aritmética Modular em Tabelas Hash
- Programação Competitiva:Exponenciação Rápida, Inverso Modular, Problemas de Teoria dos Números
Complexidade do Algoritmo:
- Equações de Congruência Linear:O(log m) (Complexidade do Algoritmo de Euclides Estendido)
- Equações de Congruência Exponencial (Força Bruta):O(n), onde n é o limite de busca
- Equações de Congruência Exponencial (BSGS):O(√m), requer espaço extra
Teoremas Importantes:
- Teorema de Bézout:A equação ax + my = mdc(a, m) sempre tem soluções inteiras
- Pequeno Teorema de Fermat:Se p é primo e mdc(a, p) = 1, então a^(p-1) ≡ 1 (mod p)
- Teorema de Euler:Se mdc(a, m) = 1, então a^φ(m) ≡ 1 (mod m)
- Teorema Chinês do Resto:Pode resolver sistemas de congruências