O que é Congruência?

Exemplo 6.19 (A prova dos noves)

A compatibilidade com $+$ e $\times$ é um recurso de verificação tão antigo quanto o comércio. Como $10 \equiv 1 \pmod 9$, todo inteiro é congruente módulo $9$ à soma dos seus algarismos (demonstrado no Exercício 6.2). Para verificar a afirmação $1234 \times 567 = 699\,678$: as somas dos algarismos dão $1234 \equiv 1$ e $567 \equiv 18 \equiv 0 \pmod 9$, de modo que o produto deve ser $\equiv 1 \times 0 = 0$; e, de fato, $6 + 9 + 9 + 6 + 7 + 8 = 45 \equiv 0$. A verificação passa (e o produto está, de fato, correto). Se alguém tivesse relatado $699\,478$, a soma dos algarismos $43 \equiv 7 \not\equiv 0$ o condenaria instantaneamente. O teste é unilateral — ele apanha um erro a menos que o próprio erro seja um múltiplo de $9$ — o que é exatamente a lição dos pseudoprimos do Exemplo 6.24 em miniatura: verificações por congruência refutam, não certificam.

Exemplo 6.21 (Invertendo $7$ módulo $26$)

Como $\gcd(7, 26) = 1$, a classe de $7$ é invertível módulo $26$. Euclides estendido:

e depois, de trás para diante:

Portanto, $7 \times (-11) \equiv 1 \pmod{26}$, isto é, $7^{-1} \equiv -11 \equiv 15 \pmod{26}$; verificação: $7 \times 15 = 105 = 4 \times 26 + 1$. Com a inversa em mãos, qualquer congruência $7x \equiv c \pmod{26}$ resolve-se com uma multiplicação: $x \equiv 15c$. Essa inversão mecânica é o cavalo de batalha da aritmética modular — e dos protocolos de chave pública mencionados na Observação 6.27, em que os módulos têm centenas de algarismos, mas o algoritmo é exatamente este.

Exemplo 6.22 (Quando o coeficiente não é invertível)

Resolva $12x \equiv 8 \pmod{20}$. Aqui $\gcd(12, 20) = 4$, de modo que $12$ não é invertível módulo $20$ — mas a equação ainda é tratável. A congruência diz que $20 \mid 12x - 8$; dividindo a relação inteira por $4$ (divisor dos três ingredientes), ela é equivalente a $5 \mid 3x - 2$, isto é,

Agora, $\gcd(3, 5) = 1$ e $3^{-1} \equiv 2 \pmod 5$ ($3 \times 2 = 6 \equiv 1$), de modo que $x \equiv 4 \pmod 5$: as soluções são $x \equiv 4, 9, 14, 19 \pmod{20}$ — quatro classes módulo $20$, correspondendo ao mdc. (Se o lado direito não fosse divisível por $4$, digamos $12x \equiv 6 \pmod{20}$, não haveria solução alguma: o lado esquerdo é sempre $\equiv 0 \pmod 4$.) Forma geral: $ax \equiv b \pmod n$ tem solução se, e somente se, $\gcd(a, n) \mid b$, e nesse caso tem exatamente $\gcd(a, n)$ classes de soluções — divida tudo pelo mdc e inverta.