Escrito por Lawrence Melo:
Notação não é uma parte da estrutura lógica da matemática: nós poderíamos chamar de $$V$$ o conjunto dos números reais, ou a operação de adição de #, e o significado dos resultados matemáticos seria o mesmo. Porém, uma boa notação pode ser incrivelmente sugestiva, levando aos resultados mais intuitivamente. Um grande passo foi dado quando Carl Friedrich Gauss notou que usamos a frase “$$a$$ deixa o mesmo resto que $$b$$ quando dividido por $$m$$”, e essa relação se comporta de forma similar à igualdade. Ele introduziu uma notação para isso, chamada de congruência.
Carl Friedrich Gauss (1777–1855).
Se $$a$$ e $$b$$ deixam o mesmo resto quando divididos por $$m$$ (onde a, b, m são inteiros e $$m > 0$$), então escrevemos:
$$a \equiv b \;(mod \; m)$$
(lê-se: $$a$$ é congruente à $$b$$ módulo $$m$$). uma maneira equivalente de dizer isso é $$m$$ é um divisor de $$b – a$$.
Essa notação sugere que nós queremos considerar essa relação uma análoga à igualdade. Realmente, muitas das propriedades de igualdade são válidas para congruências, se mantermos o $$m$$ fixo. Temos a reflexiva,
$$a \equiv a \; (mod \; m)$$
simetria,
$$a \equiv b \; (mod \; m)$$ $$\implies$$ $$b \equiv a \; (mod \; m)$$
e transitividade,
$$a \equiv b \; (mod \; m)$$, $$b \equiv c \; (mod \; m)$$ $$\implies$$ $$a \equiv c \; (mod \; m)$$
Essas propriedades são intuitivas se você se pensar que a congruência é apenas uma relação de igualdade entre os restos da divisão por $$m$$. Nós podemos fazer várias operação com congruências da mesma maneira que igualdade, se tivermos duas congruências módulo $$m$$,
$$a \equiv b \; (mod \; m)$$ e $$c \equiv d \; (mod \; m)$$
podemos somar subtrair e multiplicar as congruências,
$$a + c\equiv b + d \; (mod \; m)$$, $$a – c\equiv b – d \; (mod \; m)$$ e $$ac\equiv bd \; (mod \; m)$$
Um caso especial da multiplicação é que nós podemos multiplicar os dois lados de uma congruência pelo mesmo número: se $$a \equiv b \; (mod \; m)$$, então $$ka \equiv kb \; (mod \; m)$$, para todo $$k$$ inteiro.
Essas propriedades precisam ser provadas. Por hipótese $$a – b$$ e $$c – d$$ são divisíveis por $$m$$. Para ver que as congruências podem ser somadas, precisamos verificar que $$(a + c) – (b + d)$$ é divisível por $$m$$. Por fim, escrevemos da forma $$(a – b)+(c – d)$$, que mostra que a soma de dois inteiros divisíveis por $$m$$ também é divisível por $$m$$.
A prova que congruências podem ser subtraídas é análoga, mas multiplicação é um pouco diferente. Temos que mostrar que $$ac – bd$$ é divisível por $$m$$. Por fim, escrevemos essa $$ac – bd$$ na forma de
$$ac – bd = (a – b)c + b(c – d)$$
Note que $$a – b$$ e $$c – d$$ são divisíveis por $$m$$, então $$(a-b)c$$ e $$b(c – d)$$ também são, consequentemente sua soma também.
A notação de congruência é muito conveniente para formular varias afirmações e argumentos sobre divisibilidade. Por exemplo, o Teorema de Fermat pode ser escrito da seguinte forma: Se $$p$$ é primo e $$a$$ é um natural então
$$a^p \equiv a \;(mod \; p)$$