Lista 5_Teoria dos Números

Prévia do material em texto

Curso: Ciência da Computação (1º Semestre) 
Disciplina: Matemática Discreta (PEPMDIS) 
Professor Fabricio F. Alves 
 
Lista 5: Teoria dos Números 
1. O número 17 divide cada um dos números abaixo? 
a) 68 b) 84 c) 357 d) 1001 
 
2. Mostre que se 𝑎, 𝑏, 𝑐 e 𝑑 são números inteiros, tais que 𝑎|𝑏 e 𝑐|𝑑, então 𝑎𝑐|𝑏𝑑. 
3. Mostre que se 𝑎, 𝑏 e 𝑐 são números inteiros, com 𝑐 ≠ 0, tal que 𝑎𝑐|𝑏𝑐, então 𝑎|𝑏. 
4. Determine o resto e a divisão quando: 
a) 19 é dividido por 7 f) 3 é dividido por 5 
b) −111 é dividido por 11 g) −1 é dividido por 3 
c) 789 é dividido por 23 h) 777 é dividido por 21 
d) 1001 é dividido por 13 i) −123 é dividido por 19 
e) 0 é dividido por 19 
 
5. Seja 𝑎 um número inteiro. Mostre que: 
a) um dos inteiros 𝑎, 𝑎 + 1 ou 𝑎 + 2 é divisível por 3. 
b) um dos inteiros 𝑎, 𝑎 + 2 ou 𝑎 + 4 é divisível por 3. 
6. Mostre que a diferença entre os quadrados de dois números inteiros consecutivos é 
sempre um número ímpar. 
 
7. Calcule: 
a) mdc(20,25) d) mdc(−89, −98) 
b) mdc(0,10) e) mdc(54321,50) 
c) mdc(123, −123) f) mdc(1739,29341) 
 
8. Para cada para de números inteiros 𝑎 e 𝑏 do exercício anterior, determine inteiros 𝑥 e 
𝑦 tais que 𝑎𝑥 + 𝑏𝑦 = mdc(𝑎, 𝑏). 
9. Mostre que dois números inteiros consecutivos são primos entre si. 
 
10. Seja 𝑎 um número inteiro. Prove que 2𝑎 + 1 e 4𝑎2 + 1 são primos entre si. (Dica: 
calcule mdc(2𝑎 + 1 ,4𝑎2 + 1). 
11. Verifique se as afirmações seguintes são verdadeiras ou falsas: 
 
 
a) 7 ≡ 24 (mod 5) c) 529 ≡ −8 (mod 3) 
b) 33 ≡ 57 (mod 6) d) −12 ≡ −72 (mod 8) 
 
12. Estabeleça os critérios de divisibilidade por: 2, 5, 9 e 11. 
 
13. Ache o resto nas seguintes divisões: 
a) 245 por 7 c) 310 ⋅ 425 + 68 por 5 
b) 1110 por 100 d) 1169 por 3 
 
14. Mostre que 220 − 1 é divisível por 41. 
 
15. Resolva as seguintes congruências lineares: 
a) 5𝑥 ≡ 2 (mod 26) e) 20𝑥 ≡ 7 (mod 15) 
b) 3𝑥 ≡ 17 (mod 5) f) 14𝑥 ≡ 36 (mod 48) 
c) 34𝑥 ≡ 60 (mod 98) g) 5𝑥 ≡ −38 (mod 7) 
d) 6𝑥 ≡ 15 (mod 21) h) 20𝑥 ≡ 30 (mod 31) 
 
16. Resolva os seguintes sistemas de congruências simultâneas: 
a) 𝑥 ≡ 1 (mod 3), 𝑥 ≡ 2 (mod 5) e 𝑥 ≡ 3 (mod 7) 
b) 𝑥 ≡ 1 (mod 9), 𝑥 ≡ 5 (mod 7) e 𝑥 ≡ 3 (mod 5) 
c) 3𝑥 ≡ 1 (mod 10) e 4𝑥 ≡ 2 (mod 7) 
d) 𝑥 ≡ 1 (mod 3), 𝑥 ≡ 2 (mod 5) e 2𝑥 ≡ 3 (mod 7) 
e) 2𝑥 ≡ 1 (mod 5), 4𝑥 ≡ 1 (mod 7) e 5𝑥 ≡ 9 (mod 11) 
 
17. Ache o menor número inteiro 𝑎 > 2 tal que: 2|𝑎, 3|(𝑎 + 1), 4|(𝑎 + 2) e 5|(𝑎 + 3). 
(Dica: observe que 2|𝑎 ⟺ 𝑎 ≡ 0 (mod 2); do mesmo modo, as outras condições podem 
ser formuladas em termos de congruências. A seguir, resolva o sistema de congruências) 
 
18. Resolva, mediante o teorema chinês dos restos, os seguintes sistemas: 
a) {
𝑥 ≡ 1 (mod 10)
𝑥 ≡ 4 (mod 11)
𝑥 ≡ 6 (mod 13)
 b) {
𝑥 ≡ 5 (mod 7)
𝑥 ≡ −1 (mod 9)
𝑥 ≡ 6 (mod 10)
 
 
(Algumas) Respostas dos exercícios 
1. .a) Sim; b) Não; c) Sim; d) Não. 
3. Sugestão: Como 𝑎𝑐|𝑏𝑐, então existe um número inteiro 𝑞 tal que 𝑏𝑐 = 𝑎𝑐𝑞. 
4. a) 𝑞 = 2 e 𝑟 = 5; b) 𝑞 = −11 e 𝑟 = 10; c) 𝑞 = 34 e 𝑟 = 7; d) 𝑞 = 77 e 𝑟 = 0 
 e) 𝑞 = 0 e 𝑟 = 0; f) 𝑞 = 0 e 𝑟 = 3; g) 𝑞 = −1 e 𝑟 = 2. 
5. Sugestão: pelo Algoritmo da Divisão, há os seguintes casos para considerar: 𝑎 = 3𝑞, 
𝑎 = 3𝑞 + 1 e 𝑎 = 3𝑞 + 2. 
 
 
6. Sugestão: seja 𝑎 um número inteiro. Prove que 𝑎2 − (𝑎 + 1)2 = 2𝑘 + 1, para algum 
𝑘 ∈ ℤ. 
13. a) resto 1; b) resto 1; c) resto 4; d) resto 2. 14. Sugestão: use congruência módulo 41. 
15. a) {16}; b) {4}; c) {45; 94}; d) {6; 13; 20}; e) ∅; f) {6; 30}; g) {5}; h) {17}. 
16. a) 𝑥 ≡ 52 (mod 105); b) 𝑥 ≡ 208 (mod 315); c) 𝑥 ≡ 67 (mod 70); 
 d) 𝑥 ≡ 82 (mod 105); e) 𝑥 ≡ 268 (mod 385). 
17. 𝑎 = 2 + 60𝑘, 𝑐𝑜𝑚 𝑘 ∈ ℤ; logo a resposta é 62. 
18. a) 𝑥 ≡ 7 ⋅ 1 ⋅ 43 + 5 ⋅ 4 ⋅ 130 + 11 ⋅ 6 ⋅ 110 (mod 1430); 
 b) 𝑥 ≡ 25 (mod 630).