Lista 2

Prévia do material em texto

Matema´tica Discreta I
Lista 02: Teoria dos Nu´meros
01. Ler o livro “Nu´meros Inteiros e Criptografia RSA”, Cap´ıtulos 1, 2, 4, 7, 11. Resolva os exerc´ıcios 1–9 da
p.32, 2–10 da p.85, 1–7 da p.129 e 1–4 da p.191.
02. Mostre que
(a) 31 | 2015 − 1 (b) 61 | 2015 − 1
(c) 641 | 232 + 1 (d) 13 | 270 + 370
(e) 23n+1 − 2 e´ mu´ltiplo de 7 para todo n ≥ 0 (f) 23n+2 + 3 e´ mu´ltiplo de 7 para todo n ≥ 0
03. Determine os dois u´ltimos d´ıgitos (na notac¸a˜o decimal) de
(a) 3100 (b) 22008
(c) 37
2008
(d) 22n(22n+1 − 1) para n ≥ 1 ı´mpar
04. Encontrar os 4 u´ltimos d´ıgitos de 32008 na notac¸a˜o decimal.
Dica: para reduzir as contas, aplique o binoˆmio de Newton em (10− 1)1004.
05. Seja A a soma dos d´ıgitos de 44444444 quando escrito na notac¸a˜o decimal. Seja B a soma dos d´ıgitos de
A. Encontre a soma dos d´ıgitos de B.
06. Calcule:
(a) (14, 35) (b) (252, 180)
(c) (6643, 2873) (d) (272828282, 3242)
07. Para cada um dos pares de nu´meros (a, b) do exerc´ıcio anterior, encontre todas as soluc¸o˜es da equac¸a˜o
diofantina linear ax + by = (a, b).
08. Calcule
(a) (n, 2n + 1)
(b) (2n + 1, 3n + 1)
(c) (n! + 1, (n + 1)! + 1)
(d) (Fn, Fn+1), onde Fk denota o k-e´simo nu´mero de Fibonacci.
(e) (320 − 1, 3100 − 1)
(f) (2200 + 1, 22009 + 1)
09. Encontre o inverso multiplicativo (ou mostre que ele na˜o existe):
(a) 7 mod 13 (b) 12 mod 143
(c) 22 mod 121 (d) 19 mod 200
(e) 79 mod 101 (f) 20 mod 103
10. Resolva os sistemas de congrueˆncias:
(a)
∣∣∣∣∣x ≡ 10 (mod 21)x ≡ 2 (mod 52) (b)
∣∣∣∣∣∣∣
x ≡ 1 (mod 2)
x ≡ 2 (mod 5)
x ≡ 5 (mod 12)
11. Mostre que a equac¸a˜o diofantina x2 − 7y2 = 3 na˜o tem soluc¸o˜es inteiras.
12. Mostre que se x e y sa˜o tais que N = (x+ 6y)(2x+ 5y)(3x+ 4y) e´ divis´ıvel por 7 enta˜o N e´ mu´ltiplo de
343.
13. Prove o seguinte crite´rio de divisibilidade por 7: dado um inteiro n, seja d o u´ltimo d´ıgito de n e m o
nu´mero obtido a partir de n apagando-se o u´ltimo d´ıgito d; enta˜o n e´ divis´ıvel por 7 se, e somente se, m−2d
e´ divis´ıvel por 7. Por exemplo, para n = 8638, temos 863− 2 · 8 = 847 e 84− 2 · 7 = 70, que e´ divis´ıvel por
7, logo 8638 e´ divis´ıvel por 7 tambe´m.
1
14. Mostre que
S = 16 + 26 + 36 + · · ·+ 1006
e´ divis´ıvel por 101.
Dica: Multiplique S por 26.
15. No algoritmo RSA, dada a chave pu´blica n e expoente codificador e, encontre o expoente decodificador
d e utilize-o para decodificar as seguintes mensagens encriptadas m:
(a) n = 7 · 31, e = 17, m = 10 (b) n = 11 · 23, e = 17, m = 12
(c) n = 11 · 13, e = 17, m = 10 (d) n = 17 · 29, e = 17, m = 12
16. Mostre que existem infinitos nu´meros da forma 19999 . . . 99991 que sa˜o mu´ltiplos de 1991.
17. Mostre que existe uma poteˆncia de 2 que, quando escrito na notac¸a˜o decimal, possui pelo menos 2008
zeros consecutivos.
Dica: aplique o teorema de Euler-Fermat mo´dulo 5k.
18. Mostre que
(a) na˜o existe x inteiro tal que 43 | x2 + 1 (b) na˜o existe x inteiro tal que 103 | x3 − 2
(c) se 43 | x2 + y2 enta˜o 43 | x e 43 | y (d) se 103 | x3 − 2y3 enta˜o 103 | x e 103 | y
Dica: utilize o teorema de Euler-Fermat.
19. Determine todos os inteiros positivos m e n tais que
m2 + 161 = 3n
2