EP5 CRIPTOGRAFIA 2014. 2 gabarito - CEDERJ

Prévia do material em texto

a5 Lista de exercícios Programados de Criptografia-2-2014 
 
1. Encontre D (60), D (60) + , D (60) − . 
RESOLUÇÃO: D (60) = {m∈Z / m é divisor de 60} = { ± 1, ± 2, ± 3, ± 4, ± 5, 
± 6, ± 10, ± 12, ± 15, ± 18, ± 20, ± 30, ± 60}. 
D (60) + = {m∈Z / m > 0 e m é divisor de 60} = {1, 2, 3, 4, 5, 6, 10, 12, 15, 18, 
20, 30, 60}. 
D (60) − = {m∈Z / m < 0 e m é divisor de 60} = {-1, -2, -3, -4, -5,-6, -10, -12, -
15, -18, -20, -30, -60}. 
2. Quantos divisores tem um número primo p? 
RESOLUÇÃO: Por definição um número primo p é divisível pelos números 
± 1, por ele próprio e por seu simétrico -p. Assim um número primo tem 
apenas 4 divisores. 
3. Dê exemplos de inteiros positivos n tal que nn =)( + D 
RESOLUÇÃO: Se n = 1 então D(1) + = {1} e portanto |D(1) + | = 1 
Se n = 2 então D(2) + = {1,2} e portanto |D(2) + | = 2. 
4. Prove que se ∈∀ ba, Z e ∃r,s ∈ Z tais que ra + sb = 1 então 
mdc (a,b) = 1 
RESOLUÇÃO: Sejam a e b∈Z . Assim, pela hipótese ∃r,s ∈ Z tais que ra + 
sb = 1. 
Supõem-se por absurdo que mdc (a,b) = d≠ 1. Logo d | a e d | b. Logo d | ra e 
d | sb. Tem-se então que d | (ra + sb), assim pela hipótese d | 1. Portanto, 
como d é positivo, d = 1. Conclui-se então que mdc (a,b) = 1. 
 
5. Use o Algoritmo da Divisão de Euclides para provar que: 
Todo inteiro ímpar é da forma 4k + 1 ou 4k + 3 
RESOLUÇÃO: Seja n um inteiro ímpar. Devemos mostrar que n = 4k+1 ou n = 
4k+3. Pelo Algoritmo da Divisão, ∈∃ rk , Z, tal que n = 4k + r onde 30 ≤≤ r , 
como n é ímpar r não pode ser múltiplo de 2 . Assim r≠ 0 e r≠ 2, então r =1 
ou r = 3. Tem-se portanto que n = 4k + 1 ou n = 4k + 3. 
 6. Usar o algoritmo da divisão para provar que de três inteiros consecutivos, 
um é múltiplo de 3 
RESOLUÇÃO: Considere a, a+1, a+2 inteiros consecutivos. Devemos mostrar 
que sempre um destes 3 números é múltiplo de 3. 
Pelo algoritmo de Euclides a = 3q + r , 30 <≤ r . Assim r = 0, r = 1, r = 2 
Se r = 0, então a é múltiplo de 3. 
Se r =1, então a+2 = 3q + 1 + 2 = 3 (q + 1) é múltiplo de 3 
Se r = 2, então a + 1 = 3q + 2 +1 = 3 (q + 1) é múltiplo de 3. 
Concluíse então o desejado. 
 
7. Determine: 
a) o número de múltiplos de 2 menores ou iguais à 432. 
RESOLUÇÃO: Como 432 é múltiplo de 2, então 432=2n. 
Por outro lado, os múltiplos de 2 menores ou iguais à 432 são os números: 
O primeiro múltiplo é:2, 
O segundo múltiplo é: 4, 
O terceiro múltiplo é: 6, 
O n –ésimo múltiplo é: 2n = 432 
Desta forma, n é o número de múltiplos de 2 menores ou iguais à 432, 
mas n=432/2 = 216. Assim o número de múltiplos de 2 menores ou iguais à 
432 é 216 
b) o número de múltiplos de 3 menores ou iguais à 432. 
RESOLUÇÃO: Analogamente ao exercício anterior, 
Como 432 é múltiplo de 3, então 432=3n. 
Por outro lado, os múltiplos de 3 menores ou iguais à 432 são os números: 
O primeiro múltiplo é:3, 
O segundo múltiplo é: 6, 
O terceiro múltiplo é: 9, 
... 
O n –ésimo múltiplo é: 3n =432 
Desta forma, n é o número de múltiplos de 3 menores ou iguais à 432, 
mas n=432/3 = 144. Assim o número de múltiplos de 3 menores ou iguais à 
432 é 144 
c) Mostre que se m, n e k são inteiros positivos e m =kn então o número de 
múltiplos de k menores que m é n. 
RESOLUÇÃO: Tem-se que n = km 
Por outro lado, os múltiplos de k menores ou iguais à n são os números: 
Caso k < m, o primeiro múltiplo é: k, 
Caso 2k < m, o segundo múltiplo é: 2k, 
.... 
Assim, o n –ésimo múltiplo é: kn=m 
Desta forma, n é o número de múltiplos de k menores ou iguais à m=kn, 
 
8. Sejam a, b inteiros, d = mdc (a,b) e c um inteiro positivo. Prove que : 
 mdc (ac,bc) = d c 
RESOLUÇÃO: Suponhamos que d = mdc (a,b), assim pela definição de mdc, 
d | a e d | b. Então existem r e s tais que d = ra + sb. Logo dc = r (a c) + s (b 
c). Portanto dc divide ac e dc divide bc. Além disso, se d’ é um inteiro tal 
que d’| ac e d’| bc tem-se que d’| dc e portanto d’< dc. Logo dc é o maior 
divisor comum de ac e bc. 
 
9. Prove o Teorema de Euclides: Sejam a, b e c inteiros com c > 0, tais que 
a | bc. Se mdc (a,b) = 1 então a | c. 
RESOLUÇÃO: Sejam a, b e c inteiros com c > 0, tais que a | bc. Pela hipótese 
mdc(a,b) = 1. Pelo exercício anterior tem-se que mdc (ac,bc) = c. 
É claro que a | ac e, da hipótese a | bc, isto é a é divisor comum de ac e bc . 
Assim, tem-se que a | c. 
 
 10. Seja r≠ 0, uma raiz inteira do polinônio baxx ++2 , onde a,b são 
inteiros. 
 Mostre que r é divisor de b. 
RESOLUÇÃO: Seja r é raiz inteira do polinômio baxx ++2 . 
Assim 02 =++ barr . 
Logo rarb ).( −−= 
Portanto br | 
 11. Mostre que se k é um inteiro positivo então kk +2 é par. 
RESOLUÇÃO: Suponhamos que k é um inteiro positivo, assim, k = 2n ou 
k = 2n+1. 
Se k = 2n, então )2(2242)2( 2222 nnnnnnkk +=+=+=+ , e assim kk +2 é par. 
Se k = 2n+1, então )132(21214412)12( 2222 ++=++++=+++=+ nnnnnnnkk , 
e assim kk +2 é par. 
 12. Seja a um inteiro ímpar positivo. Mostre que 12 −a é sempre divisível 
por 8. 
RESOLUÇÃO: De fato, suponhamos que a seja um inteiro ímpar positivo. 
Assim existe k inteiro positivo tal que a = 2k+1. Logo k≥0. 
Se k = 0, o resultado segue imediato. 
Consideremos k>0. Tem-se que: 
)(444)22)(2()1)(1(1 222 kkkkkkaaa +=+=+=+−=− . 
Pelo exercício anterior kk +2 é par. 
Logo kk +2 =2n, assim 
nnkka 82.4)(41 22 ==+=− 
 13. Sejam a, b e c inteiros não nulos. Prove que se a divide b e a divide c 
 então a divide (b± c). Vale a recíproca? 
RESOLUÇÃO: Sejam a,b e c∈Z . Se a | b então existe k∈Z tal que 
b = k.a e como a | c então existe m∈Z tal que c = m.a.. assim b ± c = k.a 
± m.a = (k ± m).a. 
A recíproca é: Se a divide (b± a) então a divide b e a divide c. 
A reciproca não é verdadeira. 
Considere o contra-exemplo: a =2, b=1 e c =3 
2 |(1+3), porém 2 não divide 1 nem 2 divide 3. 
 14. Seja p um número primo, e sejam a e b inteiros. Mostre que: 
a) Se p não divide a então mdc (p,a) = 1 
 RESOLUÇÃO: Como p é primo tem-se que a não divide p. Se pela 
hipótese p não divide a, então o único divisor comum de a e p é 1. Assim tem-
se que mdc (p,a) = 1. 
b) Se p | ab então p | a ou p | b 
 RESOLUÇÃO: Supõem-se que p | ab. Se p | a a tese esta verificada. 
Caso contrário, da parte anterior tem-se que mdc (p,a) =1, do Teorema de 
Euclides segue que p | b. 
 15. Sejam a,b inteiros positivos e n inteiro não negativo, com a > b > 0. Use 
 o Princípio da Indução Matemática para provar que: 
)(| nn baba −− 
RESOLUÇÃO: 
Hipótese de indução: Se n=0, a-b divide 000 =− ba 
Base de indução: Suponhamos que )(| kk baba −− . 
Devemos mostrar que )(| 11 ++ −− kk baba 
).().(....11 kkkkkkkkk babababbababaaba −+−=−+−=− ++ 
Como (a-b) | (a-b) e )(| kk baba −− , então ).().(| kkk babababa −+−− , e 
assim )(| 11 ++ −− kk baba . 
Pelo Primeiro Princípio da Indução Matemática )(| nn baba −− 
 16. Verifique que : 
a) mdc(10,15) = 5 
RESOLUÇÃO: D(10) = {1,2,5,10} e D(15) = {1,3,5,15} 
mdc (10,15) = máx D(10)∩ D(15) = máx{1,5}= 5 
b) mdc (n,n) = n, para todo inteiro positivo n 
RESOLUÇÃO: Seja n um inteiro positivo. Tem-se que n ∈ D(n), portanto 
n∈ D(n) ∩ D(n). Além disso, n é o maior divisor de n, assim mdc (n,n) = n 
c) mdc (1,n) = 1, para todo inteiro positivo n 
RESOLUÇÃO: D(1) = {1}, e para todo n inteiro positivo 1∈ D(n). Assim D(1) 
∩ D(n)= {1}. Conclui-se então que mdc (1,n) = 1 
d) mdc (p,q) = 1 para todo p e q primos distintos 
RESOLUÇÃO: Pela definição de número primo, D(p) = { ± 1, ± p} e D(q) = { ± 1, 
± q}. Assim se p é diferente de q, D(p) ∩ D(q) = { ± 1}. Portanto mdc (p,q) = 1 
 e) mdc (70,121) = 1 
RESOLUÇÃO: D(70) = {1,2,5,7,10,14,35,70}e D(121) = {1,11,121} 
mdc (70,121) = max D(70)∩ D(121) = 1 
 
 17. Determine os conjuntos D(156) e D(130).Encontre d=mdc (156,136) e 
verifique que d é múltiplo de todos os elementos de D(156) ∩ D(130). 
RESOLUÇÃO: 
 D (156) = {m∈Z / m é divisor de 156} = { ± 1, ± 2, ± 3, ± 4, ± 6, ± 12, 
 ± 13, ± 26, ± 39, ± 52, ± 78, ± 156}. 
 D (136) = {m∈Z / m é divisor de 136} = { ± 1, ± 2, ± 4, ± 8, ±17 ± 34, 
 ± 68, , ± 136}. 
 D(156) ∩ D(130) = { ± 1, ± 2, ± 4} 
 mdc(156,136) = 4 
 Como 4 é múltiplo de ± 1, ± 2, ± 4, então 4 é múltiplo de todos os 
 elementos de D(156) ∩ D(130). 
 18.Escolha alguns pares de inteiros a e b e verifique que 
1),(,),( =




bamdc
b
bamdc
a
mdc 
RESOLUÇÃO: Sejam a = 156 e b = 136, assim d = 4, logo 
34136,39156 ==
dd
, como mdc (39,34) = 1, tem-se que mdc 1136,156 =





dd
. 
1),(,),( =




bamdc
b
bamdc
a
mdc 
 
 19. Sejam naaa ,..., 21 inteiros positivos. Generalize a noção de mdc de dois 
 inteiros , definindo de modo similar mdc( naaa ,..., 21 ). 
RESOLUÇÃO: Diz-se que o número d é o máximo divisor comum dos 
inteiros naaa ,..., 21 se : 
1. d é um divisor comum de naaa ,..., 21 , isto é, d divide cada um dos ia , 
i = 1,2,...,n. 
2. d é o maior divisor comum, isto é, se b é um outro divisor comum 
de naaa ,..., 21 então b≤ d 
 20. Seja a um número inteiro. Prove que mdc ( 14,12 2 ++ aa ) = 1 
 RESOLUÇÃO: Se d = mdc ( 14,12 2 ++ aa ) então d≠ 0 e d | 12 +a e d 
| 14 2 +a . Assim existe k 1 , k 2 ∈Z, k 1 ≠ k 2 , tal que 12 +a = k 1d e 14
2 +a = k 2 d. 
Portanto 
d
kdkkdkdkdkdkdkdkdkdka 222)2(1121)1(12 1212212112212211 +−=⇒=+−=++−⇒=+−⇒−=
Como 2k é inteiro então d = 1 ou d = 2. 
Se d = 1, concluiu-se o desejado. 
Por outro lado, d = 2 é impossível pois 2a +1 é ímpar e por hipótese d |2a + 1 
 
 21. Sejam a, b e c inteiros tais que a | b e mdc(b,c) =1.Prove que: 
mdc(a,c) = 1 
RESOLUÇÃO: 
Se a | b então existe n inteiro tal que b = na. 
Seja x = mdc (a,c). Assim x | a e x | c. 
Sendo assim x | b. 
Logo x | mdc(b,c), isto é x | 1, e assim x = 1 ou x = -1. Como x = mdc(a,c) então 
x =1. 
 22. Sejam a,b ∈Z + tais que mdc(a,b) =1. Prove que: 
mdc (a + b,a - b) = 1 ou 2 
RESOLUÇÃO: Seja x = mdc (a + b,a - b), assim x | (a+b) , x | (a-b) e x > 0 
Logo existem m e n ∈Z + tais que a+b = m.x e a-b = nx. 
Tem-se então que 2a = (m +n).x e 2b = (m-n).x. 
Sendo assim x | 2a e x | 2b, logo x | mdc(2a,2b). 
Assim x | 2. 
Logo x = 1 ou x =2