[8789 29187]03 algebra moderna

Prévia do material em texto

61
Capítulo 3
Congruência
3.1 Introdução e revisão
No decorrer deste capítulo, vamos apresentar conceitos, exemplos e proposições 
que permitam ao estudante desenvolver habilidades para reconhecer uma 
relação e, em seguida, compreender algumas propriedades que classificam tipos 
especiais de relações; bem como compreender o conceito de congruência e 
associá-lo à divisibilidade e a algumas aplicações.
A congruência é uma ferramenta matemática muito utilizada na resolução de 
problemas que envolvem divisibilidade. É fundamental para a explicação de 
alguns resultados matemáticos como os critérios de divisibilidade, o Teorema do 
Resto Chinês, o Pequeno Teorema de Fermat e no estudo de números pseudo-
primos (primos de determinada forma) estudados por Euler.
O desenvolvimento da congruência enquanto ferramenta matemática foi 
publicado em 1801 por Karl Fridrich Gauss na sua obra Disquisitiones 
Arithmeticae. Para estudá-la, vamos iniciar com alguns conceitos básicos, como 
produto cartesiano e relação.
3.2 Produto cartesiano
Pares ordenados são empregados para representar relações entre elementos 
de um conjunto. O conceito de relação envolve uma regra que associa dois 
elementos: a de um conjunto A e b de um conjunto B, e define pares ordenados 
 satisfazendo essa regra. A relação pode ser representada como o conjunto 
desses pares ordenados.
SILVA, Kelen Regina Salles; CRIPPA, Jane de Oliveira. Álgebra Moderna. Palhoça: UnisulVirtual, 2016. 
p. 61-94.
62
Capítulo 3 
Definição 3.1: dados dois conjuntos A e B, não vazios, chama-se produto 
cartesiano de A por B o conjunto formado por todos os pares ordenados tal 
que .
Assim, a notação significa “A cartesiano B” e é dada por: 
 .
Observação: é possível determinar o produto cartesiano de um conjunto A por 
ele mesmo, neste caso utiliza-se a notação A x A, ou A2. 
Exemplos 3.1: se e , então:
 • o produto cartesiano de A por B é:
 .
 • o produto cartesiano de B por A é:
 .
Exemplo 3.2: se , então o produto cartesiano , é:
 .
Exemplo 3.3: suponha que há uma família composta por dois irmãos, Miguel e João, 
sendo que Miguel tem dois filhos, Gabriel e Ana, e João tem uma filha, Beatriz. Se 
chamarmos de A o conjunto composto por todas as pessoas citadas, teremos:
A = {Miguel, João, Gabriel, Ana, Beatriz}.
O conjunto que representa o produto cartesiano A x A é:
 = {(Miguel, Miguel), (Miguel, João), (Miguel, Gabriel), (Miguel, Ana), (Miguel, 
Beatriz), (João, Miguel), (João, João), (João, Gabriel), (João, Ana), (João, Beatriz), 
(Gabriel, Miguel), (Gabriel, João), (Gabriel, Gabriel), (Gabriel, Ana), (Gabriel, 
Beatriz), (Ana, Miguel), (Ana, João), (Ana, Gabriel), (Ana, Ana), (Ana, Beatriz), 
(Beatriz, Miguel), (Beatriz, João), (Beatriz, Gabriel), (Beatriz, Ana), (Beatriz, Beatriz)}.
Se A = R (conjunto dos números reais), então R x R representa o R2, plano 
cartesiano.
63
Álgebra Moderna 
3.3 Relação e relação de equivalência
Quando analisamos uma representação gráfica, estamos compreendendo a 
relação entre dois elementos. Estes elementos podem pertencer a um ou dois 
conjuntos. As relações são largamente estudadas em matemática e podem 
ser apresentadas de diversas maneiras. Existem algumas que satisfazem 
determinadas propriedades e são classificadas como relação de equivalência. 
Vamos estudá-las a seguir.
3.3.1 Relação binária
Vamos pensar em algumas formas de “relacionar” os membros da família 
apresentada no exemplo 3.3. 
Exemplo 3.4: considere a e b elementos pertencentes a A. Se chamarmos de 
relação R1 a afirmação “a é filho ou filha de b”, que descreve uma forma de 
relacionar os membros desta família, podemos dizer então que:
“Gabriel é filho de Miguel”;
“Ana é filha de Miguel”;
“Beatriz é filha de João”.
Poderíamos escrever de outra forma as frases anteriores:
“Gabriel R1 Miguel”;
“Ana R1 Miguel”;
“Beatriz R1 João”.
Ainda podemos representar esta relação utilizando pares ordenados:
R1 = {(Gabriel, Miguel), (Ana, Miguel), (Beatriz, João)}. 
Vamos agora analisar outra relação entre os membros da mesma família, se 
chamarmos de R2 a relação definida pela afirmação “a é irmão ou irmã de b”, teremos:
“Miguel R2 João”;
“João R2 Miguel”;
“Gabriel R2 Ana”;
“Ana R2 Gabriel”.
64
Capítulo 3 
Ou utilizando pares ordenados:
R2 = {( Miguel, João), (João, Miguel), (Gabriel, Ana), (Ana, Gabriel)}.
Observe que R1 e R2 são subconjuntos de A x A.
Definição 3.2: sejam dois conjuntos A e B, não vazios. Chama-se relação de A 
em B ou relação binária de A em B a todo subconjunto de .
Importante:
 • uma relação é um conjunto, seus elementos devem estar entre 
chaves e separados por vírgulas;
 • se um par pertence à uma relação , diremos que a está 
relacionado com b pela relação , e denotamos por , ou 
 ;
 • se um par não pertence à uma relação ( ), diremos 
que a não está relacionado com b pela relação , escrevemos ;
Exemplo 3.5: R1 e R2 do exemplo 3.4 são ditas relações de A em A.
As relações mais triviais entre dois conjuntos A e B são o conjunto vazio e o 
produto cartesiano A x B. Vale lembrar que o conjunto vazio é um subconjunto 
de qualquer conjunto e A x B também é um subconjunto dele mesmo. 
Exemplo 3.6: sejam os conjuntos A e B do exemplo 3.1. 
São relações de A em B:
 • ;
 • ;
 • ;
 • . 
Existem outras relações de A em B.
Algumas relações são representadas por uma regra ou lei de formação.
65
Álgebra Moderna 
Exemplo 3.7: sejam A = Z e B = Z, então é um conjunto formado por todos 
os pares ordenados nos quais as coordenadas são números inteiros. 
São exemplos de relação de Z em Z, ou em , ou definidas em Z:
 • R1: “a é o oposto de b”, ou seja, (a está relacionado a b 
por R1 se e somente se a = – b).
tal que . 
Podemos dizer que: “–2 R1 2”, “–1 R1 1”, “0 R1 0”..., mas “–1 2” , 
“0 3”...
 • R2: “a é igual a b”, ou seja, (a está relacionado a b por R2 
se e somente se a = b).
tal que .
 • R3: “a é menor ou igual a b”, ou seja, (a está relacionado 
a b por R3 se e somente se a ≤ b).
tal que . 
Alguns elementos de R3 são pois em 
todos os casos a primeira coordenada do par ordenado é menor ou 
igual à segunda coordenada.
 • R4: “a divide b”, ou seja, . 
tal que . 
Alguns elementos de R4 são 
pois em todos os casos a primeira coordenada do par ordenado 
divide a segunda coordenada. Mas observe que o par ordenado 
 não pertence a R4, pois zero não divide quatro.
Será que só podemos falar de relação envolvendo números inteiros? A 
resposta é não. Veja outros exemplos:
Exemplo 3.8: se A = B = IR (conjunto dos números reais), então é um conjunto 
formado por todos os pares ordenados de números reais. Um exemplo é a relação de 
IR em IR:
tal que , todos os pares ordenados cujas 
coordenadas são números reais não negativos.
Algumas relações envolvem outros tipos de conjuntos. 
66
Capítulo 3 
Exemplo 3.9: se A = B = , isto é, A e B são conjuntos cujos elementos são 
pares ordenados. Logo, os elementos dos pares ordenados de são pares 
ordenados de números naturais. No caso:
tal que .
Portanto, qualquer relação R relaciona um par ordenado a outro par ordenado. 
Veja exemplos de relação neste conjunto:
 • R1: “(a, b) é igual a (c, d)”, ou seja: 
 ((a, b) está relacionado a (c, 
d)”, se e somente se a = c e b = d).
.
tal que
 
 • R2: “(a, b) está relacionado a (c, d) se a soma da primeira coordenada 
do primeiro par ordenado com a última coordenada do segundo par 
ordenado for igual a soma da segunda coordenada do primeiro par 
ordenado com a primeira coordenada do segundo par ordenado”, 
ou seja:
 
tal que .
Veja alguns elementos:
 .
Mas observe que , pois .
 • R3 “a é menor ou igual a b”, ou seja, (a está relacionado 
a b se e somente sea ≤ b).
Observação: cuidado ao estudar uma relação R definida sobre os conjuntos A e 
B, pois você deve identificar como são os elementos destes conjuntos e a lei de 
formação de R. 
3.3.2 Relação de equivalência 
Existem algumas relações largamente estudadas em álgebra: são as relações de 
equivalência e relações de ordem. Para que uma relação seja classificada de uma 
destas formas, ela deve satisfazer algumas propriedades, estudadas a seguir.
67
Álgebra Moderna 
Definição 3.3: uma relação R, definida em A, é reflexiva se todo elemento de A 
estiver relacionado a ele mesmo. Ou seja, se a A, aRa.
Exemplo 3.10: a relação tal que do exemplo 3.7 é 
reflexiva, pois para todo .
Exemplo 3.11: a relação tal que do exemplo 3.7 não é 
reflexiva. Veja um contraexemplo:
Dado tem-se que visto que não satisfaz a lei de formação 
 .
Exemplo 3.12: a relação tal que 
do exemplo 3.9 é reflexiva, pois para todo tem-se que:
 (pela comutatividade da adição dos números naturais).
Definição 3.4: uma relação R definida em A é simétrica se dados dois elementos 
a e b de A tem-se:
b relacionado a a sempre que a estiver relacionado a b. 
Ou seja: a,b A, se aRb, então bRa.
Importante: cuidado com o “se”, isto é, só precisamos verificar bRa se aRb ocorrer.
Exemplo 3.13: a relação tal que do exemplo 3.7 é 
simétrica, pois para quaisquer inteiros a e b tem-se:
Se a = b 
b = a 
Exemplo 3.14: A relação tal que do exemplo 3.7 é 
simétrica, pois para quaisquer inteiros a e b tem-se que:
Se a = –b 
b = –a .
68
Capítulo 3 
Exemplo 3.15: a relação tal que 
do exemplo 3.9 é simétrica. Pois, para quaisquer , 
se 
 
 .
Exemplo 3.16: a relação tal que do exemplo 3.7 não é 
simétrica. Veja um contraexemplo:
Dado: , ou seja, , mas 0 não divide –4. 
Definição 3.5: uma relação R definida em A é transitiva se dados três elementos 
a, b e c de A tem-se:
a relacionado a c sempre que a estiver relacionado a b e b estiver relacionado a c.
Ou seja: a, b, c A, se aRb e bRc, então aRc.
Importante: cuidado com o “se”, isto é, só precisamos verificar aRc se as duas 
condições aRb e bRc ocorrerem.
Exemplo 3.17: a relação tal que do exemplo 3.7 é 
transitiva, pois para quaisquer inteiros a, b e c tem-se que:
Se e e 
 .
Exemplo 3.18: a relação tal que do exemplo 3.7 é 
transitiva, pois para quaisquer inteiros a, b e c tem-se que:
Se e e 
 .
69
Álgebra Moderna 
Exemplo 3.19: a relação tal que 
do exemplo 3.9 é transitiva, pois para quaisquer 
se 
e 
somando as igualdades
 
 (pela lei do cancelamento)
 
 .
Exemplo 3.20: a relação tal que do exemplo 3.7 não é 
transitiva. Observe um contraexemplo:
Dados ao pares (2, –2) e (–2, 2) 
tem-se que e mas .
Observação: lembre-se de que para mostrarmos que uma relação satisfaz 
alguma propriedade devemos mostrar de forma genérica, mas se ela não é válida, 
basta apresentar um contraexemplo.
Definição 3.6: uma relação R, definida em A, é denominada relação de 
equivalência se satisfaz as seguintes propriedades:
(i) R é reflexiva;
(ii) R é simétrica;
(iii) R é transitiva.
Exemplo 3.21: a relação tal que do exemplo 3.7 é uma 
relação de equivalência, pois verificamos as três propriedades nos exemplos 3.10, 
3.13 e 3.17.
70
Capítulo 3 
Exemplo 3.22: a relação tal que 
do exemplo 3.9 é uma relação de equivalência, pois verificamos as três 
propriedades nos exemplos 3.12, 3.15 e 3.19.
Exemplo 3.23: a relação tal que do exemplo 3.7 não é 
uma relação de equivalência, pois não satisfaz a propriedade transitiva conforme 
mostrado no exemplo 3.20.
Para ser de equivalência, uma relação deve satisfazer as três propriedades; 
se uma falhar, ela não é de equivalência. 
3.3.3 Relação de ordem
Para que uma relação seja classificada como relação de ordem, ela precisa 
satisfazer uma nova propriedade.
Definição 3.7: uma relação R, definida em A, é antissimétrica se dados dois 
elementos a e b de A tem-se:
a igual a, sempre que a estiver relacionado a b e b estiver relacionado a a.
Ou seja: a, b A, se aRb e bRa, então a = b. 
Exemplo 3.24: a relação tal que do exemplo 3.7 é 
antissimétrica, pois se aRb e bRa, significa que e , o que só ocorre se .
Definição 3.8: uma relação R definida em A é denominada relação de ordem se 
satisfaz as seguintes propriedades:
(i) R é reflexiva;
(ii) R é antissimétrica;
(iii) R é transitiva.
71
Álgebra Moderna 
Exemplo 3.25: a relação tal que do exemplo 3.7 é uma 
relação de ordem:
(i) R é reflexiva, pois para qualquer inteiro a tem-se aRa, ou seja ;
(ii) R é antissimétrica, conforme mostrado no exemplo 3.24;
(iii) R é transitiva, conforme mostrado no exemplo 3.18.
3.4 Atividades de autoavaliação
1. Sejam A = {0, 1, 2, 3, 4} e B = {2, 4, 6, 8}, escreva os elementos das relações de 
A em B a seguir:
R1= {(a, b) tal que a > b}.
R2= {(a, b) tal que b = a + 2}.
R3= {(a, b) tal que b = 2a}.
2. Sejam A = {0, 1, 2} e a relação R = {(0, 0), (0, 1), (1, 0), (1, 1), (2, 2)}, verifique se 
R é uma relação de equivalência. 
3. Verifique se a relação R1 do exemplo 3.4 é uma relação de equivalência.
4. Seja A o conjunto de todas as retas no plano e a relação R definida por:
tem-se que é paralela a , verifique se R é uma relação de 
equivalência.
5. Seja A = {1, 2, 3, 4, 5} e a relação R definida por
tem-se é múltiplo de , verifique se R é uma relação de 
equivalência.
6. Considerando A = {a, b, c} e as seguintes relações em A:
R1 = {(a, a), (b, b), (c, c)}.
R2 = {(a, a), (a, b), (a, c), (b, b), (b, c), (c, c)}.
72
Capítulo 3 
R3 = {(a, b), (a, c), (b, a), (b, c), (c, a), (c, b), (c, c)}.
R4 = A x A. 
Verifique quais são reflexivas, simétricas, transitivas e/ou antissimétricas.
7. Dado tal que e sendo R a relação definida por
 , identifique:
a) os elementos de R;
b) se R é uma relação de equivalência.
3.5 Congruências módulo m
Alguns problemas do nosso dia a dia são resolvidos baseados no estudo das 
congruências. Por exemplo, para descobrir o dia da semana em que você 
nasceu, em otimização de redes de computadores e em códigos numéricos de 
identificação, como códigos de barras e até em números dos documentos (como 
de identidade, CPF, ISBN, criptografia etc.), entre outros.
A congruência módulo m é uma importante relação de equivalência e se 
caracteriza como uma ferramenta associada ao conjunto dos números inteiros. 
É utilizada para resolver problemas que envolvem divisibilidade baseada no 
algoritmo da divisão.
Definição 3.9: sejam a e b e m um inteiro estritamente 
positivo, dizemos que a é côngruo a b módulo m, e 
denotamos por , se e somente se . 
Ou seja:
 
(m divide e pela definição de divisibilidade: se existe um inteiro q, tal que 
 ou ainda ). 
Atenção: m é 
estritamente positivo, 
então diferente de zero.
73
Álgebra Moderna 
Caso a não seja côngruo a b módulo m, denotamos: 
 .
Como interpretar a congruência como uma relação R?
Dizemos que se aRb ao dividir a e b, separadamente por um inteiro não negativo 
m, apresentar o mesmo resto, este resultado é demonstrado na propriedade 3.4. 
Exemplo 3.26: como interpretar a relação de congruência:
 • , pois 2 divide 5 – 3 = 2.
Observe que ao dividir 3 por 2 o quociente é 1 e o resto é 1, ao 
dividir 5 por 2 o quociente é 2 e o resto é 1.
 • , pois 2 divide 3 – 5 = –2.
 • , pois 77 – 13 = 64 que é divisível por 8.
 • , pois 45 – (–5) = 50 e 10 | 50.
 • , pois 26 – 3 = 23 e 5 não divide 23.
Exemplo 3.27: um caso clássico de congruência que envolve a congruência 
módulo 24 está relacionado às horas do dia. Pois como a cada 24 horas se inicia 
um novo ciclo, então a 25ª hora é congruente a uma hora módulo 24, a 26ª é 
congruente a duas horas módulo24, e assim sucessivamente.
Com isso, podemos observar as seguintes relações:
.
Suponha que agora são 11 horas. Que hora será daqui 165 horas?
Inicialmente vamos admitir que a hora 11 representa o ponto inicial. 
Pelo algoritmo da divisão:
165 = 6 . 24 + 21.
Ou seja, serão 6 dias e 21 horas a partir das 11 horas iniciais.
74
Capítulo 3 
Podemos representar esta conclusão utilizando congruência como:
 .
Proposição 3.1: a relação de congruência é uma relação de equivalência
Para ser uma relação de equivalência, a relação de congruência deve satisfazer 
as três propriedades, conforme definição 3.6.
(i) Reflexiva: .
(ii) Simétrica: Se , então .
(iii) Transitiva: Se e , então .
Demonstração:
(i) É reflexiva, pois . Assim,
 (qualquer número inteiro não nulo divide zero). Neste caso, 
dizemos que qualquer inteiro é côngruo a ele mesmo módulo m.
(ii) É simétrica: , então .
tal que
 
(iii) É transitiva: se e , então 
 .
.
75
Álgebra Moderna 
3.5.1 Propriedades da congruência
A relação de congruência satisfaz ainda outros resultados:
Propriedade 3.1: se e , então .
Demonstração:
tal que
 
Exemplo 3.28: se , então:
 
 , pois .
Propriedade 3.2: se e , então .
Demonstração: 
Se (pela propriedade 3.1).
Se (pela propriedade 3.1).
Então, se e , como a congruência é 
transitiva: .
Observação: esta propriedade pode ser estendida, ou seja:
Se , ,..., e então:
 .
76
Capítulo 3 
Exemplo 3.29: sendo e , observe que:
 
 pois .
Propriedade 3.3: se r é o resto da divisão de a por m , então , com 
 . 
Demonstração:
Pelo algoritmo da divisão:
 
Exemplo 3.30: o resto da divisão de 48 por 5 é 3, então podemos dizer que 
 .
Propriedade 3.4: se se e somente se, o resto da divisão de a por m é 
igual ao resto da divisão de b por m.
Demonstração:
 Vamos demonstrar a afirmação “Se o resto da divisão de a 
por m é igual ao resto da divisão de b por m”.
Sabemos que tal que .
Se chamarmos de q1 o quociente da divisão de a por m e de r o resto desta 
divisão, tem-se: 
77
Álgebra Moderna 
 .
Como 
 (lembre-se de que é um número inteiro).
Logo, r é o resto da divisão de b por m.
 Agora vamos demonstrar a afirmação “Se o resto da divisão de a por m é 
igual ao resto da divisão de b por m ”.
Seja r o resto da divisão de a e de b por m, isto é:
Chamando os respectivos quocientes de e :
 .
Subtraindo as duas igualdades: 
 
 (lembre-se de que é um número inteiro).
Logo, .
Exemplos 3.31: 12 7 (mod 5), pois 2 é o resto da divisão de 12 por 5 e de 7 por 
5, ou seja, 7 e 12 deixam o mesmo resto na divisão por 5. 
Propriedade 3.5: se e , então .
Demonstração:
tal que (multiplicando por c).
 
 (lembre-se de que c . q é um número inteiro)
 .
78
Capítulo 3 
Exemplo 3.32: se , então:
 
 , pois .
Propriedade 3.6: se e , então 
Demonstração: 
Se (pela propriedade 3.5).
Se (pela propriedade 3.5).
Então, se e , como a congruência é transitiva: 
 .
Observação: esta propriedade pode ser estendida, ou seja:
Se , ,..., , então:
 .
Exemplo 3.33: se , , , então:
 
 , pois .
Propriedade 3.7: se , então .
Demonstração:
Se a partir da propriedade 3.6 admitir-se:
 
 .
79
Álgebra Moderna 
Exemplo 3.34: calcular o resto da divisão de por 5. 
Para isso, vamos aplicar as propriedades demonstradas.
Inicialmente, vamos determinar o menor inteiro congruente a 348 módulo 5.
 (pois 5|(348-3).
Então, aplicando a propriedade 3.7, tem-se: 
 ou, ainda, .
Continuando a trabalhar com potências:
 
 (vamos trabalhar com esse resultado, o 
expoente de 348 múltiplo de 4).
Pensando no expoente do número , observamos que 467 será múltiplo de 4 
se diminuirmos 3 unidades, ou seja, podemos escrever 467 = 464 + 3 = 4 . 116 + 3. 
Assim a potência pode ser escrita como:
 .
Pelas propriedades 3.6 e 3.7, tem-se:
 .
Portanto, o resto da divisão por 5 é 2.
Exemplo 3.35: calcular algarismo das unidades de . 
Inicialmente, vamos lembrar que o algarismo das unidades é o resto da divisão do 
número por 10. Assim, vamos utilizar a congruência módulo 10 e as propriedades 
de congruência para resolver este problema.
 (pois 10 | (81 – 1).
Então, aplicando a propriedade 3.7, tem-se 
 .
Com isso, o algarismo das unidades é 1.
80
Capítulo 3 
3.5.2 Aplicações da congruência 
I. Calendário
Os dias da semana, domingo, segunda-feira, terça-feira, quarta-feira, quinta-
feira, sexta-feira e sábado, são respectivamente côngruos módulo 7 aos outros 
domingos, segundas-feiras, terças-feiras, quartas-feiras, quintas-feiras, sextas-
feiras e sábados, pois todos se repetem de 7 em 7 dias. 
Você pode fazer a seguinte correspondência, que será útil em alguns cálculos.
SEG TER QUA QUI SEX SAB DOM
0 1 2 3 4 5 6
Em que dia da semana você nasceu?
Vamos descrever aqui o procedimento e as respectivas explicações para que 
você possa descobrir o dia da semana em que nasceu. É claro que o 
procedimento pode ser utilizado para descobrir outras datas.
Escolhemos como ano básico o ano de 1900. Isto porque para nossa geração é 
razoável em termos de idade, porque foi um ano bissexto (fevereiro tem 29 dias, 
ocorre de 4 em 4 anos), e porque eu sei o dia da semana de 1/ 1/1900.
O dia da semana de 1/1/1900 foi uma segunda-feira.
Seguiremos a correspondência já estabelecida. 
Primeira semana de 1/1/1900.
SEG TER QUA QUI SEX SAB DOM
0 1 2 3 4 5 6
Se soubermos o número de dias transcorridos desde o dia 1/1/1900 até o dia de 
nosso nascimento, podemos descobrir em que dia da semana nascemos. Isso porque 
se dois números forem côngruos entre si, módulo 7, cairão no mesmo dia da semana.
Por exemplo: 27/1/1900 caiu no domingo já que 27 6 mod 7 (veja a 
correspondência dada).
No entanto, pode ser muito monótono ou trabalhoso, principalmente para quem 
é jovem, calcular a quantidade de dias transcorridos até a data de nascimento. 
Pensamos em facilitar os cálculos com o procedimento proposto e aproveitar 
para utilizar as propriedades dadas.
Você pode utilizar outra 
se quiser, mas tenha 
cuidado em saber 
por onde começou a 
contar. 
81
Álgebra Moderna 
Procedimento
1. Veja quantos anos transcorreram de 1900 até o ano de seu 
nascimento.
Por exemplo, se você nasceu em 1955, transcorreram 55 anos.
Atenção: se não fossem os anos bissextos já saberíamos o dia da semana de 
1/1/1955 facilmente.
2. Calcule quantos anos bissextos tivemos neste período (basta aplicar 
o algoritmo da divisão para o obtido no item 1 e dividir por 4).
Para o nosso exemplo, tem-se 55 = 4 . 13 + 3 e, assim, tivemos neste período 13 
anos bissextos.
Cada ano tem 365 dias e os bissextos 366 dias.
Qual o dia da semana de 1/1/1955?
Como 365 = 7 . 52 + 1, tem-se pela propriedade 2 que 
365 1 mod 7. 
Como 55 = 7 . 7 + 6, tem-se pela propriedade 2 que 
55 6 mod 7.
Utilizando a propriedade 3, podemos afirmar que 5 
5.365 6.1 mod 7, ou seja, 55.365 6 mod 7 (isso garante 
que será considerado somente os anos transcorridos). 
E os anos bissextos?
Nos anos bissextos tem-se um dia a mais, 29 de fevereiro, portanto, se no período 
de 1900 a 1955 tivemos 13 anos bissextos, teremos 13 dias a mais neste período.
13 6 mod 7 e, pela propriedade 1, obtem-se 55 + 13 6 + 6 mod 7. Por outro 
lado, tem-se que 12 5 mod 7 e pela transitividade da relação de congruência 
será 55 + 13 5 mod 7.
Olhando em nossa tabela, concluímos que 1/1/1955 ocorreu em um sábado.
3. Considere o mês de seu nascimento e associe a ele o número 
segundo a tabela abaixo. Por exemplo, se você nasceu no mês de 
setembro, o número correspondente é o 5. Corresponde ao dia 1 
do mêsde setembro.
Quando o ano não for 
bissexto, o dia primeiro 
do ano seguinte cairá 
em um dia da semana 
consecutivo ao dia 
da semana em que 
ocorreu o dia primeiro 
do ano considerado.
82
Capítulo 3 
janeiro 0 julho 6
fevereiro 3 agosto 2
março 3 setembro 5
abril 6 outubro 0
maio 1 novembro 3
junho 4 dezembro 5
Nesta tabela, associamos 0 ao mês de janeiro por ser o início de nossa contagem, 
ele é o primeiro mês do ano. A fevereiro atribuímos o número 3 porque até dia 1 
de fevereiro transcorreram 31 dias de janeiro e 31 3 mod 7, a março atribuímos 
também o número 3 , porque 3 + 28 = 31 3 mod 7.
Por que 6 para abril?
3 + 31 = 34 6 mod 7.
Assim, sucessivamente com todos os meses.
4. Considere, agora, o dia de seu nascimento (digamos que você 
tenha nascido no dia 20).
Como o dia 1 já foi considerado na atribuição do mês em questão (setembro), 
teremos até o dia 20, 19 dias transcorridos.
Calcule: 55 + 13 + 5 + 19 = 92.
92 = 7 . 13 + 1
92 1 mod 7. 
Olhe na tabela o dia da semana que está associado ao número 1.
Conclusão: A pessoa em questão nasceu em uma terça-feira.
Observe que você pode calcular também da seguinte forma: 55 6 mod 7
13 6 mod 7.
Setembro corresponde ao número 5.
19 5 mod 7.
6+ 6 + 5 + 5 = 22 1 mod 7.
83
Álgebra Moderna 
II. Critérios de divisibilidade
A congruência também é empregada para se estabelecer os critérios de 
divisibilidade de números inteiros.
Inicialmente vamos utilizar a representação polinomial de um número natural a:
 .
Sendo uma sequência de números naturais com 
 . 
Com isso, vamos analisar os critérios de divisibilidade.
Partindo da congruência: 
a. Critério de divisibilidade por 2: um número a inteiro é divisível por 2 
se for par.
Suponha que a seja um inteiro qualquer representado na forma polinomial
 .
Como , pela propriedade 3.7 tem-se que 
 . Dado um número natural , pela propriedade 3.5: 
 . 
Consequentemente:
 .
Pela propriedade 3.2:
 .
Logo
 
ou seja:
 .
Portanto, pela propriedade 3.4, têm mesmo resto na divisão por 2; assim, a 
é divisível por 2 se e somente se for divisível por 2, ou seja, se for par.
b. Critério de divisibilidade por 3: um número a inteiro é divisível por 3 
se a soma de seus algarismos for divisível por 3.
Suponha que a seja um inteiro qualquer representado na forma polinomial
 .
84
Capítulo 3 
Como , pela propriedade 3.7 tem-se que 
 . Dado um número natural , pela propriedade 3.5: 
 .
Consequentemente:
 .
Pela propriedade 3.2:
 .
Logo,
 .
Portanto, pela propriedade 3.4, têm mesmo resto na 
divisão por 3. Assim, a é divisível por 3 se e somente se , que 
representa a soma dos dígitos de a, for divisível por 3.
III. Problema do Resto Chinês
Um resultado interessante sobre a teoria das congruências é o Teorema do Resto 
Chinês, publicado entre os séculos III e V pelo matemático chinês Sun Tsu. O 
problema surgiu da necessidade de determinar um número x sabendo apenas 
que se divido por alguns inteiros resulta em determinados restos. Veja:
Determinar um número x cujo resto, ao ser dividido por 3, é 2; ao ser dividido por 
5, é 7; e ao ser dividido por 7, é 2.
Hoje sabemos que é possível determinar este número por substituição, e que ele 
não é único. Mas, utilizando a congruência podemos escrever o problema como:
 
Vamos apresentar o teorema do resto chinês que mostra como resolver o 
problema utilizando congruências.
85
Álgebra Moderna 
Teorema 3.1: sejam números inteiros maiores que 1, tais que 
MDC (mi, mj) = 1 para , isto é, são primos dois a dois. Dado 
 números inteiros quaisquer, o sistema de congruências
 
é possível e quaisquer duas soluções são congruentes módulo .
Demonstração:
Suponha uma solução do sistema 
 
Dada pelo número desde que
 e 
 
ou seja
 
Observe que y é realmente solução do sistema, para isso vejamos que y satisfaz a 
j-ésima (j = 1, ..., k) congruência do sistema dado: .
De fato, como tem-se
 .
Mas, 
 então e, portanto,
 .
86
Capítulo 3 
Nosso objetivo é determinar os números que satisfazem as condições de 
 .
Para isso, tomemos :
 
Sabemos que MDC (mi,mj) = 1 , então , pois como 
 , um divisor primo de teria que dividir 
também algum , o que não ocorre, pois são primos.
Logo, a congruência 
 (*)
tem solução. Para ilustrar, vamos tomar e admitir b1 uma solução 
da equação (*). Assim:
 , mas sabemos que é divisível por . Então,
 
portanto,
 
Seguindo o mesmo raciocínio, se b2 uma solução da equação (*):
 , então
 e
 .
Consequentemente:
 .
Portanto, uma solução do sistema é
 , ou ainda,
 .
Suponha agora outra solução do sistema dada por c, então 
 .
87
Álgebra Moderna 
Logo são divisores de c – b e como são primos dois a 
dois, então são divisores de c – b, ou seja .
Portanto 
 .
É a solução geral do sistema dado.
Exemplo 3.36: utilize o teorema do resto chinês para resolver o sistema:
 .
Observe que 
 e , então e 
 .
Precisamos determinar tal que:
 .
Vejamos:
 , mas , logo 
 
 , logo 
 logo .
Portanto,
 
e 
 .
Observe que
 
Assim, existem outras soluções que satisfazem este sistema.
88
Capítulo 3 
IV. Pequeno teorema de Fermat
Teorema 3.2: seja p um número primo e de tal forma que p não divide a, então 
 .
Demonstração:
Seja uma sequência dos (p – 1) múltiplos positivos de a:
 (**)
Observe que:
 .
Suponha e . Então, , pois 
MDC (a, p) = 1. Portanto, os números são congruentes aos 
números módulo p, em alguma ordem. Ou seja:
 .
Utilizando a notação de fatorial, tem-se:
 .
Como , o termo pode ser cancelado da congruência, 
resultando em:
 .
Exemplo 3.37: verifique o pequeno teorema de Fermat para a = 3 e p = 5.
Escrevendo a sequência , tem-se 
 , (pois p – 1 = 4). Os restos positivos da divisão de cada termo da 
sequência acima por 5 são respectivamente 3, 1, 4, 2, que podem ser escritos na 
ordem: 1, 2, 3, 4.
Então:
 
ou ainda
 , de fato o resto da divisão de 81 por 5 é 1.
89
Álgebra Moderna 
Curiosidade: dado um número inteiro a e um número inteiro composto n, tal 
que an – 1 = 1 (mod n). Então, n é dito pseudoprimo de base a. 
 
Se n é pseudoprimo de base a para todo o inteiro a tal que MDC (a, n) = 1, 
então n é chamado de número de Carmichael. 
 
São alguns números pseudoprimos: 
• de base 2: 341, 561, 645, 1105, 1387, 1729, ... 
• de Carmichel: 561, 1105, 1729, 2465, . . . 
3.6 Atividades de autoavaliação
1. Determine os restos das seguintes divisões
a) por 6.
b) por 100.
c) por 5.
2. Determine o algarismo das unidades de .
3. Determine todos os inteiros x que satisfazem:
a) 
b) 
c) 
4. Pesquise os critérios de divisibilidade por 4 e por 5 e demonstre-os utilizando 
congruência.
5. Resolva, utilizando o teorema do resto chinês:
a) .
b) (problema clássico, Regiomantanus do século XVI). 
90
Capítulo 3 
3.7 Classes de equivalência das congruências Módulo m
Definição 3.10: se R é uma relação de equivalência em um conjunto A e a um 
elemento de A. Chamamos de classe de equivalência de a, módulo R, ao conjunto 
constituído por todos os elementos , tais que (x está relacionado a a 
pela relação R).
As classes de equivalência são denotadas por:
 
Exemplo 3.38: seja a relação de equivalência R = {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 
2), (2, 0), (2, 1), (2, 2), (3, 3)} em que A = {0, 1, 2, 3}, apresentada no exemplo 3.23. 
São classes de equivalência:
 ={0, 1, 2} (o conjunto de todos os elementos de A, relacionados ao 0).
 ={0, 1, 2} (o conjunto de todos os elementos de A, relacionados ao 1).
 ={0,1, 2} (o conjunto de todos os elementos de A, relacionados ao 2).
 ={3} (o conjunto de todos os elementos de A, relacionados ao 3).
Exemplo 3.39: seja R a relação definida em Z, por ; isto é: “x é 
côngruo a a módulo 5”. Como determinar as classes de equivalência de R?
R é uma relação de equivalência, e pela proposição 3.6, a e x têm mesmo resto 
em suas divisões por 5. Aplicando o algoritmo da divisão de um número b por 5: 
 para algum inteiro q
ou seja, os possíveis restos da divisão de um número inteiro por 5 são: 0, 1, 2, 3 e 4.
Assim, a partir da congruência teremos apenas 5 possibilidades:
 • (números inteiros cujo resto da divisão por 5 é 0);
 • (números inteiros cujo resto da divisão por 5 é 1);
 • (números inteiros cujo resto da divisão por 5 é 2);
 • (números inteiros cujo resto da divisão por 5 é 3);
 • (números inteiros cujo resto da divisão por 5 é 4).
91
Álgebra Moderna 
Observe que:
c. o conjunto de todos os inteiros que são côngruos a 0 módulo 5 é 
o conjunto de todos os múltiplos de 5: {..., –10, –5, 0, 5, 10,...} , ou 
ainda, cujo resto da divisão por 5 é 0;
d. o conjunto de todos os inteiros que são côngruos a 1 módulo 5 é o 
conjunto de todos os múltiplos de 5 mais 1: {..., –9, –4, 1, 6, 11,...}, 
ou ainda, cujo resto da divisão por 5 é 1;
e. o conjunto de todos os inteiros que são côngruos a 2 módulo 5 é o 
conjunto de todos os múltiplos de 5 mais 2: {..., –8, –3, 2, 7, 12,...}, 
ou ainda, cujo resto da divisão por 5 é 2;
f. o conjunto de todos os inteiros que são côngruos a 3 módulo 5 é o 
conjunto de todos os múltiplos de 5 mais 3: {..., –7, –2, 3, 8, 13,...}, 
ou ainda, cujo resto da divisão por 5 é 3;
g. o conjunto de todos os inteiros que são côngruos a 4 módulo 5 é o 
conjunto de todos os múltiplos de 5 mais 4: {..., –6, –1, 4, 9, 14,...}, 
ou ainda, cujo resto da divisão por 5 é 4.
Logo, as classes de equivalência módulo 5, são:
 ={..., -10, -5, 0, 5, 10,...} (o conjunto de todos os elementos de Z, cujo resto da 
divisão por 5 é 0);
 ={..., -9, -4, 1, 6, 11,...} (o conjunto de todos os elementos de Z, cujo resto da 
divisão por 5 é 1);
 ={..., -8, -3, 2, 7, 12,...} (o conjunto de todos os elementos de Z, cujo resto da 
divisão por 5 é 2);
 ={..., -7, -2, 3, 8, 13,...} (o conjunto de todos os elementos de Z, cujo resto da 
divisão por 5 é 3);
 ={..., -6, -1, 4, 9, 14,...} (o conjunto de todos os elementos de Z, cujo resto da 
divisão por 5 é 4).
Cada uma dessas classes é composta por subconjuntos do conjunto dos 
números inteiros de tal forma que a união desses subconjuntos resulta no 
próprio conjunto dos inteiros e a intersecção de dois a dois é vazia.
92
Capítulo 3 
O conjunto das classes de congruência módulo m, é chamado de conjunto 
quociente de Z pela relação de congruência módulo m e é denotado por Zm (lê-se 
“conjunto zeeme”). 
Se m é um inteiro estritamente positivo, teremos m classes de congruência 
módulo m, veja a seguinte proposição. 
Proposição 3.2: o conjunto tem exatamente m classes, são elas 
 
Demonstração:
Pela proposição 3.1, a relação de congruência módulo m é uma relação de 
equivalência em Z. 
Assim, dados a e b , tem-se que .
Logo, para cada a pertencente a Z, tem-se que , sendo r o resto da 
divisão de a por m. 
Pela divisão Euclidiana, sabe-se que . Assim, tem-se que 
a e, portanto, coincide com uma das classes de congruência .
Para finalizar a demonstração, vamos mostrar que as classes são distintas entre elas. 
Para isso, basta observar que se r1 e r2 são restos tais que , então
 .
Logo Zm tem m elementos.
Exemplo 3.40: o conjunto , para:
m = 2 
m = 3 
m = 7 
m = 11 .
93
Álgebra Moderna 
3.8 Atividades de autoavaliação
1. Determine os conjuntos com alguns elementos das classes de Z4.
2. Dada a relação de equivalência da atividade 7 de 3.4, determine os elementos 
de e .
3. Seja Q o conjunto dos números racionais e R a relação definida por:
 
a) Mostre que R é uma relação de equivalência.
b) Descreva os elementos da classe