Matemática Computacional 01 - Congruências

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)$