Fundamentes de Álgebra Moderna
Profª Ana Paula
Congruências
Definição 1: Sejam a, b números inteiros quaisquer e m um inteiro estritamente
positivo. Diz-se que a é côngruo a b módulo m se m
a b , isto é, a b mq para
um conveniente inteiro q. Para indicar que a é côngruo a b, módulo m , usa-se a notação
a b mod m
Exemplos: 5
9 mod 2
5
9 mod 4
16
2 mod 7
14
4 mod 5
A relação assim definida sobre o conjunto chama-se congruência módulo m.
Para indicar que a b não é divisível por m, ou seja, que a não é côngruo b módulo m,
escreve-se
a b mod m
Exemplos: 5
8 mod 2
3
10 mod 6
13
2 mod 7
14
0 mod 5
Propriedades:
1) Reflexivadade a a mod m .
2) Simetria: Se a b mod m , então b a mod m .
3) Transitividade: Se a b mod m e b c mod m , então a c mod m .
4) Se a b mod m e 0 b m, , então b é o resto da divisão euclidiana de a por m.
5) a b mod m se, e somente se, a e b dão o mesmo resto na divisão euclidiana por
m.
6) a b mod m se, e somente se a c b c mod m .
7) a b mod m e c d mod m , então a c b c mod m .
8) Se a b mod m , então ac bc mod m .
9) Se a b mod m e c d mod m , então ac bd mod m .
10) Se ca cb mod m e mdc c, m
d 0, então a b mod m/c .
.
11) Se a b mod m , então a n b n mod m , n
12) Se a c b c mod m , então a b mod m .
Corolário 1: Se ca
1
cb mod m e mdc c, m
1, então a
b mod m .
Fundamentos de Álgebra Moderna
Exemplos:
1) Mostrar que 10 200 1 é divisível por 11.
2) Mostre que o resto da divisão de um número por 10 é seu algarismo das unidades
e que o resto da divisão por 100 é o número formado pelo dois últimos algarismos do
número dado.
3) Determinar o algarismo das unidades de 3 100 .
4) Determinar o resto da divisão de 5 60 por 26.
Definição 2: Todo conjunto formado por um e um só elemento de cada classe de
equivalência módulo m é chamado de sistema completo de restos módulo m.
0, 1, 2, , m 1 é o sistema completo de restos módulo m.
São também sistemas completos de restos módulo m:
0, 1, 2, , m2 1 se m é ímpar.
m
0, 1, 2, ,
1 , m2 se m é par.
2
Exemplos:
1) Mostrar que a congruência x 2 1 0 mod 8 não tem solução.
2) Mostrar que, qualquer que seja o inteiro ímpar a, o resto da divisão de a 2 por 8 é
1.
2
Fundamentos de Álgebra Moderna
Critérios de Divisibilidade
Pode-se utilizar a congruência de inteiros para restabelecer critérios de
divisibilidade. Lembrando que todo número N pode ser representado de uma única
maneira como um polinômio, isto é,
N a n a n 1 a n 2 a 1 a 0 a 0 a 1 10 a 2 10 2
a n 10 n
onde a n , a n 1, a n 2, a 1 , a 0
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 .
Para estabelecer um critério de divisibilidade por m, a idéia é descobrir uma
expressão mais simples em termos dos dígitos a n , a n 1, a n 2, a 1 , a 0 à qual o polinômio é
côngruo, módulo m, e depois usar a propriedade (5).
Divisibilidade por 2:
Como 10 t 0 mod 2 , para todo t 1, então N a 0 mod 2 . Logo N e a 0 têm o
mesmo resto na divisão por 2. Isto é, N é divisível por 2
a 0 é divisível por 2. Ou seja,
se a 0 é par.
Divisibilidade por 3:
Como 10 1 mod 3 , então 10 2 1 mod 3 , 10 3
Então
a 2 . 10 2 a 2 . 1 mod 3 , a 3 . 10 3 a 3 . 1 mod 3 , , a n . 10 n
propriedades
(1)
e
(7),
N a0
an an 1 an 2
a 1 a 0 mod 3 . Logo N e a n a n 1
resto na divisão por 3. Isto é, N é divisível por 3
an
por 3.
1 mod 3 , , 10 n 1 mod 3 ,
n.
a 1 . 10 a 1 . 1 mod 3 , então
a n . 1 mod 3 . Logo , devido as
a 1 10 a 2 10 2
a n 10 n
an 2
a 1 a 0 têm o mesmo
an 1 an 2
a 1 a 0 é divisível
Exercício: Estabeleça os critérios de divisibilidade de 4, 5 e 6.
Exemplos:
1) Provar que n n 1 n 2 é divisível por 6, qualquer que seja n.
2) Ache o resto da divisão de 3 10 . 42 5 6 8 por 5.
Exercícios
1) Ache os restos da divisões:
a) 2 45 por 7.
b) 11 100 por 100.
c) 5 2 . 4841 28 5 por 3.
3
Fundamentos de Álgebra Moderna
2) Mostre que o número 2 20
1 é divisível por 41.
3) Qual é o resto da divisão euclidiana de 1 5 2 5 3 5
Justifique.
Sugestão: Dividir a soma dada em 25 grupos de 4 parcelas.
99 5
100 5 por 4?
4)
100
a) Ache o algarismo das unidades de 7 7 .
9
a) Ache os dois últimos algarismos de 9 9 .
5) Se p e p 2 são números primos, então se denominam primos gêmeos. É o caso,
por exemplo, de 3 e 5. Se p 3 e os números p e p 2 são números primos gêmeos,
prove que a soma p p 2
2p 2 é múltiplo de 12.
Sugestão: Sendo a soma um número par, então a príncipio essa soma poderia ser
côngrua a 0,2,4,6,8,10 módulo 12. Mostrar que todas essas possibilidades, exceto a
primeira, levam a uma contradição.
a
6) Prove que se a
b mod n .
b mod m
e n é um divisor de m, maior que 1. então
7) Demonstre:
a) a 3 a mod 6
b) a 3 0, 1, ou 8 mod 9
c) Se a é um inteiro que não é divisível por 2 nem por 3, então a 2
d) Se a é um cubo perfeito,então a 0, 1, ou 1 mod m .
Respostas:
1) a)1
b)1
3)0
4
c)0
1 mod 24 .