MAT1310_Lista2
4 pág.

MAT1310_Lista2


DisciplinaMatemática Discreta4.195 materiais81.690 seguidores
Pré-visualização1 página
MAT1310 \u2013 Matema´tica Discreta - 2012.1 PUC-Rio
Lista de Exerc´\u131cios II
1. Prove as propriedades:
(a) 1 | a, a | a, a | 0.
(b) [ a | b \u2227 b | c ] \u21d2 a | c.
(c) [ a | b \u2227 c | d ] \u21d2 a · c | b · d.
(d) a | (b+ c) \u21d2 [ a | b \u21d4 a | c ].
(e) a | b \u21d2 |a| \u2264 |b|.
(f) [ d | a \u2227 d | b ] \u21d2 d | (a x+ b y).
2. O algoritmo de Euclides estendido pode ser escrito da seguinte forma: dado a e b,
construa uma seque\u2c6ncia rn por:
r0 = a
r1 = b
\u2200i > 0, ri\u22121 = ri · qi + ri+1 e 0 \u2264 ri+1 < ri .
O algoritmo pa´ra no passo i tal que ri+1 = 0
(a) Enumere os passos do algoritmo no caso que a = 42 e b = 9.
(b) Mostre no caso geral que, a cada passo do algoritmo, o maior divisor comum e´
preservado: \u2200i, ri+1 6= 0\u21d2 mdc(a, b) = mdc(ri, ri+1).
3. Deseja-se comprar exatamente 1000 gramas de um produto que e´ vendido em embalagens
de 19 e 33 gramas. Apresente todas as possibilidades de compra deste produto (se
existirem).
4. De quantos modos podemos comprar selos de cinco e de tre\u2c6s reais, de modo a gastar
cinquenta reais?
5. Ache todos os pontos de coordenadas inteiras das seguintes retas:
(a) 14x+ 91y = 3.
(b) 12x+ 105y = 6.
6. Considere a reta plana r de equac¸a\u2dco a ·x = b · y, com a e b inteiros positivos. Os pontos
de coordenadas inteiras (0, 0) e (b, a) pertencem a` reta r. Mostre que existe um ponto
com coordenadas x e y inteiras com 0 < x < b se e somente se mdc(a, b) 6= 1.
7. Uma pessoa multiplicou a data do dia do seu nascimento por 12 e o nu´mero que indica
o me\u2c6s do nascimento por 31 obtendo 689. Qual o dia/me\u2c6s do aniversa´rio desta pessoa ?
8. Mostre que quaisquer dois elementos consecutivos Fn e Fn+1 para n \u2265 3 na seque\u2c6ncia
de Fibonacci sa\u2dco primos entre si, lembrando que F0 = 0, F1 = 1 e Fn+2 = Fn+1 + Fn.
9. Os nu´meros de Fermat sa\u2dco definidos por Fn = 2
2n+1, isto e´, F0 = 3, F1 = 5, F2 = 17,. . .
(a) Prove que Fn+1 = 2 + F0F1 · · ·Fn.
(b) Mostre que quaisquer dois nu´meros de Fermat distintos sa\u2dco primos entre si.
Nota histo´rica: Pierre de Fermat (1601?\u20131665) conjecturou que esta fo´rmula produzia apenas nu´meros
primos. Isso de fato funciona para 0 \u2264 n \u2264 4. A conjectura foi refutada por Leonhard Euler, que
mostrou (em 1732) que fatorou F5 = 641 · 6700417.
10. (a) Prove que para todo n nu´mero natural, n \u2265 1, a seque\u2c6ncia (n+ 1)! + 2, (n+ 1)! +
3, (n+ 1)! + 4, . . . , (n+ 1)! + (n+ 1) na\u2dco tem nenhum nu´mero primo.
(b) Mostre que (n+ 1)! + (n+ 2) pode ser primo.
11. Determine o resto da divisa\u2dco de 3355640 por 641.
12. Determine o resto da divisa\u2dco de (111111 + 222222 + 333333)444 por 7.
13. Determine o resto da divisa\u2dco de 2122 · 7203 + 58 por 9.
14. Determine o algarismo das unidades de 37100.
15. Determine o algarismo das unidades de 2x, onde x = 32010.
16. Determine o algarismo das unidades de 7x onde x = 191002.
17. Determine o menor inteiro positivo x de modo que 3221 · 7343 \u2212 x seja divis´\u131vel por 4.
18. Determine o algarismo das unidades de 177219
2011
.
19. Prove se verdadeiro ou apresente um contra-exemplo caso falso.
(a) Se p e´ primo tal que mdc(a, p) = 1 e ab \u2261 ac mod p enta\u2dco b \u2261 c mod p.
(b) Se n e´ um nu´mero inteiro \u131´mpar enta\u2dco 209n e´ mu´ltiplo de 9.
20. Verdadeiro ou falso? Justifique sua resposta!
(a) Sejam a, b e m inteiros com m \u2265 2. Vale ab \u2261 0 mod m se e somente se a \u2261
0 mod m ou b \u2261 0 mod m.
(b) Se a \u2261 b mod m e a\u2032 \u2261 b\u2032 mod m\u2032 enta\u2dco aa\u2032 \u2261 bb\u2032 mod mm\u2032.
(c) Sejam a, b e m inteiros positivos. Enta\u2dco a2 \u2261 b2 mod m se e somente se a \u2261
b mod m.
(d) Se a, b e m sa\u2dco inteiros com m \u2265 2 enta\u2dco (a+ b)m \u2261 am + bm mod m.
21. Encontre o inverso multiplicativo de 62420 + 4128 mo´dulo 103.
22. (a) Fac¸a uma tabela de inversos multiplicativos mo´dulo 11, usando apenas os nu´meros
de 0 a 10.
(b) Encontre todas as soluc¸o\u2dces do sistema:
2x+ 3y \u2261 1 mod 11
x+ 4y \u2261 4 mod 11
23. Seja um nu´mero n, e seja p a soma dos seus algarismos. Mostre, usando aritime´tica
mo´dulo 9, que n e´ divis´\u131vel por 9 se e somente se p e´ mu´ltiplo de 9.
24. Escrevemos os algarismos 1, 2, 3, 4, 5 (nessa ordem) cinquenta vezes. Chamemos de x
o nu´mero obtido, isto e´, x = 1234512345. . .12345. Qual o resto da divisa\u2dco de x por 9?
25. Determine que nu´meros possuem raiz quadrada mo´dulo 11. (Isto e´, determine para
quais inteiros a existe algum x tal que x2 \u2261 a mod 11.)
26. Seja p um nu´mero primo e n \u2208 N\u2217. Mostre que existe um inverso multiplicativo de a
mo´dulo p se e somente se existe um inverso multiplicativo de a mo´dulo pn.
27. Demonstrar o teorema de Wilson:
Um nu´mero inteiro p > 1 e´ primo, se e somente se, (p\u2212 1)! \u2261 \u22121 mod p.
28. Determine todas as soluc¸o\u2dces dos seguintes sistemas:
{
x \u2261 2 mod 3
x \u2261 3 mod 10
\uf8f1\uf8f2\uf8f3
x \u2261 3 mod 4
x \u2261 7 mod 3
x \u2261 10 mod 5
\uf8f1\uf8f2\uf8f3
x \u2261 3 mod 4
x \u2261 7 mod 6
x \u2261 10 mod 5
29. Seja n = p1 · p2 · . . . · pk, com p1, p2, . . . , pk nu´meros primos distintos.
(a) Seja \u3d5(n) = (p1 \u2212 1) · (p2 \u2212 1) · . . . · (pk \u2212 1) 1. Mostre, usando o teorema chine\u2c6s
dos restos, que
\u2200i, a 6\u2261 0 (mod pi) \u2192 a\u3d5(n) \u2261 1 (mod n) .
(b) Mostre um contra-exemplo caso p1 = p2.
30. Determinar todos os naturais menores que 3000 que te\u2c6m resto 9 na divisa\u2dco por 37 e
simultaneamente resto 15 na divisa\u2dco por 52.
31. Prove que os inteiros k e k5 te\u2c6m o mesmo algarismo das unidades.
32. Considere um co´digo RSA definido por xc \u2261 y mod N onde N = 91 e c = 29.
(a) Codifique 51.
(b) Decodifique 10.
33. Suponha, que num processo de criptografia RSA, tenhamos escolhido os primos p = 7,
q = 11 e o expoente de codificac¸a\u2dco c = 7. Encontre um coeficiente de decodificac¸a\u2dco d
adequado.
34. Considere um co´digo RSA definido pela func¸a\u2dco f(x) \u2261 xc mod 161.
(a) Sabendo que 161 = 7 · 23, decida, justificando, qual dos valores a seguir pode ser o
valor de c: 3, 11 ou 13.
(b) Considere agora c = 5, codifique 24.
(c) Ainda considerando c = 5, decodifique 8.
1caso particular da func¸a\u2dco totiente de Euler.
35. Considere um co´digo RSA definido pela func¸a\u2dco f(x) = xc mod 91.
(a) Sabendo que 91 = 7 · 13 e 31 < c < 37, determine o valor de c.
(b) Codifique 10 e 20.
(c) Decodifique 25 e 15.
36. Considere um co´digo RSA definido pela func¸a\u2dco de codificac¸a\u2dco f(x) = xc mod 1517.
(a) Sabendo que 1517 = 37 · 41 e 127 < c < 133, determine o valor de c.
(b) Codifique 500.
(c) Determine o expoente d a func¸a\u2dco de decodificac¸a\u2dco f(y) = yd mod 1517.
(d) Decodifique 5.
37. Uma frase foi convertida na seque\u2c6ncia de nu´meros
2510271029349914992118231310
da seguinte forma: a letra A foi convertida em um nu´mero n com dois algarismos, B em
n+ 1, e assim por diante; tambe´m foi usado um nu´mero para espac¸os em branco.
(a) Qual e´ a frase?
(b) Considere o co´digo RSA definido pela func¸a\u2dco f(x) = xc mod 143, onde c e´ o menor
valor poss´\u131vel. Determine o valor de c.
(c) Quebre a seque\u2c6ncia de nu´meros em blocos com valores menores que 143 e codifique
cada bloco usando o co´digo RSA do item anterior.
38. Usando a func¸a\u2dco de decodificac¸a\u2dco g(y) = y103 mod 143, decifre:
64\u2212 119\u2212 6\u2212 119\u2212 102\u2212 36\u2212 130\u2212 36\u2212 27\u2212 79\u2212 23\u2212 117\u2212 10 .
39. Com um mo´dulo pequeno a RSA na\u2dco e´ segura. Na pra´tica, usar primos de 100 d´\u131gitos
ainda na\u2dco garantiria a seguranc¸a. Para ilustrar, sabendo que foram usados na RSA dois
nu´meros primos menores que o nu´mero 16, tente decifrar a palavra que foi codificada
nos nu´meros abaixo:
53\u2212 2\u2212 12