congruências

Em matemática, uma congruência é uma relação entre inteiros que descreve a igualdade de restos quando divididos por um inteiro m, denominado módulo. Dizer que a é congruente a b modulo m, escreve-se a ≡ b (mod m), significa que m divide a − b. Por exemplo, 17 ≡ 5 (mod 12) porque 17 − 5 = 12 é múltiplo de 12.

A relação de congruência é reflexiva, transitiva e, de modo útil, fechada sob adição, subtração e multiplicação: se a ≡ b (mod m) e c ≡ d (mod m), então a + c ≡ b + d (mod m) e ac ≡ bd (mod m). Consequentemente, diferentes inteiros podem representar o mesmo resíduo modulo m, formando classes de resíduos modulo m.

Resolver ax ≡ b (mod m) envolve o coeficiente a e o gcd g = gcd(a, m). Se g não divide b, não há solução. Se g divide b, existem exatamente g soluções modulo m; pode-se reduzir ao problema ax' ≡ b' (mod m') com a' = a/g, b' = b/g, m' = m/g, onde a' é invertível modulo m'. Então x ≡ b' (a')^{-1} (mod m'). As soluções são x0 + t m' para t = 0,1,...,g−1.

Quando os módulos m1, ..., mk são coprimos entre si, o sistema de congruências x ≡ ai (mod mi) tem uma solução única módulo M = ∏ mi. O teorema chinês das congruências garante a existência e a unicidade dessa solução nesses moldes.

As congruências aparecem amplamente na teoria dos números, na criptografia e em algoritmos que utilizam aritmética modular, incluindo geração de números pseudoaleatórios e verificação de resíduos.