Departamento de Matemática da Universidade de Coimbra Teoria dos Números Ano lectivo 2005/2006 Folha 4 41. ? Prove que se n > 1 é um número natural e n | (n − 1)! + 1 então n é primo. 42. ? Quais são os primos p para os quais também p2 + 2 é primo? 43. Para a ∈ N, designamos por τ (a) o número de divisores positivos de a (incluindo 1 e a). Sabendo que 3 | a , 4 | a e τ (a) = 14 , determine a. 44. Determine o menor inteiro positivo n que tem exactamente: (a) 6 divisores positivos; (b) 13 divisores positivos; (c) 15 divisores positivos. 45. Prove que, se (a, b) = 1, então τ (ab) = τ (a)τ (b) . 46. Calcule os valores de τ (n) para n ≤ 20 . 47. Seja a > 1 um número inteiro cuja decomposição canónica é do tipo pα1 1 pα2 2 e tal que τ (a2 ) = 81. Determine τ (a3 ) . 48. Sendo n > 1 um inteiro positivo qualquer, prove que existe uma infinidade de números inteiros positivos com exactamente n divisores positivos. 49. Seja n um inteiro positivo. Prove que τ (n) é ı́mpar se e só se n é um quadrado perfeito. 50. ? Prove que, para n ∈ N, o produto dos divisores positivos de n é igual a nτ (n)/2 . 51. Use o crivo de Eratóstenes para determinar todos os números primos inferiores a 200 . 52. Calcule os valores de π(n) para n ≤ 20 . 53. ? Prove que lim π(x) = +∞. x→+∞ Capı́tulo 4: Congruências 54. Sejam m, m1 , m2 ∈ N. Prove que, quaisquer que sejam os inteiros indicados, se tem: (a) a ≡ a (mod m) ; (b) a ≡ b (mod m) =⇒ b ≡ a (mod m) ; (c) a ≡ b (mod m) ∧ b ≡ c (mod m) =⇒ a ≡ c (mod m) ; (d) a ≡ b (mod m) ∧ c ≡ d (mod m) =⇒ a + c ≡ b + d (mod m) ; (e) a ≡ b (mod m) ∧ c ≡ d (mod m) =⇒ ac ≡ bd (mod m) ; (f) a ≡ b (mod m1 ) ∧ m2 | m1 =⇒ a ≡ b (mod m2 ) ; (g) a ≡ b (mod m) =⇒ (a, m) = (b, m) ; (h) a ≡ b (mod m1 ) ∧ a ≡ b (mod m2 ) =⇒ a ≡ b (mod [m1 , m2 ]) . 55. Determine todos os inteiros entre 1 e 100 que são congruentes com 7 módulo 17. 56. Determine todos os inteiros x entre 0 e 6 que satisfazem 3x ≡ 1 (mod 7) . 57. Prove que 7 | 313 + 28 . 58. Determine o resto da divisão de (a) (116 + 17)21 por 8; (b) 14256 por 17; (c) 1316 − 225 · 515 por 37; (d) (3810 + 5)31 por 37; (e) 3100 por 101; (f) 1316 − 225 · 515 por 3. 59. (Critérios de divisibilidade por 3, 9, 11 e 7) Seja n um número natural e sejam ak , ak−1 , . . . , a2 , a1 , a0 os algarismos da representação decimal de n. Isto é, tem-se ak , ak−1 , . . . , a2 , a1 , a0 ∈ {0, 1, 2, . . . , 9} e n = ak 10k + ak−1 10k−1 + · · · + a2 102 + a1 10 + a0 . Prove que: (a) n é divisı́vel por 3 se e só se ak + ak−1 + · · · + a2 + a1 + a0 o for; (b) n é divisı́vel por 9 se e só se ak + ak−1 + · · · + a2 + a1 + a0 o for; (c) n é divisı́vel por 11 se e só se (−1)k ak + (−1)k−1 ak−1 + · · · + a2 − a1 + a0 o for; (d) Sendo r = ak 10k−1 + ak−1 10k−2 + · · · + a2 10 + a1 − 2a0 , n é divisı́vel por 7 se e só se r o for. (r obtém-se de n retirando o algarismo das unidades, a0 , e subtraindo, a esse novo número, 2a0 . Por exemplo, se n = 1536 então r = 153 − 12 = 141.) 60. Justifique a “prova dos noves” para a adição e multiplicação de inteiros, expressos no sistema decimal de numeração. 61. Verifique que os inteiros da forma mk = 10k + · · · + 102 + 10 + 1, com k > 1 e ı́mpar, são todos compostos. 62. Prove que um quadrado perfeito tem por algarismo das unidades 0,1,4,5,6 ou 9. 63. Prove que uma quarta potência tem por algarismo das unidades 0,1,5 ou 6. 64. Determine o último dı́gito de 3400 e de 2400 .