TEORIA DOS NÚMEROS - EXERCÍCIOS DE NÚMEROS PRIMOS
01 – Achar os cinco menores primos da forma n2 – 2.
Solução:
O único par que n pode assumir é dois pois 22 – 2 = 2 (2 é primo).
Qualquer outro valor par para n, n2 – 2 será par pois n par ⇒ n2 é par e, em consequência, não será primo.
Assim, devemos testar, para n > 2, os valores ímpares.
Para n = 3 ⇒ n2 – 2 = 32 – 2 = 9 – 2 = 7 (é primo)
Para n = 5 ⇒ n2 – 2 = 52 – 2 = 25 – 2 = 23 (é primo)
Para n = 7 ⇒ n2 – 2 = 72 – 2 = 49 – 2 = 47 (é primo)
Para n = 9 ⇒ n2 – 2 = 92 – 2 = 79 – 2 = 79 (é primo)
Resposta: 2, 7, 23, 47 e 79.
O único par que n pode assumir é dois pois 22 – 2 = 2 (2 é primo).
Qualquer outro valor par para n, n2 – 2 será par pois n par ⇒ n2 é par e, em consequência, não será primo.
Assim, devemos testar, para n > 2, os valores ímpares.
Para n = 3 ⇒ n2 – 2 = 32 – 2 = 9 – 2 = 7 (é primo)
Para n = 5 ⇒ n2 – 2 = 52 – 2 = 25 – 2 = 23 (é primo)
Para n = 7 ⇒ n2 – 2 = 72 – 2 = 49 – 2 = 47 (é primo)
Para n = 9 ⇒ n2 – 2 = 92 – 2 = 79 – 2 = 79 (é primo)
Resposta: 2, 7, 23, 47 e 79.
02 – Achar três primos ímpares cuja soma seja:
(a) 81.
Solução: Como são primos ímpares, não podemos usar o 2. Consultando a tabela encontramos: ( 17, 41, 23), (13, 31, 37), (3, 37, 41), (11, 23, 47), (3, 7, 71), (3, 61, 17).
Solução: Como são primos ímpares, não podemos usar o 2. Consultando a tabela encontramos: ( 17, 41, 23), (13, 31, 37), (3, 37, 41), (11, 23, 47), (3, 7, 71), (3, 61, 17).
(b) 125
Solução: Consultando a tabela: (97, 11, 17) , (97, 5, 23), (89, 23, 53), (89, 71, 5). Existem vários outros. Para facilitar a procura faz-se 125 – nº primo menor que 125.
Depois procuram-se mais dois primos cuja soma seja igual à diferença obtida.
Solução: Consultando a tabela: (97, 11, 17) , (97, 5, 23), (89, 23, 53), (89, 71, 5). Existem vários outros. Para facilitar a procura faz-se 125 – nº primo menor que 125.
Depois procuram-se mais dois primos cuja soma seja igual à diferença obtida.
03 – Achar todos os pares de primos p e q, tais que p – q = 3.
Solução:
Como p – q é ímpar, p e q devem ter paridades diferentes. Isto é: um dos dois é par e o outro é ímpar. Como o único primo par é 2, a solução única é 5 – 2 = 3, ou seja, p = 5 e q = 2.
Solução:
Como p – q é ímpar, p e q devem ter paridades diferentes. Isto é: um dos dois é par e o outro é ímpar. Como o único primo par é 2, a solução única é 5 – 2 = 3, ou seja, p = 5 e q = 2.
04 – Achar todos os primos que são iguais a um quadrado perfeito menos 1.
Solução: n2 – 1 = (n + 1)( n – 1). (n + 1) e (n – 1) são dois inteiros cuja diferença é 2. Para que n2 – 1 seja múltiplo de dois inteiros e seja primo, um dos inteiros somente pode ser 1. Como n + 1 > n – 1, devemos ter n – 1 = 1 ⇒ n = 2. Assim, n2 – 1 = (2 + 1)(2 – 1) = 3.1 = 3.
05 – Achar todos os primos que são iguais a um cubo perfeito menos 1.
Solução: n3 – 1 = (n – 1)(n2 + n + 1). Seguindo o mesmo raciocínio anterior, n – 1 = 1 ⇒ n = 2.
Portanto: n3 – 1 = 23 – 1 = 7. Resposta: 7.
06 – Determinar todos os inteiros positivos n tais que n, n + 2 e n + 4 são todos primos.
Solução: n não pode ser par pois n = 2k, teríamos n + 2 = 2k + 2 = 2(k + 1) é par, portanto, não é primo. Assim, n, n + 2 e n + 4 são três ímpares consecutivos.
Para n = 3, n + 2 = 5 e n + 4 = 7. 3, 5 e 7 são três primos consecutivos.
Para n > 3, temos n = 3k ou n = 3k + 1 ou n = 3k + 2, com k > 1.
Se n = 3k, n não seria primo pois seria múltiplo de 3.
Se n = 3k + 1, n + 2 = 3k + 1 + 2 = 3k + 3 = 3(k + 1), teríamos n + 2 não primo por ser múltiplo de 3. Se n = 3k + 2, n + 4 = 3k + 2 + 4 = 3.(k + 2), teríamos n + 4 não primo por ser múltiplo de 3. Portanto, o único valor de n é 3. Resposta: 3.
Para n = 3, n + 2 = 5 e n + 4 = 7. 3, 5 e 7 são três primos consecutivos.
Para n > 3, temos n = 3k ou n = 3k + 1 ou n = 3k + 2, com k > 1.
Se n = 3k, n não seria primo pois seria múltiplo de 3.
Se n = 3k + 1, n + 2 = 3k + 1 + 2 = 3k + 3 = 3(k + 1), teríamos n + 2 não primo por ser múltiplo de 3. Se n = 3k + 2, n + 4 = 3k + 2 + 4 = 3.(k + 2), teríamos n + 4 não primo por ser múltiplo de 3. Portanto, o único valor de n é 3. Resposta: 3.
07 – Determinar todos os primos p tais que 3p + 1 é um quadrado perfeito.
Solução: Para p = 2, temos 3p + 1 = 3.2 + 1 = 7 que não é quadrado perfeito.
Os demais primos são ímpares, portanto, 3p + 1 é par pois 3p é ímpar.
Temos (2k)2 = 4k2 = 3p + 1 ⇒ 4k2 – 1 = 3p. Ora, 4k2 – 1 = (2k + 1)(2k – 1) = 3p
Como p é primo, (2k + 1)(2k – 1) somente admitem como fatores 3 e p. Portanto, 2k + 1 = 3 ⇒ p = 2k – 1 = 1, solução que não tem validade pois 1 não é primo, ou 2k – 1 = 3 ⇒ p = 5.
Os demais primos são ímpares, portanto, 3p + 1 é par pois 3p é ímpar.
Temos (2k)2 = 4k2 = 3p + 1 ⇒ 4k2 – 1 = 3p. Ora, 4k2 – 1 = (2k + 1)(2k – 1) = 3p
Como p é primo, (2k + 1)(2k – 1) somente admitem como fatores 3 e p. Portanto, 2k + 1 = 3 ⇒ p = 2k – 1 = 1, solução que não tem validade pois 1 não é primo, ou 2k – 1 = 3 ⇒ p = 5.
08 – Determinar se são primos os números
(a) 169
Solução: Para verificar se um número n é primo devemos dividí-los por todos os primos menores ou iguais a √n, ou então dividí-lo pelos primos até que o quociente se torne maior que o divisor.
√169 = 13. Portanto, 169 não é primo pois admite 13 como divisor.
Solução: Para verificar se um número n é primo devemos dividí-los por todos os primos menores ou iguais a √n, ou então dividí-lo pelos primos até que o quociente se torne maior que o divisor.
√169 = 13. Portanto, 169 não é primo pois admite 13 como divisor.
(b) 197
Solução: 14 < √197 < 15. Devemos dividir 197 por todos os primos menores ou igual a 13.
Como 197 não divisível por 2, 3, 5, 7, 11, 13 e 17. Portanto, 197 é primo.
Solução: 14 < √197 < 15. Devemos dividir 197 por todos os primos menores ou igual a 13.
Como 197 não divisível por 2, 3, 5, 7, 11, 13 e 17. Portanto, 197 é primo.
(c) 239
Solução: 239, não é divisível por 2, 3, 5, 7, 11, 13 e 17 (172 = 289). 239 é primo.
Solução: 239, não é divisível por 2, 3, 5, 7, 11, 13 e 17 (172 = 289). 239 é primo.
(d) 473
Solução: 473 não é divisível por 2, 3, 5, 7. Mas é divisível por 11. Portanto, 473 não é primo.
Solução: 473 não é divisível por 2, 3, 5, 7. Mas é divisível por 11. Portanto, 473 não é primo.
09 – Achar a decomposição canônica do inteiro 5040.
Solução:
Solução:
5040
|
2
| |
2520
|
2
| |
1260
|
2
| |
630
|
2
| |
315
|
3
| |
105
|
3
| |
35
|
5
| |
7
|
7
| |
1
|
Resposta: 5040 = 24 x 32 x 5 x 7
|
10 – Achar o mdc(a, b) e mmc(a, b) sabendo a = 230 . 521 . 19 . 233 e b = 26 . 3 . 74 . 112 . 195. 237
Solução: O mdc(a,b) é o produto dos fatores comuns com seus menores expoentes.
Portanto, Mdc(a, b) = 26 . 19. 233. E o mmc(a, b) é o produto de todos os fatores com seus maiores expoentes. Portanto, mmc(a, b) = 230.3.521.74.112.195.237 Resposta: mdc(a, b) = 26 . 19. 233 e mmc(a, b) = 230.3.521.74.112.195.237.
Portanto, Mdc(a, b) = 26 . 19. 233. E o mmc(a, b) é o produto de todos os fatores com seus maiores expoentes. Portanto, mmc(a, b) = 230.3.521.74.112.195.237 Resposta: mdc(a, b) = 26 . 19. 233 e mmc(a, b) = 230.3.521.74.112.195.237.
11 – Mostrar que são primos gêmeos:
(a) 1949 e 1951
Solução: Primos gêmeos são dois primos que são ímpares consecutivos.
1ª condição: 1949 e 1951 são dois ímpares consecutivos.
2ª condição: Devemos verificar se ambos são primos.
452 > 1949 e 452 > 1951
Como ambos não são divisíveis por 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 e 43, os dois são primos.
Portanto são primos gêmeos.
1ª condição: 1949 e 1951 são dois ímpares consecutivos.
2ª condição: Devemos verificar se ambos são primos.
452 > 1949 e 452 > 1951
Como ambos não são divisíveis por 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 e 43, os dois são primos.
Portanto são primos gêmeos.
(b) 1997 e 1999
Solução:
1ª condição: são ímpares consecutivos.
2ª condição: Não são divisíveis por 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 e 43 .
Portanto, são primos gêmeos.
1ª condição: são ímpares consecutivos.
2ª condição: Não são divisíveis por 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 e 43 .
Portanto, são primos gêmeos.
13 – Achar uma sequência de quatro inteiros positivos consecutivos e compostos.
Solução: A forma mais fácil para encontrar sequências com os essa é usar o fatorial somado a inteiros sucessivos a partir de 2 pois no fatorial conterá esse fator.
Por exemplo em 10! Aparece o fator 4. Portanto, 10! + 4 é múltiplo de 4 pois 10! + 4 = (10!/4 + 1).4. Assim, para o que foi pedido podemos tomar 5! + 2, 5! + 3, 5! + 4, 5! + 5 ou qualquer outro fatorial somado a inteiros consecutivos.
Observe que em n! + a, a < n. Resposta: 5! + 2, 5! + 3, 5! + 4, 5! + 5.
Por exemplo em 10! Aparece o fator 4. Portanto, 10! + 4 é múltiplo de 4 pois 10! + 4 = (10!/4 + 1).4. Assim, para o que foi pedido podemos tomar 5! + 2, 5! + 3, 5! + 4, 5! + 5 ou qualquer outro fatorial somado a inteiros consecutivos.
Observe que em n! + a, a < n. Resposta: 5! + 2, 5! + 3, 5! + 4, 5! + 5.
14 – Achar um sequência de 100 inteiros positivos consecutivos e compostos.
Solução: Usando o mesmo reaciocínio anterior teríamos:
101! + 2, 101! + 3, 101! + 4 . . . 101! + 100, 101! + 101.
De 2 a 101 temos 100 números. Resposta:- 101! + 2, 101! + 3, 101! + 4 . . . 101! + 100, 101! + 101.
101! + 2, 101! + 3, 101! + 4 . . . 101! + 100, 101! + 101.
De 2 a 101 temos 100 números. Resposta:- 101! + 2, 101! + 3, 101! + 4 . . . 101! + 100, 101! + 101.
15 – Verificar a conjectura de Goldbach para os seguintes inteiros pares:
Solução: A conjectura de Goldbach diz que todo inteiro para maior que 4 pode ser expresso como uma soma de dois primos ímpares.
Solução: A conjectura de Goldbach diz que todo inteiro para maior que 4 pode ser expresso como uma soma de dois primos ímpares.
16 – Verificar que todo par entre 4 e 100 é a soma de dois primos:
Solução:
6 = 3 + 3
|
8 = 2 + 5
|
10 = 7 + 3
|
12 = 5 + 7
|
14 = 3 + 11
|
16 = 5 + 11
|
18 = 7 + 11
|
20 = 7 + 13
|
22 = 3 + 19
|
24 = 19 + 5
|
26 = 19 + 7
|
28 = 5 + 23
|
30 = 7 + 23
|
32 = 19 + 13
|
34 = 29 + 5
|
36 = 29 + 7
|
38 = 31 + 7
|
40 = 29 + 11
|
42 = 29 + 13
|
44 = 13 + 31
|
46 = 29 + 17
|
48 = 29 + 19
|
50 = 19 + 31
|
52 = 29 + 23
|
54 = 23 + 31
|
56 = 53 + 3
|
68 = 61 + 7
|
60 = 53 + 7
|
62 = 19 + 43
|
64 = 53 + 11
|
66 = 53 + 13
|
58 = 53 + 5
|
70 = 47 + 23
|
72 = 61 + 11
|
74 = 61 + 13
|
76 = 53 + 23
|
78 = 47 + 31
|
80 = 61 + 19
|
82 = 59 + 23
|
84 = 71 + 13
|
86 = 83 + 3
|
88 = 83 + 5
|
90 = 83 + 7
|
92 = 61 + 31
|
94 = 47 + 47
|
96 = 83 + 13
|
98 = 61 + 37
|
17 – Achar o menor inteiro positivo n tal que 2n2 + 29 é um inteiro composto.
Solução: pode-se garantir que para n = 29, 2n2 + 29 é um número composto pois: 2.292 + 29 = 29.(2.29 +1) = 29.59. Resta verificar se existe algum composto da forma 2n2+ 29 para n < 29.
A tabela abaixo mostra os valores de 2n2 + 29 para 1 < n < 29.
A tabela abaixo mostra os valores de 2n2 + 29 para 1 < n < 29.
- n1234567892n2+29313335373941434547n1011121314151617182n2+29495153555759616365n1920212223242526272n2+2975182991199710871181127913811487n28--------2n2+291597--------
Verificando, pelo processo das divisões por primos verifica-se que todos os valores de 2n2 + 1 são primos. Portanto, o menor valor de n para o qual 2n2 +29 é primo é n = 29.
18 – Mostar que a soma de inteiros positivos ímpares e consecutivos é sempre um inteiro composto.
Solução: Se os dois são ímpares consecutivos então eles têm as formas 2k + 1 e 2k + 3.
Assim, 2k + 1 + 2k + 3 = 4k + 4 = 4(k + 1). 4(k + 1), é múltiplo de 4.
Portanto, a soma é um inteiro composto. Cqd.
Portanto, a soma é um inteiro composto. Cqd.
19 – Usando a decomposição canônica dos inteiros 507 e 1287, achar o mdc(507, 1287) e o mm(507, 1287).
Solução: O mdc é igual ao produto dos fatores comuns com seus menores expoentes e o mmc é o produto de todos os fatores com seus maiores expoentes.
Na decomposição temos: 507 = 3.132 e 1287 = 32.11.13
Resposta: mdc(507, 1287) = 3.13 = 39 e mmc(507, 1289) = 32.11.132 = 16731
Na decomposição temos: 507 = 3.132 e 1287 = 32.11.13
Resposta: mdc(507, 1287) = 3.13 = 39 e mmc(507, 1289) = 32.11.132 = 16731
20 – Demonstrar que todo primo, exceto 2 e 3 é da forma 6k – 1 ou 6k + 1, onde k é um inteiro positivo.
Solução: De acordo com o algoritmo da divisão, todo número ao ser dividido por 6 é de uma das formas:
6k, 6k + 1, 6k + 2, 6k + 3, 6k + 4, 6k + 5.
Para n = 6k , n é múltiplo de 6. Não é primo.
Para n = 6k + 1, pode ser primo.
Para n = 6k + 2, n = 2(3k + 1) ⇒ n é múltiplo de 2. 6k + 2 não é primo.
Para n = 6k + 3, n = 3(2k + 1) ⇒ n é múltiplo de 3. 6k + 3 não é primo.
Para n = 6k + 4, n = 2(3k + 2) ⇒ n é múltiplo de 2. 6k + 4 não é primo.
Para n = 6k + 5, n = 6k + 6 – 1 = 6(k + 1) – 1 = 6k’ – 1. Pode ser primo.
Portanto, se n for primo ele não pode ser das formas 6k, 6k + 2, 6k + 3 e 6k + 4.
Assim, n é primo para 6k – 1 ou 6k + 1. Cqd.
6k, 6k + 1, 6k + 2, 6k + 3, 6k + 4, 6k + 5.
Para n = 6k , n é múltiplo de 6. Não é primo.
Para n = 6k + 1, pode ser primo.
Para n = 6k + 2, n = 2(3k + 1) ⇒ n é múltiplo de 2. 6k + 2 não é primo.
Para n = 6k + 3, n = 3(2k + 1) ⇒ n é múltiplo de 3. 6k + 3 não é primo.
Para n = 6k + 4, n = 2(3k + 2) ⇒ n é múltiplo de 2. 6k + 4 não é primo.
Para n = 6k + 5, n = 6k + 6 – 1 = 6(k + 1) – 1 = 6k’ – 1. Pode ser primo.
Portanto, se n for primo ele não pode ser das formas 6k, 6k + 2, 6k + 3 e 6k + 4.
Assim, n é primo para 6k – 1 ou 6k + 1. Cqd.
21 – Achar o menor inteiro positivo pelo qual se deve dividir 3720 para se obter um quadrado perfeito.
Solução: Todo quadrado perfeito tem seus fatores primos elevados a expoentes pares.
Decompondo 3720 temos: 3720 = 23 . 3. 5 . 31. Para que os expoentes dos fatores sejam números pares devemos eliminar um dois, o 3, o 5 e o 31. Portanto, 3720 deve ser dividido por 2.3.5.31 = 930.
Decompondo 3720 temos: 3720 = 23 . 3. 5 . 31. Para que os expoentes dos fatores sejam números pares devemos eliminar um dois, o 3, o 5 e o 31. Portanto, 3720 deve ser dividido por 2.3.5.31 = 930.
22 – Achar todos os primos que são divisores de 50!.
Solução: Todos os inteiros de 1 a 50 aparecem em 50!, pois 50! = 1.2.3.4.5....48.49.50!
Portanto, todos os primos inferiores a 50 são divisores do 50!.
Resposta:- 2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
Portanto, todos os primos inferiores a 50 são divisores do 50!.
Resposta:- 2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
23 – Mostrar que o único primo da forma n3 – 1 é 7.
Solução: Decompondo n3 – 1 temos: n3 – 1 = (n – 1)(n2 + n + 1).
Para que n3 – 1 seja primo e (n – 1)(n2 + n + 1) são seus fatores, (n – 1) deve ser igual a 1.
Assim, n – 1 = 1 ⇒ n = 2. Nesse caso, n2 + n + 1 = 22 + 2 + 1 = 7 e n3 – 1 = 23 – 1 = 8 – 1 = 7. Resposta: o único n3 – 1 primo é 7.
Para que n3 – 1 seja primo e (n – 1)(n2 + n + 1) são seus fatores, (n – 1) deve ser igual a 1.
Assim, n – 1 = 1 ⇒ n = 2. Nesse caso, n2 + n + 1 = 22 + 2 + 1 = 7 e n3 – 1 = 23 – 1 = 8 – 1 = 7. Resposta: o único n3 – 1 primo é 7.
24 – Mostrar que todo inteiro da forma n4 + 4, com n > 1 é composto.
Solução:
(1) Se n é par, temos n = 2k ⇒ (2k)4 + 4 = 16k4 + 4 = 4(4k4 + 1) ⇒ n4 + 4 é múltiplo de 4. Portanto, é composto.
(1) Se n é par, temos n = 2k ⇒ (2k)4 + 4 = 16k4 + 4 = 4(4k4 + 1) ⇒ n4 + 4 é múltiplo de 4. Portanto, é composto.
(2) Se n é ímpar, temos n = 2k + 1 ⇒ (2k + 1)4 + 4 = (2k)4 + 4(2k)3 + 6(2k)2 + 4(2k) + 1 + 5 = 16k4 + 32k3 + 24k2 + 8k + + 6 = 2(8k4 + 16k3 + 12k2 + 4k + 3) ⇒ n4 + 4 é múltiplo de 2. Portanto, é composto. Portanto n4 + 4 é composto, qualquer que seja n. Cqd.
Lucas Ribeiro, encontrou um erro nessa questão, pois, ao invés de usar n4 - 4 o autor do livro usou n4 - 5 na parte (2). Então, retificando temos a seguinte solução:
Observe que:
(n²+2)² - 4n² = n4 - 4
(n²+2-2n) (n²+2+2n) = n4 + 2n2 + 2n3 + 2n2 + 4 + 4n – 2n3 – 4n – 4n2 = n4- 4
Agora vamos à resposta enviada pelo Lucas,
(n²+2)² - 4n² => (n²+2-2n) (n²+2+2n) nesse ponto voce chegou a um produto de dois números, onde n>1 (dado) caracterizando um composto.
25 – Mostrar que se n > 4, é composto, então n divide (n – 1)!.
Solução: Se n é composto, n pode ser escrito na forma n = ab, com a > 1 e b > 1. Consideremos inicialmente b > a. Temos então: n = ab > a2 pois b > a . Mas a2 > 2a para a > 2.
Portanto, n > 2a ⇒ n – 1 > 2a – 1 = a + a – 1 > a + 1 – 1 = a. Conclui-se então que n – 1 > a.
Temos ainda que n = ab > 2b pois a > 2. Assim, n – 1 > b + b – 1 > b + 1 – 1 = b ⇒ n – 1 > b
Desta forma, a e b são dois inteiros diferentes, menores que n – 1. Portanto estão contidos em (n – 1)!. Desta forma, ab = n divide (n – 1)!.
Se a = b, teremos: n = ab = b2 > 2b pois a > b.
Em consequência n – 1 > 2b – 1 > b + b – 1 > b + 1 – 1 ⇒ n – 1 > b.
Portanto, o fator b está incluso em ( n – 1)!.
Provemos que, pelo menos um múltiplo de b, está também contido em (n – 1)!.
Ora, n = b2 e n > 4 implica que b > 2 ou b > 3. Portanto, n >3b ⇒ n - 1 > 3b – 1 = 2b + b – 1 > 2b + 1 – 1 ⇒ (n – 1) > 2b, de onde se conclui que 2b está incluído em (n – 1)!. Se b e 2b estão incluídos em (n – 1)!, 2b2 = 2n2 divide (n – 1)! ⇒ n divide (n – 1)!. Cqd.
Portanto, n > 2a ⇒ n – 1 > 2a – 1 = a + a – 1 > a + 1 – 1 = a. Conclui-se então que n – 1 > a.
Temos ainda que n = ab > 2b pois a > 2. Assim, n – 1 > b + b – 1 > b + 1 – 1 = b ⇒ n – 1 > b
Desta forma, a e b são dois inteiros diferentes, menores que n – 1. Portanto estão contidos em (n – 1)!. Desta forma, ab = n divide (n – 1)!.
Se a = b, teremos: n = ab = b2 > 2b pois a > b.
Em consequência n – 1 > 2b – 1 > b + b – 1 > b + 1 – 1 ⇒ n – 1 > b.
Portanto, o fator b está incluso em ( n – 1)!.
Provemos que, pelo menos um múltiplo de b, está também contido em (n – 1)!.
Ora, n = b2 e n > 4 implica que b > 2 ou b > 3. Portanto, n >3b ⇒ n - 1 > 3b – 1 = 2b + b – 1 > 2b + 1 – 1 ⇒ (n – 1) > 2b, de onde se conclui que 2b está incluído em (n – 1)!. Se b e 2b estão incluídos em (n – 1)!, 2b2 = 2n2 divide (n – 1)! ⇒ n divide (n – 1)!. Cqd.
26 – Mostrar que todo inteiro da forma 8n + 1, com n > 1, é composto.
Solução: Façamos 8n = (23)n = (2n)3 = a.
Assim, 8n + 1 = a3 + 1. Ora ( a3 + 1) = (a + 1)(a2 – a + 1).
Como 2n >2 conclui-se a > 1, de onde se tira a + 1 > 3 . Também, a2 > a ⇒ a2 – a + 1 > 1 e inteiro. Assim, 8n + 1 admite dois fatores maiores que 1. Portanto, 8n + 1 é composto. Cqd.
Assim, 8n + 1 = a3 + 1. Ora ( a3 + 1) = (a + 1)(a2 – a + 1).
Como 2n >2 conclui-se a > 1, de onde se tira a + 1 > 3 . Também, a2 > a ⇒ a2 – a + 1 > 1 e inteiro. Assim, 8n + 1 admite dois fatores maiores que 1. Portanto, 8n + 1 é composto. Cqd.
27 – Mostrar que se n2 + 2 é primo então 3 | n.
Solução: Todo número inteiro é da forma 3k, 3k + 1 e 3k + 2.
Se n é da forma 3k + 1, teremos: n2 + 2 = (3k + 1)2 + 2 = 3k2 + 6k + 1 + 2 = 3.(k2 + 2k + 1) ⇒ para números da forma (3k + 1), n2 + 2 é composto.
Se n é da forma 3k + 2, teremos: n2 + 2 = (3k + 2)2 + 2 = 9k2 + 12k + 4 + 2 = 3.(3k2 + 4k + 2) ⇒ para números da forma (3k + 2), n2 + 2 não é primo.
Assim, n2 + 2 só poderão ser primos se n for da forma 3k ⇒ 3 | n. Cqd.
Se n é da forma 3k + 1, teremos: n2 + 2 = (3k + 1)2 + 2 = 3k2 + 6k + 1 + 2 = 3.(k2 + 2k + 1) ⇒ para números da forma (3k + 1), n2 + 2 é composto.
Se n é da forma 3k + 2, teremos: n2 + 2 = (3k + 2)2 + 2 = 9k2 + 12k + 4 + 2 = 3.(3k2 + 4k + 2) ⇒ para números da forma (3k + 2), n2 + 2 não é primo.
Assim, n2 + 2 só poderão ser primos se n for da forma 3k ⇒ 3 | n. Cqd.
28 – Mostrar, mediante um exemplo, que a seguinte conjectura é falsa:
Todo inteiro positivo pode-se escrever sob a forma a2 + p, onde o inteiro a > 0 e p é um inteiro primo ou 1.
Todo inteiro positivo pode-se escrever sob a forma a2 + p, onde o inteiro a > 0 e p é um inteiro primo ou 1.
Solução: Após testar todos os inteiros de 1 até 25, verifica-se que 25 não tem a forma indicada pois; 25 = 1 + 24 ou 25 = 4 + 21 ou 25 = 9 + 16 ou 25 = 16 + 9. Observe que 24, 21, 16 e 9 não são primos e 1, 4, 9 e 16 são os únicos quadrados menores que 25.
29 – Demonstrar as seguintes propriedades:
(a) Todo primo da forma 3n + 1 é também da forma 6m + 1.
Solução: Se 3n + 1 é primo, 3n + 1 é impar. Assim, n e um número par. Portanto, para qualquer valor de m existe n tal que n + 2m.
Podemos então escrever 3(2m) + 1 = 6m + 1.
Solução: Se 3n + 1 é primo, 3n + 1 é impar. Assim, n e um número par. Portanto, para qualquer valor de m existe n tal que n + 2m.
Podemos então escrever 3(2m) + 1 = 6m + 1.
(b) Todo inteiro da forma 3n + 2 tem um fator primo desta forma.
Solução: Se 3n + 2 é primo, sua decomposição em fatores primos é 3n + 2 = (3n + 2).1 ⇒ 3n + 2 tem um fator primo da forma 3n + 2.
Se 3n + 2 não é primo, seja 3n + 2 = a1.a2.a3...an sua decomposição canônica em fatores primos. Como todo número inteiro tem uma das formas 3k, 3k + 1 ou 3k + 2, os fatores ai de 3n + 2 não podem ser da forma 3k pois 3k é múltiplo de 3, portanto não será primo.
Assim, cada ai somente poderá assumir uma das formas 3k + 2 ou 3k + 1.
Se todos forem da forma 3k + 1, teríamos:
(3k + 1)(3k’ + 1) = 9kk’ + 3k + 3k’ + 1 = 3.(3kk’ + k + k’) + 1 que é da forma 3n + 1. Portanto, 3n + 2 deve admitir pelo menos 1 fator da forma 3n + 2.
Solução: Se 3n + 2 é primo, sua decomposição em fatores primos é 3n + 2 = (3n + 2).1 ⇒ 3n + 2 tem um fator primo da forma 3n + 2.
Se 3n + 2 não é primo, seja 3n + 2 = a1.a2.a3...an sua decomposição canônica em fatores primos. Como todo número inteiro tem uma das formas 3k, 3k + 1 ou 3k + 2, os fatores ai de 3n + 2 não podem ser da forma 3k pois 3k é múltiplo de 3, portanto não será primo.
Assim, cada ai somente poderá assumir uma das formas 3k + 2 ou 3k + 1.
Se todos forem da forma 3k + 1, teríamos:
(3k + 1)(3k’ + 1) = 9kk’ + 3k + 3k’ + 1 = 3.(3kk’ + k + k’) + 1 que é da forma 3n + 1. Portanto, 3n + 2 deve admitir pelo menos 1 fator da forma 3n + 2.
(c) Se p > 5 é um primo, então p2 + 2 é composto.
Solução: Todo inteiro pode ser representado por uma das formas 3k , 3k + 1 ou 3k + 2.
Para p = 3k, p não é primo. Portanto, se p é primo e maior ou igual a 5, p é da forma 3k + 1 ou 3k + 2, com k > 1.
Se p = 3k + 1, temos p2 + 2 = (3k + 1)2 + 2 = 9k2 + 6k + 1 + 2 = 9k2 + 6k + 3 = 3.(9k2 + 6k + 1) é múltiplo de 3, maior que 3 pois k > 1.
Se p = 3k + 2 , temos p2 + 2 = (3k + 2)2 + 2 = 9k2 + 12k + 4 + 2 = 9k2 + 12k + 6 = 3.(3k2 + 4k + 2) é múltiplo de 3, maior que 3, pois k > 1.
Assim, qualquer que seja p > 5, p primo, p2 + 2 é composto. Cqd
Solução: Todo inteiro pode ser representado por uma das formas 3k , 3k + 1 ou 3k + 2.
Para p = 3k, p não é primo. Portanto, se p é primo e maior ou igual a 5, p é da forma 3k + 1 ou 3k + 2, com k > 1.
Se p = 3k + 1, temos p2 + 2 = (3k + 1)2 + 2 = 9k2 + 6k + 1 + 2 = 9k2 + 6k + 3 = 3.(9k2 + 6k + 1) é múltiplo de 3, maior que 3 pois k > 1.
Se p = 3k + 2 , temos p2 + 2 = (3k + 2)2 + 2 = 9k2 + 12k + 4 + 2 = 9k2 + 12k + 6 = 3.(3k2 + 4k + 2) é múltiplo de 3, maior que 3, pois k > 1.
Assim, qualquer que seja p > 5, p primo, p2 + 2 é composto. Cqd
(d) Se p é um primo e se p | an , então pn | an.
Solução: Seja a = a1.a2.a3...an a decomposição canônica de a em fatores primos. Assim teremos: an = a1n.a2n.a3n...ann . Todos os fatores primos de an são da forma ain.
Se p | an , então em p é um fator primo de an , o que permite, conforme indicado acima, que pn é fator de an. Portanto, pn | an. Cqd
Solução: Seja a = a1.a2.a3...an a decomposição canônica de a em fatores primos. Assim teremos: an = a1n.a2n.a3n...ann . Todos os fatores primos de an são da forma ain.
Se p | an , então em p é um fator primo de an , o que permite, conforme indicado acima, que pn é fator de an. Portanto, pn | an. Cqd
(e) Todo inteiro n > 11 pode ser expresso como a soma de dois inteiros compostos.
Solução: Se n é par, temos, n = 2k , com k maior que 5. Assim, n = 2k = 2.(k – 2) + 4 onde 2.(k – 2) é um composto maior que 2 pois de k > 5 conclui-se que k – 2 > 3 e 2.(k – 2) é um par maior que 6 e 4 é um composto.
Se n é ímpar, temos n = 2k + 1 com k > 5. Assim, n = 2k + 1 = 2.(k – 4) + 1 + 8 = 2.(k – 4) + 9. Como k > 5, k – 4 > 1 ⇒ 2(k – 4) é um par maior que 4 e 9 é um múltiplo de 3.
Assim, para n > 11, n pode ser expresso como 2(k – 2) + 4 se n for para e 2(k – 4) + 9 se n for ímpar.
Solução: Se n é par, temos, n = 2k , com k maior que 5. Assim, n = 2k = 2.(k – 2) + 4 onde 2.(k – 2) é um composto maior que 2 pois de k > 5 conclui-se que k – 2 > 3 e 2.(k – 2) é um par maior que 6 e 4 é um composto.
Se n é ímpar, temos n = 2k + 1 com k > 5. Assim, n = 2k + 1 = 2.(k – 4) + 1 + 8 = 2.(k – 4) + 9. Como k > 5, k – 4 > 1 ⇒ 2(k – 4) é um par maior que 4 e 9 é um múltiplo de 3.
Assim, para n > 11, n pode ser expresso como 2(k – 2) + 4 se n for para e 2(k – 4) + 9 se n for ímpar.
(f) Se p > q > 5 e se p e q são ambos primos, então 24 | p2 – q2.
Solução: Para p = q, a propriedade é evidente, pois p = q ⇒ p2 – q2 = 0 e 24 | 0.
Devemos provar que p2 – q2 é múltiplo de 3 e múltiplo de 8.
Para p > q, façamos p2 – q2 = (p + q)(p – q). Assim, se p + q ou p – q, for múltiplo de 3 p2 – q2 será múltiplo de 3. O mesmo ocorrendo com 8 e p2 – q2.
Provemos inicialmente que p2 – q2 é múltiplo de 3.
Se p e que são primos, então p = 3k + 1 ou 3k + 2 e q = 3k’ + 1 ou 3k’ + 2.
Para p = 3k + 1 e q = 3k’ + 1 teremos p – q = (3k + 1) – (3k’ + 1) = 3k – 3k’ = 3.(k – k’) ⇒ (p – q) é múltiplo de 3.
Para p = 3k + 2 e q = 3k’ + 2 teremos p – q = (3k + 2) – (3k’ + 2) = 3k – 3k’ = 3.(k – k’) ⇒ (p – q) é múltiplo de 3.
Para p = 3k + 1 e q = 3k’ + 2 teremos p + q = (3k + 1) + (3k’ + 2) = 3.(k + k’ + 1) ⇒ (p + q) é múltiplo de 3.
Para p = 3k + 2 e q = 3k’ + 1 teremos p + q = (3k + 2) + (3k’ + 1) = 3.(k + k’ + 1) ⇒ (p + q) é múltiplo de 3.
Portanto, p2 – q2 é múltiplo de 3, em todas as situações possíveis.
Provemos agora que p2 – q2 é múltiplo de 8.
Sendo p e q primos maiores ou iguais a 5, então p = 4k + 1 ou 4k + 3 e q = 4k’ + 1 ou 4k’ + 3, com k e k maior ou igual a 1. Note que 4k e 4k + 2 não são primos pois são múltiplos de 2.
Solução: Para p = q, a propriedade é evidente, pois p = q ⇒ p2 – q2 = 0 e 24 | 0.
Devemos provar que p2 – q2 é múltiplo de 3 e múltiplo de 8.
Para p > q, façamos p2 – q2 = (p + q)(p – q). Assim, se p + q ou p – q, for múltiplo de 3 p2 – q2 será múltiplo de 3. O mesmo ocorrendo com 8 e p2 – q2.
Provemos inicialmente que p2 – q2 é múltiplo de 3.
Se p e que são primos, então p = 3k + 1 ou 3k + 2 e q = 3k’ + 1 ou 3k’ + 2.
Para p = 3k + 1 e q = 3k’ + 1 teremos p – q = (3k + 1) – (3k’ + 1) = 3k – 3k’ = 3.(k – k’) ⇒ (p – q) é múltiplo de 3.
Para p = 3k + 2 e q = 3k’ + 2 teremos p – q = (3k + 2) – (3k’ + 2) = 3k – 3k’ = 3.(k – k’) ⇒ (p – q) é múltiplo de 3.
Para p = 3k + 1 e q = 3k’ + 2 teremos p + q = (3k + 1) + (3k’ + 2) = 3.(k + k’ + 1) ⇒ (p + q) é múltiplo de 3.
Para p = 3k + 2 e q = 3k’ + 1 teremos p + q = (3k + 2) + (3k’ + 1) = 3.(k + k’ + 1) ⇒ (p + q) é múltiplo de 3.
Portanto, p2 – q2 é múltiplo de 3, em todas as situações possíveis.
Provemos agora que p2 – q2 é múltiplo de 8.
Sendo p e q primos maiores ou iguais a 5, então p = 4k + 1 ou 4k + 3 e q = 4k’ + 1 ou 4k’ + 3, com k e k maior ou igual a 1. Note que 4k e 4k + 2 não são primos pois são múltiplos de 2.
Portanto, quaisquer que sejam as formas de p e q primos, (p + q)(p – q) = p2 – q2 é múltiplo de 8
Como p2 – q2 é múltiplo de 3 e múltiplo de 8, sendo mdc(3, 8) = 1, p2 – q2 é múltiplo de 24, ou 24 | p2 – q2.
Como p2 – q2 é múltiplo de 3 e múltiplo de 8, sendo mdc(3, 8) = 1, p2 – q2 é múltiplo de 24, ou 24 | p2 – q2.
(g) Se p ≠ 5 é um primo ímpar, então p2 – 1 ou p2 + 1 é divisível por 10.
Solução: Seja p um primo diferente de 5. Sendo p ≠ 5, um inteiro primo, então, p pode ter uma das formas: p = 10k + 1, 10k + 3, 10k + 7, 10k + 9.
Note que para p = 10k, 10k + 2, 10k + 4, 10k + 6 e 10k + 8 p é um número par, portanto não primo ímpar) e p = 10k + 5 é um múltiplo de 5.
No caso de k = 0 teremos p = 5, o que não serve. Assim, confirmamos que p = 10k + 1, 10k + 3, 10k + 7 ou 10k + 9. A tabela abaixo mostra os quadrados dessas formas:
Solução: Seja p um primo diferente de 5. Sendo p ≠ 5, um inteiro primo, então, p pode ter uma das formas: p = 10k + 1, 10k + 3, 10k + 7, 10k + 9.
Note que para p = 10k, 10k + 2, 10k + 4, 10k + 6 e 10k + 8 p é um número par, portanto não primo ímpar) e p = 10k + 5 é um múltiplo de 5.
No caso de k = 0 teremos p = 5, o que não serve. Assim, confirmamos que p = 10k + 1, 10k + 3, 10k + 7 ou 10k + 9. A tabela abaixo mostra os quadrados dessas formas:
Observando a tabela, sempre uma das formas p2 + 1 ou p2 – 1 é um múltiplo de 10. Cqd.
30 – Verificar que todo inteiro pode escrever-se sob a forma 2km, onde o inteiro k > 0 e m é um inteiro ímpar.
Solução: Se n é um inteiro ímpar, faz-se m = n e n = 20.m.
Se n é um inteiro para, na sua decomposição canônica temos, n = 2k.a1k1.a2k2.a3k3....ankn . Somente o fator 2 é um primo par. Assim, o produto de todos os fatores, exceto 2, é um número ímpar. Portanto, conclui-se: n = 2k.m. Cqd.
Se n é um inteiro para, na sua decomposição canônica temos, n = 2k.a1k1.a2k2.a3k3....ankn . Somente o fator 2 é um primo par. Assim, o produto de todos os fatores, exceto 2, é um número ímpar. Portanto, conclui-se: n = 2k.m. Cqd.
31 – Demonstrar que o inteiro positivo a > 1 é um quadrado perfeito se e somente se todos os expoentes dos fatores primos da sua decomposição canônica são inteiros pares.
Solução: Seja a um quadrado perfeito então a tem a forma n2. Se n = n1k1.n2k2.n3k3. ... nnkn, onde n1k1.n2k2.n3k3. ... nnkn é a decomposição canônica em fatores primos de n, teremos n2 = (n1k1.n2k2.n3k3. ... nnkn)2 = n12k1.n22k2.n32k3. ... nn2kn . Como todos os expoentes são da forma 2k, conclui-se que todos os expoentes são pares.
Seja então ni um fator primo de n cujo expoente não seja par. Neste caso, o fator teria expoente da forma 2k + 1. Ora, ni2k + 1 = ni2k . ni. ni2k tem expoente para, portanto está de acordo com o que foi dito anteriormente. Para que fosse quadrado, ni deveria ter dois fatores primos iguais. Como ni é primo isto não é possível. Portanto, todo número é quadrado perfeito, se e somente se, todos os. expoentes dos fatores primos na decomposição canônica for par. Cqd.
Seja então ni um fator primo de n cujo expoente não seja par. Neste caso, o fator teria expoente da forma 2k + 1. Ora, ni2k + 1 = ni2k . ni. ni2k tem expoente para, portanto está de acordo com o que foi dito anteriormente. Para que fosse quadrado, ni deveria ter dois fatores primos iguais. Como ni é primo isto não é possível. Portanto, todo número é quadrado perfeito, se e somente se, todos os. expoentes dos fatores primos na decomposição canônica for par. Cqd.
32 – Demonstrar que, se o inteiro n é composto, então 2n – 1 também é composto.
Solução: Evidentemente se trata de n positivo, pois se n < 0 , n – 1 é negativo e 2n – 1 não será um inteiro. Assim, para n > 0 e n composto, n > 3. Teremos então n – 1 > 2 ⇒ 2n – 1 = 2k, k = n – 1 > 2 inteiro ⇒ k – 2 > 0 ⇒ (k – 1) > 0. Ora, 2n – 1 = 2k = 2.(2k – 1) que é múltiplo de 2 (não se esqueça que k – 1 > 0) ⇒ 2n – 1 é composto.
33 – Demonstrar que, se o inteiro n > 2, então existe um primo p tal que n < p < n!.
Solução: Temos 2.(n – 1) = n + n – 2 > n + 2 – 2 > n . Portanto, 2.(n – 1) > n (1).
Como n!/[2(n – 1)] = n(n –2)(n – 3).....3 resulta também que n! > 2.(n – 1) (2).
De (1) e (2) concluímos que n! > 2.(n – 1) > n. Ora, para todo n > 3, entre n e 2(n – 1) existe pelo menos um primo, de acordo com a proposição de Tschebischeff, concluímos que entre n e n! existe um primo p. Para n = 2, temos 2! = 4. Temos o 3 que é primo. Portanto, para n > 2, existe p primo, tal que n < p < n!. Cqd.
Como n!/[2(n – 1)] = n(n –2)(n – 3).....3 resulta também que n! > 2.(n – 1) (2).
De (1) e (2) concluímos que n! > 2.(n – 1) > n. Ora, para todo n > 3, entre n e 2(n – 1) existe pelo menos um primo, de acordo com a proposição de Tschebischeff, concluímos que entre n e n! existe um primo p. Para n = 2, temos 2! = 4. Temos o 3 que é primo. Portanto, para n > 2, existe p primo, tal que n < p < n!. Cqd.
34 – Demonstrar que todo primo ímpar é da forma 4k + 1 ou 4k – 1, onde k é um inteiro positivo.
Solução: Qualquer que seja n inteiro, n = 4k, 4k + 1, 4k + 2 ou 4k + 3.
Se n é primo ímpar, n não pode assumir uma das formas 4k e 4k + 2 pois estas são formas de pares. Assim, n só pode ser 4k + 1 ou 4k + 4. Para n = 4k + 3, temos n = 4k +3 + 1 – 1 = 4(k + 1) – 1 que é da forma 4k – 1. Cqd.
Se n é primo ímpar, n não pode assumir uma das formas 4k e 4k + 2 pois estas são formas de pares. Assim, n só pode ser 4k + 1 ou 4k + 4. Para n = 4k + 3, temos n = 4k +3 + 1 – 1 = 4(k + 1) – 1 que é da forma 4k – 1. Cqd.
