04 TopicosdeAlgebra
97 pág.

04 TopicosdeAlgebra


DisciplinaMatemática78.182 materiais1.402.230 seguidores
Pré-visualização27 páginas
\u2212 a) \u21d2 b \u2261 a(modm).
(iii) Se a \u2261 b(modm) e b \u2261 c(modm), então existem inteiros k1 e k2 tais que a \u2212 b = k1m e b \u2212 c = k2m.
Somando-se, membro a membro, estas últimas equações, obtemos a \u2212 c = (k1 + k2)m o que implica a \u2261
c(modm). 2
Uma relação entre pares de elementos que satisfaz as três propriedades acima (reflexiva, simétrica e tran-
sitiva) é chamada uma relação de equivalência. Dessa forma a proposição anterior mostra que a congruência
módulo m é uma relação de equivalência.
A proposição seguinte mostra resultados imediatos, cujas demonstrações são deixadas a cargo do leitor.
1.39 Proposição. Sejam a, b inteiros quaisquer e m um inteiro não-nulo. Então:
(i) a \u2261 b(mod 1);
(ii) a \u2261 0(modm) se, e somente se, m | a;
(iii) a \u2261 b(modm) se, e somente se, a \u2261 b(mod\u2212m).
Como conseqüência do item (iii) da proposição anterior, na congruência módulo m podemos supor sempre
que m > 0. Isso é o que faremos a partir de agora. Isso quer dizer que podemos identificar um inteiro qualquer
a com o seu resto na divisão por m como mostra a próxima proposição.
1.40 Proposição. Todo inteiro a é congruente módulo m a exatamente um dos valores:
0, 1, 2, 3, . . . ,m\u2212 1.
Prova: Se a for um inteiro qualquer e m > 0, então, pelo Lema da Divisão de Euclides, existem inteiros q
e r tais que
a = qm + r , com 0 \u2264 r < m \u2212 1.
Como q e r são univocamente determinados, temos o resultado. 2
Exemplo 1.13. Se a for um inteiro qualquer e m = 2, temos apenas duas possibilidades: se a for par,
a \u2261 0(mod 2); se a for ímpar, a \u2261 1(mod 2).
TÓPICOS DE ÁLGEBRA 37
Veremos, a seguir, que propriedades válidas para a igualdade de números inteiros são também verdadeiras
para a congruência módulo m:
1.41 Proposição. Seja m um inteiro positivo fixo. Então:
(i) se a \u2261 b(modm) e a\u2032 \u2261 b\u2032(modm), então
(a + a\u2032) \u2261 (b + b\u2032)(modm) e aa\u2032 \u2261 bb\u2032(modm);
(ii) se a \u2261 b(modm), então, para qualquer inteiro k , temos que
(a + k) \u2261 (b + k)(modm) e ak \u2261 bk(modm);
(iii) se a \u2261 b(modm) e k > 0, então
ak \u2261 bk(modmk).
Prova: Mostraremos apenas a segunda parte do item (i). Num dos exercícios propostos dessa seção, o
leitor é convidado a concluir a prova. Se a \u2261 bmodm) e a\u2032 \u2261 b\u2032(modm), então existem inteiros k e t tais que
a = b + km e a\u2032 = b\u2032 + tm. Assim, multiplicando-se membro a membro as duas últimas equações, teremos
aa\u2032 = bb\u2032 + btm + b\u2032km + ktm2 \u21d2 aa\u2032 \u2212 bb\u2032 = m(bt + b\u2032k + ktm),
ou seja,
aa\u2032 \u2261 bb\u2032(modm).
2
ER 12. Mostre que Nenhum número da forma 8n + 7 pode ser escrito como a soma dos quadrados de três
inteiros. Mais precisamente, se k = 8n + 7 para certo inteiro n, então não existem inteiros a, b e c tais que
k = a2 + b2 + c2.
Solução: De fato, se k = 8n + 7, então k \u2261 7(mod 8). Por outro lado, se fosse k = a2 + b2 + c2 para
inteiros a, b e c , então teríamos,
a2 + b2 + c2 \u2261 7(mod 8).
ER 13. Que valores o quadrado de um inteiro pode assumir módulo 8?
Solução: Se m for um inteiro, então m é congruente a um único elemento rm \u2208 {0, 1, . . . , 7}. Mas, então,
m2 \u2261 r2m(mod 8). Verificamos, imediatamente:
rm = 0 \u21d2 m2 \u2261 0(mod 8),
rm = 1 \u21d2 m2 \u2261 1(mod 8),
rm = 2 \u21d2 m2 \u2261 4(mod 8),
rm = 3 \u21d2 m2 \u2261 1(mod 8),
rm = 4 \u21d2 m2 \u2261 0(mod 8),
rm = 5 \u21d2 m2 \u2261 1(mod 8),
rm = 6 \u21d2 m2 \u2261 4(mod 8),
rm = 7 \u21d2 m2 \u2261 1(mod 8).
FTC EAD | LICENCIATURA EM MATEMÁTICA38
Assim, não há maneira de combinar os quadrados de a2, b2 e c2 de modo a produzir um número congruente
a 7. De fato, pelo menos um desses números deve ser congruente a 4 módulo 8: se todos eles fossem
congruentes a 0 ou 1, a soma seria congruente a, no máximo, 3 módulo 8. Se for a2 \u2261 4(mod 8), então,
claramente, não podemos tomar b2 e c2 congruentes a 0 ou 1, pois a soma seria congruente a, no máximo, 6
módulo 8. Se tomarmos também b congruente a 4, a soma a2 + b2 é congruente a 0 módulo 8 e, como não
há número cujo quadrado seja congruente a 7 módulo 8, a2 + b2 + c2 não é congruente a 7 módulo 8.
Uma propriedade que é válida quando lidamos com a igualdade de números, mas que não é válida no caso
da congruência módulo m, é a lei do cancelamento: se ab \u2261 ac(modm), não é necessariamente verdade que
b \u2261 c(modm). Com efeito,
3 · 4 \u2261 3 · 8(mod 12),
mas 4 não é congruente a 8 módulo 12.
No entanto, com uma hipótese adicional a lei do cancelamento pode ser utilizada em congruências.
1.42 Proposição. Se ac \u2261 bc(modm) e mdc(c ,m) = 1, então a \u2261 b(modm).
Prova: Se ac \u2261 bc(modm), então m | (a \u2212 b)c . Como mdc(c ,m) = 1, temos m | (a \u2212 b), ou seja,
a \u2261 b(modm). 2
Entretanto, se mdc(c ,m) 6= 1, o melhor resultado que conseguimos é o seguinte:
1.43 Corolário. Se ac \u2261 bc(modm) e mdc(c ,m) = d , então a \u2261 b
\ufffd
mod
m
d
\ufffd
.
Prova: De ac \u2261 bc(modm) temos ac \u2212 bc = c(a \u2212 b) = km. Se dividirmos os dois membros por d ,
teremos c
d
(a \u2212 b) = k m
d
. Logo, (m
d
) |
\ufffd c
d
(a\u2212 b)
\ufffd
e, como mdc(
m
d
,
c
d
) = 1 ( ver proposição 1.29 item iii )
temos por essa mesma proposição item (i) que (m
d
) | (a\u2212 b) o que implica a \u2261 b
\ufffd
mod
m
d
\ufffd
. 2
A seguir, apresentamos mais algumas propriedades de congruências em diferentes módulos e regras para
cancelamento.
1.44 Proposição. Sejam a e b inteiros quaisquer, e sejam m, d , r e s inteiros positivos.
(i) Se a \u2261 b(modm) e d | m, então a \u2261 b(mod d);
(ii) se a \u2261 b(mod r) e a \u2261 b(mod s), então a \u2261 b(modmmc(r , s));
(iii) se ra \u2261 rb(modm), então a \u2261 b

mod
m
mdc(r ,m)
‹
;
(iv) se ra \u2261 rb(mod rm), então a \u2261 b(modm).
As demonstrações ficam a cargo do leitor (ver exercícios propostos).
1.7.1 Exercícios Propostos
EP 1.23. Demonstre o restante da proposição 1.41.
EP 1.24. Prove a proposição 1.44.
TÓPICOS DE ÁLGEBRA 39
EP 1.25. Mostre que, se a \u2261 b(modm), então an \u2261 bn(modm) para todo inteiro positivo n.
EP 1.26. Se a = (72)6 + (72)5 + 2, mostre que 7 | a.
EP 1.27. Suponha que a \u2261 b(modm) e c \u2261 d(modm). Mostre que ax + cy \u2261 bx + dy(modm) para quaisquer
x , y \u2208 Z.
EP 1.28. Resolva as congruências:
(a) 3 \u2261 3(mod 5);
(b) 3 \u2261 1(mod 6).
EP 1.29. Encontre todos os inteiros x , com 0 \u2264 x < n, satisfazendo as congruências módulo n dadas a
seguir. Se a congruência não possuir solução, justifique.
(a) n = 6 e 4x \u2261 2(mod n);
(b) n = 11 e 5x \u2261 1(mod n).
1.8 Classes de Congruência
A congruência módulo m permite a identificação de todos os números que deixam o mesmo resto quando
divididos por m. Essa identificação nos permite a criação de outros \u201csistemas\u201d numéricos.
1.45 Definição. Sejam m um inteiro fixo e a um inteiro qualquer. Denotamos por [a]m a classe de congruência
de a módulo m, isto é, o conjunto formado por todos os inteiros que são congruentes a a módulo m:
[a]m = {x \u2208 Z : x \u2261 a(modm)} .
ER 14. Determine a classe de congruência de 3 módulo 12 e 15 módulo 12.
Solução: Seja m = 12. Se a = 3, então,
[a]12 = {x \u2208 Z : x \u2261 3(mod 12)}
= {x \u2208 Z : 12 | (x \u2212 3)}
= {x \u2208 Z : x = 12k + 3 para algum k \u2208 Z}
= {. . . ,\u221221,\u22129, 3, 15, . . .}
Por outro lado,
[15]12 = {x \u2208 Z : x \u2261 15(mod 12)} .
Como 15 \u2261 3(mod 12), então x \u2261 15(mod12) se, e somente se, x \u2261 3(mod 12), pela propriedade transitiva
de congruência vista na Proposição 1.38. Logo,
[15]12 = {x \u2208 Z : x \u2261 3(mod 12)} = [3]12.
Para mostrar alguns dos próximos resultados, precisaremos lembrar a definição de igualdade entre dois
conjuntos. Para mostrar que dois conjuntos são iguais, devemos provar que eles possuem os mesmos elemen-
tos. Assim, A = B se, e somente se, A \u2282 B (todo elemento de A é elemento de B) e B \u2282 A (todo elemento de
B é elemento de A).
FTC EAD | LICENCIATURA EM MATEMÁTICA40
1.46 Proposição. Sejam a e b inteiros quaisquer e m um inteiro positivo. Então
(i) a \u2208 [a]m para qualquer m;
(ii) a \u2261 b(modm) se, e somente se, [a]m = [b]m;
(iii) [a]m = [r ]m para algum r \u2208 {0, 1, 2, . . . ,m \u2212 1}.
Prova: Como a \u2261 a(modm) para qualquer m, temos que a \u2208 [a]m, mostrando (i).
Mostraremos agora que, se a \u2261 b(modm), então