congruencia

Congruência pesquisa 4. Congruência
Introdução
O conceito de congruência bem como sua notação foi apresentado pelo matemático alemão Karl Friedrich Gauss (1777 – 1855), em sua obra Disquisitione arithmeticae em 1801. Hoje a congruência é um poderoso instrumento da teoria dos números.
Antes de apresentarmos as definições e propriedades sobre congruência, vamos desenvolver dois exemplos:

Exemplo 1. Se hoje é terça-feira, que dia da semana será daqui a 1520 dias?
Para organizar o raciocínio, indiquemos por 0 o dia de hoje, por 1 o dia de amanhã, e assim por diante. Temos assim o seguinte quadro:
TERÇA

QUARTA

QUINTA

SEXTA

SÁBADO

DOMINGO

SEGUNDA

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

Nosso problema se resume em saber em que coluna se encontra o número 1520.
Para isso observe que dois números pertencem a uma mesma coluna se sua diferença é divisível por 7, ou seja, é um múltiplo de 7. Assim, supondo que 1520 esteja na coluna encabeçada pelo número r, com 0  r  6, segue que 1520 – r = 7q para algum inteiro q, ou seja 1520 = 7q + r. Logo, basta efetuarmos a divisão de 1520 por 7 e observar o resto. Como na divisão de 1520 por 7 temos resto 1, segue que 1520 está na segunda coluna, ou seja, daqui a 1520 dias será uma quarta-feira.

Exemplo 2. (OBMEP) A, B, C, D, E, F, G e H são os fios de apoio que uma aranha utiliza para construir sua teia, conforme indica a figura abaixo. A aranha continua seu trabalho. Sobre qual fio de apoio estará o número 118?

Essas ideias motivaram a seguinte definição:
Definição. Sejam a e b inteiros que deixam o mesmo resto quando divididos por um inteiro m > 0.
Então podemos dizer que “a e b são congruentes módulo m”.
Notação: a  b (mod m)

Uma definição equivalente para a congruência também pode ser dada por:
Definição. Sejam a, b e m inteiros com m > 0. Dizemos que “a é congruente a b módulo m” se m divide a