Álgebra I – Congruência
23
4. Congruência
4.1 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?
Prof. Robson Rodrigues da Silva
24
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 diferença a – b.
a  b (mod m)  m | (a – b)   q  Z : a – b = mq
Exemplos:
a) 10  1 (mod 3), pois 3 | (10 – 1)
b) 8  2 (mod 3), pois 3 | (8 – 2)
c) 12  7 (mod 5), pois 5 | (12 – 7)
d) 5  - 1 (mod 6), pois 6 | (5 – (–1))
Observação: Quando a não for congruente a b módulo m escreveremos a  b (mod m).
Exercício. Utilizando a definição de congruência responda:
a) 68 e 38 são congruentes módulo 4?
b) 66 e 38 são congruentes módulo 4?
4.2 Algumas aplicações do conceito de congruência
4.2.1 Código de barras EAN – 13
No Brasil o sistema de código de barras EAN – 13 (Numeração de Artigos Europeus) foi adotado para
identificação de produtos em 1983.
Álgebra I – Números inteiros
17
Esse sistema é constituído por 13 algarismos sendo o último o digito controle (a13). O cálculo do digito
de controle é fundamentado na congruência módulo 10. Os 12 primeiros dígitos são multiplicados pela
base {1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3}. Indicando a soma desses produtos por S têm-se que:
S + a13  0 (mod 10)
Exemplo. Um produto possui o seguinte código de barras: 789 7424 08066 x. Determine o dígito
controle.
4.2.2 Cadastro de Pessoas Físicas na Receita Federal (CPF)
No Brasil, o número do CPF de uma pessoa é formado por 11 dígitos, sendo um primeiro bloco com
algarismos e um segundo, com mais dois algarismos, que formam o dígito de verificação. A
determinação desses dois dígitos é mais uma aplicação do conceito de congruência.
S1 - a10  0 (mod 11) e S2 - a11  0 (mod 11)
Exemplo. Determine o dígito verificador para o CPF de número 123 217 151 - xx
4.3 Propriedades da congruência
Sejam m > 0 um inteiro fixo, e a, b, c e d inteiros arbitrários. Então valem as seguintes
propriedades:
P1. a  a (mod m)
P2. a  b (mod m)  b  a (mod m)
P3. a  b (mod m) e b  c (mod m)  a  c (mod m)
P4. a  b (mod m) e c  d (mod m)  a + c  b + d (mod m)
P5. a  b (mod m) e c  Z  a + c  b + c (mod m)
P6. a  b (mod m) e c  d (mod m)  ac  bd (mod m)
P7. a  b (mod m) e c  Z  ac  bc (mod m)
P8. a  b (mod m)  an  bn para todo inteiro positivo n.
a) As propriedades anteriores permitem olhar a congruência como se fosse uma igualdade.
b) Uma das importantes aplicações da congruência na Teoria dos Números é a resolução de problemas
envolvendo divisão de inteiros.
Exemplo. Calcule o resto da divisão de 2100 por 7.
Exercício. Demonstre as propriedades da congruência.