Aula 10 profmat - congruencias lineares e quadraticas - 10 11-17

Aula de Congruências Lineares, Classes Residuais e Congruências Quadráticas - introdução do PROFMAT da UERJ

1. Congru^encias Lineares
Congru^encias Quadraticas
Aritmetica - MA14
AULA 10 - CONGRU^ENCIAS LINEARES E CLASSES
RESIDUAIS
CONGRU^ENCIAS QUADRATICAS - UMA INTRODUC~AO
Aline de Lima Guedes Machado
PROFMAT - IME/UERJ
Universidade do Estado do Rio de Janeiro
[email protected]
10 de Novembro 2017
1 / 57

2. Congru^encias Lineares
Congru^encias Quadraticas
Sumario
1
Congru^encias Lineares
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
2
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Quadraticas
2 / 57

3. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Sumario
1
Congru^encias Lineares
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
2
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Quadraticas
3 / 57

4. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares
Objetivo central dessa aula e resolver congru^encias lineares do tipo
aXb mod m;a;b;m2Z;m>1;
ou seja, determinarse existiremx2Ztais queaxb mod m:
Proposic~ao 11.1: Criterio para vericar se tais congru^encias admitem
soluc~ao.
Dadosa;b;m2Z, comm>1, a congru^encia
aXb mod m;a;b;m2Z;m>1;
tem soluc~ao inteira se e somente se
(a;m)jb:
OBS:Sex0e soluc~ao da congru^enciaaXb mod m,
ent~ao todoxtal quexx0mod me tambem soluc~ao
da congru^encia(soluc~oes particulares determinam
innitas soluc~oes). Elas s~ao consideradas uma so soluc~ao modulom.
4 / 57

5. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares
Em sequ^encia, outro objetivo e determinar uma colec~ao completa de
soluc~oes duas a duas incongruentes modulom, que ser~ao chamadas
desistema completo de soluc~oes incongruentesda congru^encia.
Teorema 11.2: Soluc~oes de uma congru^encia
Sejama;b;m2Z, comm>1 e (a;m)jb. Sex0e uma soluc~ao da
congru^enciaaXb mod m;a;b;m2Z;m>1;ent~ao
x0;x0+
m
d
;x0+ 2
m
d
; :::;x0+ (d1)
m
d
onded= (a;m), formam um sistema completo de soluc~oes da
congru^encia, duas a duas incongruentes modulom.
OBS:Isso quer dizer que qualquer soluc~ao da congru^encia e con-
gruente a um e somente um dos numeros acima.
OBS2:A congru^encia possui exatamentedsoluc~oes
modulom, incongruentes duas a duas. 5 / 57

6. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares
Exemplo: Resolver 6X3mod15.
6 / 57

7. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares
Exemplo: Resolver 6X3mod15.
d= (6;15) = 3 e 3j3. Logo a congru^encia tem soluc~ao.
Numero de soluc~oes:d= 3 soluc~oes modulo 15.
Por tentativa e erro, encontra-se a soluc~ao inicialx0= 8, pois
683mod15, ja que 15j483 = 45.
Logo, todas as soluc~oes modulo 15 s~ao:
8;8 +
15
3
= 13;8 + 2
15
3
= 183mod15:
E assim, todas as soluc~oes inteiras s~ao:
3 + 15t;8 + 15t;13 + 15t;t2Z:
7 / 57

8. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares
Exemplo: Seria possvel simplicar a congru^encia 6X3mod15 e
obter todas as soluc~oes?
8 / 57

9. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares
Exemplo: Seria possvel simplicar a congru^encia 6X3mod15 e
obter todas as soluc~oes?
N~ao!Isso so pode ser feito se (a,m)=1.
Se o cancelamento fosse feito, teramos um problema:
6X3mod15,d= (6;15) = 3 e 3j3. A congru^encia possui 3
soluc~oes modulo 15.
3 + 15t;8 + 15t;13 + 15t;t2Z:
Ja ao dividir a congru^encia por 3:
2X1mod15,d= (2;15) = 1 e 1j3. A congru^encia teria 1
soluc~ao modulo 15:x0= 8 seria soluc~ao, pois 15j2.8-1.
Jax= 3 ex= 13 n~ao seriam soluc~oes, pois: 156 j2:31 = 5 e
156 j2:131 = 25:
9 / 57

10. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares
Exemplo: Resolver 6X3mod5.
10 / 57

11. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares
Exemplo: Resolver 6X3mod5.
Poderia ser simplicada, pois (6,5)=1. Da:
6X3mod5$2X1mod5.
Por inspec~ao, tem-sex0= 3 como soluc~ao unica modulo 5, uma
vez qued= 1.
11 / 57

12. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares
Exemplo: Resolver 6X21mod18.
12 / 57

13. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares
Exemplo: Resolver 6X21mod18.
A congru^encia n~ao possui soluc~ao, pois (6,18)=6 e 66 j21:
13 / 57

14. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares - soluc~ao unica
Em alguns casos, a congru^encia temsoluc~ao unicamodulom.
Corolario 11.4. Consequ^encia direta do teorema 11.2
Se (a;m) = 1, ent~ao a congru^enciaaXb mod mpossui uma
unica soluc~ao modulom.
Corolario 11.5. Consequ^encia direta do teorema 11.2
Sejamm>1 eR
0
um conjunto reduzido de resduos modulom(se
r2R
0
, ent~ao (r;m) = 1. Seb2Z, ent~ao8r2R
0
, a congru^encia
rXb mod mpossui uma unica soluc~ao modulomemR
0
.
14 / 57

15. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares - inverso
multiplicativo.
Inverso multiplicativo
A congru^enciaaX1mod m, com (a;m) = 1 admite soluc~ao
unica modulom. Esta soluc~aox0sera chamada deinverso
multiplicativodeamodulom.
Exemplo: Resolver a congru^encia 7a+ 54mod9:
15 / 57

16. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares - inverso
multiplicativo.
Inverso multiplicativo
A congru^enciaaX1mod m, com (a;m) = 1 admite soluc~ao
unica modulom. Esta soluc~aox0sera chamada deinverso
multiplicativodeamodulom.
Exemplo: Resolver a congru^encia 7a+ 54mod9:
7a+ 54mod9$7a 1mod9$7a8mod9:
Para "sumir"com o 7, devemos encontrar o inverso multiplicativo
modulo 9 de 7.

E o 4, pois 74 = 281mod9:Da:
47a48mod9$a32mod9$a5mod9:
Soluc~ao:a5mod9 oua= 9b+ 5;b2Z:
16 / 57

17. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares - soluc~ao unica
Em geral, as congru^enciasaXb mod ms~ao mais faceis de resol-
ver por inspec~ao quando o modulome pequeno. Quando ele n~ao
for pequeno, pode-se aplicar algumas propriedades das congru^encias
para baixar o modulo, como no exemplo a seguir.
Resolver a congr^encia 13X4mod42:
(13;42) = 1, ent~ao existe soluc~ao e e unica a soluc~ao modulo 42.
Temos que 42= 2 x 3 x 7 e [2,3,7]=42. Logo, por proposic~ao
anterior (9.13),x0e soluc~ao da congru^encia acima se e somente se
ela e soluc~ao simult^anea das congru^encias:
13X4mod2;13X4mod3;13X4mod7:
Por inspec~ao, e facil ver quex0= 10 e soluc~ao de todas as
congru^encias, logo e soluc~ao da congru^encia inicial. Ent~ao, as
soluc~oes s~ao dadas porx= 10 + 42t;t2Z.
17 / 57

18. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares - aplicac~ao
Achar as soluc~oes inteiras de 15x
2
7y
2
= 9.
Soluc~ao:Essa equac~ao pode ser reescrita como 15x
2
7y
2
9 = 0.
Assim, e possvel resolver essa equac~ao utilizando congru^encia. Como
00mod m, qualquer que sejam, podemos reescrever essa equac~ao
como uma congru^encia com zero modulo "algum numerom", substituindo
o zero pela equac~ao. O modulo 7 e um otimo candidato ao modulo, pois:
7y
2
0mod7
Assim, a parte doysumiria na congru^encia. Reescrendo a equac~ao
original modulo 7, temos:
15x
2
7y
2
90mod7
Fazendo as simplicac~oes em relac~ao ao modulo 7, temos:
1x
2
0y
2
20mod7;ou seja;x
2
2mod7:
Analisando os possveis valores dexdentro do sistema completo de
resduos (0,1,2,3,4,5,6), chegamos que as soluc~oes paraxs~ao:
x3mod7 oux4mod7, ou seja,x= 7k+ 3 oux= 7k+ 4;k2Z:
18 / 57

19. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares - aplicac~ao
Achar as soluc~oes inteiras de 15x
2
7y
2
= 9.
Continuac~ao da soluc~ao:
Isso ainda n~ao e garantia de soluc~ao, pois precisamos encontrar um par
(x,y). Substituirxna equac~ao para encontraryseria muito trabalhoso.
Faremos ent~ao o mesmo procedimento para "sumir" com ox,
reescrevendo a equac~ao como congru^encia com o zero modulo 3, 5 ou 15.
Escolhendo modulo 3, temos:
0x
2
1y
2
00mod3;ou seja;y
2
0mod3:
A soluc~ao seriay0mod3, ou seja,y= 3t;t2Z:Ainda n~ao e
suciente para responder ao problema. Vamos ent~ao resolver modulo 5:
0x
2
2y
2
40mod5;ou seja;2y
2
4mod5:
Como (2,5)=1, podemos simplicar:y
2
2mod5;ou ainda,
y
2
3mod5:Ao substituir 0,1,2,3,4, vemos que essa congru^encia n~ao
tem soluc~ao modulo 5 e a a equac~ao proposta n~ao tem soluc~ao emZ.
19 / 57

20. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares - aplicac~ao
Exerccio 11.5: Mostre que a congru^enciaX
2
+ 10mod7 n~ao
possui soluc~oes. Conclua que a equac~ao
X
2
7Y
2
14X+ 7Y6 = 0 n~ao admite soluc~oes inteiras.
20 / 57

21. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Resoluc~ao de Congru^encias Lineares - aplicac~ao
Exerccio 11.5: Mostre que a congru^enciaX
2
+ 10mod7 n~ao possui
soluc~oes. Conclua que a equac~aoX
2
7Y
2
14X+ 7Y6 = 0 n~ao
admite soluc~oes inteiras.
Soluc~ao:De fato,
X
2
+ 10mod7$X
2
1mod7$X
2
6mod7.
Substituindo todos os elementos do conjunto de resduos, temos:
0
2
0mod7;1
2
1mod7;2
2
4mod7;3
2
2mod7
4
2
2mod7;5
2
4mod7;6
2
1mod7.
Logo, a congru^enciaX
2
+ 10mod7 n~ao possui soluc~oes.
Se a equac~aoX
2
7Y
2
14X+ 7Y6 = 0 tivesse soluc~ao (x,y)
inteira, a congru^encia abaixo teria soluc~ao:
X
2
7Y
2
14X+ 7Y60mod7:
Como7Y
2
0mod7;14X0mod7;7Y0mod7,
implicaria queX
2
60mod7 tivesse soluc~ao. Absurdo! Logo, a
equac~aoX
2
7Y
2
14X+ 7Y6 = 0 n~ao admite soluc~oes inteiras.
21 / 57

22. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Sistemas de Congru^encias Lineares - exemplo
Em um cesto, ha uma quantidadeNde ovos. Se os ovos forem
agrupados de 3 em 3, sobram 2. Se os ovos forem agrupados de 4 em 4,
sobra 1. Quantos ovos pode haver no cesto?
Resolver por congru^encia!
22 / 57

23. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Sistemas de Congru^encias Lineares - exemplo
Em um cesto, ha uma quantidadeNde ovos. Se os ovos forem
agrupados de 3 em 3, sobram 2. Se os ovos forem agrupados de 4 em 4,
sobra 1. Quantos ovos pode haver no cesto?
Resolver por congru^encia!
Soluc~ao:
(
N2mod3
N1mod4
N2mod3 e o mesmo que,N= 3a+ 2;a2N:
SubstituindoNna segunda congru^encia, temos:
3a+ 21mod4$3a 1mod4$3a3mod4
Como (3,4)=1, podemos cancelar:a1mod4, ou seja,
a= 4b+ 1;b2N. Substituindo na primeira equac~ao deN:
N= 3(4b+ 1) + 2$N= 12b+ 5$N5mod12:
Partimos de duas congru^encias, uma modulo 3 e outra modulo 4 e por
m, a respota e modulo 12. Isso n~ao foi coincid^encia, como veremos.
A soluc~ao e:N5mod12 ouN= 5 + 12b;b2N.
23 / 57

24. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Teorema Chin^es dos Restos
No seculo I, o matematico chin^es Sun-Tsu prop^os o problema:
Qual e o numero que deixa restos 2, 3 e 4 quando dividido, respec-
tivamente, por 3, 5 e 7?
A resposta dada pelo chin^es para esse problema foi 23. Ao escrever
esse problema em linguagem matematica moderna, ele se equivale
na resoluc~ao de um sistema de congru^encias:
X2mod3
X3mod5
X2mod7
De modo geral, o objetivo e resolver o sistema abaixo:
Xcimod mi;i= 1;2; :::;r:
OTeorema Chin^es dos Restosvai auxiliar na
resoluc~ao de tais sistemas.
24 / 57

25. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Teorema Chin^es dos Restos
A proposic~ao a seguir sera util para o Teorema Chin^es dos Restos.
Proposic~ao 11.6: Reduc~ao de Congru^encias Lineares
Toda congru^encia do tipoaXb mod mque tem soluc~ao e
equivalente a uma congru^encia do tipo
Xc mod n
Demonstrac~ao:
aXb mod m(I) tem soluc~ao$d= (a;m)jb:
Fazendoa
0
=
a
d
;b
0
=
b
d
;n=
m
d
, tem-se que a congru^encia (I) e
equivalente aa
0
Xb
0
mod n(II). Como (a
0
;n) = 1,a
0
e invertvel,
ou seja, existe uma
00
tal quea
0
a
00
1mod n. Da, multiplicando a
congru^encia (II) pora
00
, tem-sea
0
a
00
Xba
00
mod n, isto e,
Xc mod n,
ondec=ba
00
, coma
00
o inverso multiplicativo dea
0
modulon.
25 / 57

26. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Teorema Chin^es dos Restos
Sistemas de Congru^encias Lineares
Os sistemas de congru^encias lineares do tipo
aiXbimod ni;i= 1; :::;r
Possuem soluc~ao quando (ai;ni)jbi;8i= 1; :::;r.
Pela proposic~ao anterior, esses sistemas s~ao equivalentes a um
sistema reduzido escrito na forma
Xcimod mi;i= 1; :::;r(I):
A partir dessa equival^encia dos sistemas de congru^encia, sera
apresentado o Teorema Chin^es dos Restos.
26 / 57

27. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Teorema Chin^es dos Restos
Teorema Chin^es dos Restos
Se (mi;mj) = 1 para todo parmi;mjcomi6=j, ent~ao o sistema
Xcimod mi;i= 1; :::;r
possui umaunica soluc~ao moduloM=m1m2 mr. Alem disso,
as soluc~oes s~ao do tipo:
x=M1y1c1+ +Mryrcr+tM;
ondet2Z;Mi=
M
mi
(ouMie o resultado do produto de todos os
mjexceto omi), eyie soluc~ao deMiY1mod mi;i= 1; :::;r:
27 / 57

28. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Teorema Chin^es dos Restos
Resoluc~ao do problema de Sun-Tsu
A resoluc~ao do problema e equivalente a resoluc~ao do sistema:
X2mod3
X3mod5
X2mod7
M= 3x5x7 = 105;M1=
105
3
= 35 (ouM1= 57);M2=
105
5
= 21 (ou
M2= 37) ;M3=
105
7
= 15 (ouM3= 35):Por outro lado, o sistema
35Y1mod3
21Y1mod5
15Y1mod7
tem como soluc~oes, respectivamente,y1= 2;y2= 1;y3= 1. Portanto,
uma soluc~ao modulo 105 e dada por:
x=M1y1c1+M2y2c2+M3y3c3= 233
Como 23323mod105, segue que 23 e uma soluc~ao do sistema e
qualquer outra soluc~ao e do tipo 23 + 105t;t2Z:
28 / 57

29. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Teorema Chin^es dos Restos - Exerccio
Exerccio 11.10: Resolver o sistema:
3X1mod7;5X2mod11;4X3mod13
Soluc~ao:Devemos reduzir o sistema acima a um sistema da forma
Xcimod mi;i= 1;2;3:
29 / 57

30. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Teorema Chin^es dos Restos - Exerccio
Exerccio 11.10: Resolver o sistema:
3X1mod7;5X2mod11;4X3mod13
Soluc~ao:Devemos reduzir o sistema acima a um sistema da forma
Xcimod mi;i= 1;2;3:
Para isso, devemos determinar os inversos multiplicativos de 3, 5 e 7
modulo 7, 11 e 13, respectivamente. Assim:
351mod7;591mod11;4101mod13:
Logo, temos um sistema equivalente ao sistema inicial:
35X15mod7 $X5mod7
59X29mod11 $X187mod11
410X310mod13$X304mod13
M= 7:11:13 = 1001;M1= 11:13 = 143;M2= 7:13 = 91;M3= 7:11 =
77:Resolvendo as congru^enciasMiYi1mod mitemos:
143Y11mod7;91Y21mod11;77Y31mod13:Fazendo a
reduc~ao de seus coecientes em relac~ao aos modulos: 3Y11mod7;
3Y21mod11;12Y31mod13:Por inspec~aoy1= 5;y2= 4,
y3=1:Da,x=M1y1c1+M2y2c2+M3y3c3= 5815810mod1001.
30 / 57

31. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Teorema Chin^es dos Restos - Generalizado
Essa modicac~ao do Teorema Chin^es dos Restos e para os casos em
que os modulosmi;i= 1; :::rn~ao s~ao primos entre si.
Teorema 11.16: Teorema Chin^es dos Restos Generalizado
O sistema de congru^encias
Xcimod mi;i= 1; :::r
admite soluc~ao se e somente se,
cicjmod(mi;mj)8i;j= 1; :::r:
Nesse caso, asoluc~ao e unica modulo[m1; :::mr].
31 / 57

32. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Teorema Chin^es dos Restos Generalizado - Exerccios
Exerccio 11.13: Resolva o sistema:
X2mod3;X3mod4;X4mod5;X2mod6:
32 / 57

33. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Teorema Chin^es dos Restos Generalizado - Exerccios
Exerccio 11.13: Resolva o sistema:
X2mod3;X3mod4;X4mod5;X2mod6:
Soluc~ao:
Como osmin~ao s~ao todos primos entre si, temos que utilizar o
Teorema Chin^es dos Restos Generalizado.
Assim, considerandom2= 4 em4= 6, temos:
(6,4)=2. Mas 362mod2, pois 26 j32.
Logo o sistema n~ao tem soluc~ao.
33 / 57

34. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Teorema Chin^es dos Restos Generalizado - Exerccios
Exerccio 11.12: Resolva o sistema:
X2mod3;X3mod4;X4mod5;X5mod6:
34 / 57

35. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Teorema Chin^es dos Restos Generalizado - Exerccios
Exerccio 11.12: Resolva o sistema:
X2mod3;X3mod4;X4mod5;X5mod6:
Soluc~ao:
Como osmin~ao s~ao todos primos entre si, temos que utilizar o
Teorema Chin^es dos Restos Generalizado e analisar osmique n~ao
s~ao primos entre si.
Assim, considerandom1= 3 em4= 6, temos:
(6,3)=3 e 52mod3.
Agora considerandom2= 4 em4= 6, temos:
(6,4)=2 e 53mod2.
Logo o sistema tem soluc~ao unica modulo [3,4,5,6]=60. Por
inspec~ao, analisando todas as congru^encias, e facil vericar que
x=1 e soluc~ao do sistema e como159mod60, 59 e a
soluc~ao mnima positiva do sistema.
35 / 57

36. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Classes Residuais
O objetivo do estudo de Classes Residuais se da no fato da possibili-
dade de construir novas estruturas algebricas a partir da congru^encia
modulo um numero naturalm>1, alem de faciliar a resoluc~ao de
algumas congru^encias.
Partic~ao deZ:
Sejam2Z;m>1:Fazer umapartic~ao do conjunto dos
Numeros InteirosZe o mesmo que dividir esse conjunto em uma
famlia de subconjuntos, de modo que essessubconjuntos sejam
disjuntos dois a doise que auni~ao desses subconjuntos
resulte em todo o conjuntoZ.
36 / 57

37. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Classes Residuais
Umexemplo de partic~aodo conjuntoZseria considerar que cada um
dos seus subconjuntos fosse formado por todos osnumeros inteiros que
possuem o mesmo resto quando divididos porm.
[0] =fx2Z;x0mod mg
[1] =fx2Z;x1mod mg

[m1] = fx2Z;xm1mod mg
Para-se em [m1], pois tem-se que [m] = [0];[m+ 1] = [1]; :::
Partic~ao deZ- Classes Residuais.
O conjunto
[a] = fx2Z;xa mod mg
e chamado declasse residual modulomdo elementoadeZ:O
conjunto de todas as classes residuais modulome representado porZm.
Portanto,Zm=f[0];[1]; :::;[m1]g
37 / 57

38. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Classes Residuais - Exemplos
Exemplo 1:m= 2
[0] =fx2Z;x0mod2g=fx2Z;xe parg
[1] =fx2Z;x1mod2g=fx2Z;xe mparg
Exemplo 2:m= 3
[0] =fx2Z;x0mod3g=f3t;t2Zg
[1] =fx2Z;x1mod3g=f3t+ 1;t2Zg
[2] =fx2Z;x2mod3g=f3t+ 2;t2Zg
38 / 57

39. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Classes Residuais - Propriedades
Classes Residuais - Propriedades
i) [a] = [b] se e somente seab mod m;
ii) Se [a]\[b]6= 0, ent~ao [a] = [b];
iii)
S
a2N
[a] =Z:
Denic~ao: Representante da Classe Residual
Dado [a]2Zm, um inteiroxtal que [x] = [a] sera chamado um
representante de [a].
OBS:Existe uma innidade de representantes da classe [a]2Zm.
Por exemplo, todos os numeros pares s~ao representantes da classe
residual [0], sem= 2.
39 / 57

40. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Classes Residuais - Propriedades
Classes Residuais - Propriedades - Proposic~ao 11.25 e 11.26
i) Para cadaa2Z, existe um e somente umr2Z, com
0r<mtal que [a] = [r];
ii) Existem exatamentemclasses residuais distintas duas a duas
modulom, a saber: [0];[1]; :::;[m1].
OBS:Classes residuais transformam a congru^enciaab mod m
na igualdade [a] = [b].
40 / 57

41. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Operac~oes emZm
Operac~oes emZm
EmZms~ao denidas as seguintes operac~oes:
Adic~ao:[a] + [b] = [a+b];
Multiplicac~ao:[a][b] = [ab].
OBS:As operac~oes independem das escolhas dos seus
representantes (justicado por propriedades das congru^encias).
41 / 57

42. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Operac~oes emZm- Propriedades
Propriedades da Adic~ao emZm
Para todos [a];[b];[c]2Zm;tem-se:
A1) Associatividade:([a] + [b]) + [c] = [a] + ([b] + [c]);
A2) Comutatividade:[a] + [b] = [b] + [a];
A3) Exist^encia do zero:[a] + [0] = [a];8[a]2Zm;
A4) Exist^encia do simetrico:[a] + [a] = [0]:
Propriedades da Multiplicac~ao emZm
Para todos [a];[b];[c]2Zm;tem-se:
M1) Associatividade:([a][b])[c] = [a]([b][c]);
M2) Comutatividade:[a][b] = [b][a];
M3) Exist^encia da unidade:[a][1] = [a]:
AM) Distributividade:[a]([b] + [c]) = [a][b] + [a][c]:
42 / 57

43. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Zme um anel
Zmmunido das operac~oes de adic~ao e multiplicac~ao e chamado de
anel das classes residuais modulomou anel dos inteiros modulo
m.
Denic~ao: elemento invertvel
Um elemento [a]2Zme dito invertvel quando existir [b]2Zmtal
que [a][b] = 1. Nesse caso, [b] e o inverso de [a].
43 / 57

44. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Tabelas de adic~oes e multiplicac~oes emZm
Tabelas de adic~ao e multiplicac~ao emZ2=f[0];[1]g
+[0] [1]
[0][0] [1]
[1][1] [0]
[0] [1]
[0][0] [0]
[1][0] [1]
OBS:Todo elemento n~ao nulo deZ2e invertvel.
Tabelas de adic~ao e multiplicac~ao emZ3=f[0];[1];[2]g
+[0] [1] [2]
[0][0] [1] [2]
[1][1] [2] [0]
[2][2] [0] [1]
[0] [1] [2]
[0][0] [0] [0]
[1][0] [1] [2]
[2][0] [2] [1]
OBS:Todo elemento n~ao nulo deZ3e invertvel.
44 / 57

45. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Tabelas de adic~oes e multiplicac~oes emZm
Tabelas de adic~ao e multiplicac~ao emZ4=f[0];[1];[2];[3]g
+[0] [1] [2] [3]
[0][0] [1] [2] [3]
[1][1] [2] [3] [0]
[2][2] [3] [0] [1]
[3][3] [0] [1] [2]
[0] [1] [2] [3]
[0][0] [0] [0] [0]
[1][0] [1] [2] [3]
[2][0] [2] [0] [2]
[3][0] [3] [2] [1]
OBS:EmZ4, os unicos elementos invertveis s~ao [1] e [3].
OBS2:EmZ4, existe um elemento n~ao nulo cujo produto dele por ele
mesmo e nulo: [2][2] = 0. Isso motiva a denic~ao a seguir.
Denic~ao: Divisor de zero
Um elementoa6= 0 de um anelAe chamado dedivisor de zerose
existir umb6= 0 emAtal queab= 0:
OBS:Um divisor de zero nunca e invertvel (produto ou e 1 ou e 0).
45 / 57

46. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Tabelas de adic~oes e multiplicac~oes emZm
Tabelas de adic~ao e multiplicac~ao emZ5=f[0];[1];[2];[3];[4]g
+[0] [1] [2] [3] [4]
[0][0] [1] [2] [3] [4]
[1][1] [2] [3] [4] [0]
[2][2] [3] [4] [0] [1]
[3][3] [4] [0] [1] [2]
[4][4] [0] [1] [2] [3]
[0] [1] [2] [3] [4]
[0][0] [0] [0] [0] [0]
[1][0] [1] [2] [3] [4]
[2][0] [2] [4] [1] [3]
[3][0] [3] [1] [4] [2]
[4][0] [4] [3] [2] [1]
OBS:EmZ5(tambem emZ2eZ3), todo elemento n~ao nulo e invertvel.
OBS2:Isso n~ao ocorre em todos osZm(emZ4, [2] e divisor de zero,
logo n~ao e invertvel.)
OBS3:A tabela e simetrica em relac~ao a diagonal principal.
OBS4:[1] e [m-1] s~ao sempre invertveis e seus inversos s~ao,
respectivamente, [1] e [m-1] emZm.
46 / 57

47. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Tabelas de multiplicac~oes emZm
Tabelas de multiplicac~ao emZ8=f[0];[1];[2];[3];[4];[5];[6];[7]g
[0] [1] [2] [3] [4] [5] [6] [7]
[0][0] [0] [0] [0] [0] [0] [0] [0]
[1][0] [1] [2] [3] [4] [5] [6] [7]
[2][0] [2] [4] [6] [0] [2 [4] [6]
[3][0] [3] [6] [1] [4] [7] [2] [5]
[4][0] [4] [0] [4] [0] [4] [0] [4]
[5][0] [5] [2] [7] [4] [1] [6] [3]
[6][0] [6] [4] [2] [0] [6] [4] [2]
[7][0] [7] [6] [5] [4] [3] [2] [1]
Exemplos:Resolver as congru^encias olhando a tabela:
a)2x6mod8
b)2x1mod8
a)3x1mod8
47 / 57

48. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Tabelas de multiplicac~oes emZm
Tabelas de multiplicac~ao emZ8=f[0];[1];[2];[3];[4];[5];[6];[7]g
[0] [1] [2] [3] [4] [5] [6] [7]
[0][0] [0] [0] [0] [0] [0] [0] [0]
[1][0] [1] [2] [3] [4] [5] [6] [7]
[2][0] [2] [4] [6] [0] [2 [4] [6]
[3][0] [3] [6] [1] [4] [7] [2] [5]
[4][0] [4] [0] [4] [0] [4] [0] [4]
[5][0] [5] [2] [7] [4] [1] [6] [3]
[6][0] [6] [4] [2] [0] [6] [4] [2]
[7][0] [7] [6] [5] [4] [3] [2] [1]
Exemplos:Resolver as congru^encias olhando a tabela:
a)2x6mod8!x3mod8 oux7mod8
b)2x1mod8!N~ao tem soluc~ao, ou seja, [2] n~ao e invertvel emZ8:
a)3x1mod8!x3mod8, ou seja, [3] e o inverso de [3] emZ8:
48 / 57

49. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Zmdenido como Corpo
As informac~oes anteriores motivam a denic~ao a seguir.
Denic~ao: Corpo
Um anel onde todo elemento n~ao nulo possui inverso multiplicativo
e chamado decorpo.
OBS:Z2;Z3;Z5, com as operac~oes denidas, s~ao corpos.Z4n~ao
e.

E importante saber se um determinado elemento deZme invertvel.
Proposic~ao 11.32: Elemento deZminvertvel
Um elementoadeZme invertvel se e somente se, (a;m) = 1:
Corolario 11.33:Zmdenido como Corpo
Zme um Corpo se e somente se,me primo.
49 / 57

50. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
Exemplo- aplicac~aoZmna resoluc~ao de congru^encias
As classes residuais permitem resolver as congru^encias do seguinte modo:
Congru^encias e classes residuais
Resolver uma congru^enciaaXb mod mreduz-se a resolver, emZm, a
seguinte equac~ao:
[a]Z= [b]:
Exemplo de aplicac~ao.
Resolver a congru^encia 4X3mod5 equivale a resolver a equac~ao
[4]Z= [3].
Olhando a tabela de multiplicac~ao deZ5, vemos que [4][4]=1. Logo [4] e
invertvel emZ5com inverso [4]. Portanto, multiplicando a equac~ao
[4]Z= [3] em ambos os lados por [4]:
[4][4]Z= [4][3]$[1]Z= [2]
. Logo,Z= [2] e as soluc~oes da congru^encia s~aox= 2 + 5t;t2Z.
50 / 57

51. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Quadraticas
Sumario
1
Congru^encias Lineares
Resoluc~ao de Congru^encias Lineares
Teorema Chin^es dos Restos
Classes Residuais
2
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Quadraticas
51 / 57

52. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Quadraticas
Resoluc~ao de Congru^encias Quadraticas
Objetivo:resolver congru^encias quadraticas do tipo:
AY
2
+BY+C0mod N;(I)
A;B;C;N2Z;N>1;A60mod Nou seja,Nn~ao e um divisor deA.
Estrategia de substituic~ao:
Multiplicando por 4A, encontramos uma congru^encia equivalente
4A
2
Y
2
+ 4ABY+ 4AC0mod4AN
Que tambem e equivalente a congru^encia
4A
2
Y
2
+ 4ABY+ 4AC0mod N
Completando quadrados, temos: (2AY+B)
2
B
2
4AC mod N.
PondoZ= 2AY+B; =B
2
4AC, resolver a congru^encia (I) e equi-
valente a resolver o sistema de congru^encias:
(
Z
2
mod N
2AY+BZ mod N
(II)
52 / 57

53. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Quadraticas
Resoluc~ao de Congru^encias Quadraticas
Conclus~ao:Resolver a congru^encia (I) e equivalente a resolver em
Za primeira congru^encia de (II) e, de posse da soluc~aozmodulo
N, encontrar a soluc~aoyda segunda congru^encia do sistema (II),
desde que tais congru^encias sejam soluveis.
Sendo as congru^encias do tipoX
2
a mod nmais simples de traba-
lhar quando (a;n) = 1, e possvel transformar o sistema (II) em um
sistema equivalente, onde a primeira congru^encia sera desse tipo.
Proposic~ao
A congru^enciaZ
2
mod mdo sistema (II) e equivalente a
congru^encia
X
2
a mod n
em que (a;n) = 1:
53 / 57

54. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Quadraticas
Resoluc~ao de Congru^encias Quadraticas
Proposic~ao 12.2: Vericac~ao da exist^encia de soluc~ao de uma
congru^encia quadratica
Sejan=p
r1
1
p
rs
sa decomposic~ao denfatores primos, a
congru^enciaX
2
a mod nadmite soluc~ao se e somente se, cada
congru^encia, separadamente, da famlia abaixo admitir soluc~ao:
X
2
a mod p
ri
i
;i= 1; :::;s:
54 / 57

55. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Quadraticas
Resoluc~ao de Congru^encias Quadraticas
Observac~ao sobre resoluc~ao de congru^encias quadraticas
A resolutividade ou n~ao da congru^encia (I)
AY
2
+BY+C0mod N;(I)
reduz-se ao problema da resolutividade ou n~ao de congru^encias do
tipo
X
2
a mod p
r
;
em quepe primo ep6 ja:
Alem disso, quandope mpar, temos:
Proposic~ao:
Dadosa;p;r2Z;r2,pe primo mpar ep6 ja. A congru^encia
X
2
a mod p
r
admite soluc~ao e se somente se, a congru^encia
X
2
a mod padmite soluc~ao. 55 / 57

56. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Quadraticas
Resoluc~ao de Congru^encias Quadraticas
Exemplo: Resolver a congru^encia a seguir.
8X
2
+ 5X+ 10mod23:
Resoluc~ao:Dica: Completar quadrados.
56 / 57

57. Congru^encias Lineares
Congru^encias Quadraticas
Resoluc~ao de Congru^encias Quadraticas
Resoluc~ao de Congru^encias Quadraticas
Exemplo: Resolver a congru^encia a seguir.
8X
2
+ 5X+ 10mod23:
Resoluc~ao:Dica: Completar quadrados.
Multiplicar a congru^encia por4a, ou seja, por 48:
488X
2
+ 485X+ 4810mod23:
48
2
X
2
+ 2285X+ 320mod23:
(28X)
2
+ 2285X+ 5
2
5
2
+ 320mod23:
(16X+ 5)
2
25 + 320mod23$(16X+ 5)
2
+ 70mod23:
(16X+ 5)
2
7mod23$(16X+ 5)
2
16mod23:
23j(16X+ 5)
2
16. Da, temos duas opc~oes:
23j(16X+ 5)4$16X 1mod23$X10mod23
ou
23j(16X+ 5) + 4$16X 9mod23$X21mod23
Dessa maneira, 10 e 21 s~ao as unicas soluc~oes incongruentes de
8X
2
+ 5X+ 10mod23:
57 / 57