Lista 3 - Teoria dos Números

Prévia do material em texto

Disciplina: Teoria dos Números
Professor: Vinícius Oliveira
Lista 3 � Algoritmo de Euclides. Mínimo Multiplo Comum.
1. Usando o algoritmo de Euclides, determinar:
(a) mdc(272, 1479)
Solução:
1479 = 272 · 5 + 119
272 = 119 · 2 + 34
119 = 34 · 3 + 17
34 = 17 · 2
Portanto,
mdc(272, 1479) = 17
(b) mdc(884, 1292)
Solução:
1292 = 884 · 1 + 418
884 = 418 · 2 + 48
418 = 48 · 8 + 34
48 = 34 · 1 + 14
34 = 14 · 2 + 6
14 = 6 · 2 + 2
6 = 2 · 3
Portanto,
mdc(272, 1479) = 2
(c) mdc(7469, 2387)
Solução:
7469 = 2347 · 3 + 308
2347 = 308 · 7 + 231
1
308 = 231 · 1 + 77
231 = 77 · 3
Portanto,
mdc(7469, 2387) = 77
2. Usando o algoritmo de Euclides, encontre os inteiros x e y que veri�quem cada uma das
seguintes igualdades.
(a) mdc(24, 138) = 24x+ 138y
Solução:
Como
mdc(24, 138) = 6
24x+ 138y = 6
138 = 24 · 5 + 18
24 = 18 · 1 + 6
18 = 6 · 3
Temos,
6 = 24− 18 · 1
24− (138− 24 · 5) · 1
24 · 6 + 138 · (−1)
Portanto,
x = 6 e y = −1
.
3. Achar os inteiros x e y que veri�quem cada uma das seguintes equações.
(a) 78x+ 32y = 2
Solução:
78 = 32 · 2 + 14
32 = 14 · 2 + 4
14 = 4 · 3 + 2
4 = 2 · 2
2
Fazendo a volta, temos
2 = 14− 4 · 3
2 = 14− (32− 14 · 2) · 3
2 = 14 · 7 + 32 · (−3)
2 = (78− 32 · 2) · 7 + 32 · (−3)
2 = 78 · 7 + 32 · (−17)
Logo,
x = 7 e y = −17
(b) 11x+ 19y + 3z = 1
Solução:
Temos,
11x+ 19y = 1− 3z
Note que 1− 3z tem que ser múltiplo do mdc(11, 19)
Vamos determinar o mdc(11, 19):
19 = 11 · 1 + 8
11 = 8 · 1 + 3
8 = 3 · 2 + 2
3 = 2 · 1 + 1
2 = 1 · 2
Como o mdc(11, 19) = 1, para quaisquer valores atribuidos a z, a expressão 1 − 3z
será múltiplo de 1
Tomando z = 1 tem-se
11x+ 19y = −2
Temos,
1 = 3− 2 · 1
1 = 3 + (8− 3 · 3) · (−1)
1 = 3 · 3 + 8 · (−1)
1 = (11− 8 · 1) · 3 + 8 · (−1)
3
1 = 11 · 3 + 8 · (−4)
1 = 11 · 3 + (19− 11 · 1) · (−4)
1 = 11 · 7 + 19 · (−4) × (−2)
−2 = 11 · (−14) + 19 · 8
Portanto, para z = 1 temos x = −14 e y = 8 n
4. demonstrar que se a e b são inteiros positivos tais que o mdc(a, b) = mmc(a, b), então
a = b.
Solução:
Seja mdc(a, b) = d, por de�nição d|a e d|b
e
Seja mmc(a, b) = d, por de�nição a|d e b|d
Assim, d|a e a|d então a = d, e se d|b e b|d, logo b = d
Portanto a = b = d
5. Sendo a e b inteiros positivos, demonstrar que o mdc(a, b) sempre divide o mmc(a, b).
Solução:
Seja mdc(a, b) = d 3 x, y; a = dx e b = dy
a · b = dx · dy
a · b = mdc(a, b) ·mmc(a, b) · xy
mdc(a, b) ·mmc(a, b) = mdc(a, b) ·mdc(a, b) · xy
Por de�nição:
mdc(a, b)|mmc(a, b)
6. Achar os cinco menores primos da forma n2 − 2.
Solução:
Note que qualquer valor par para n, n2 também será par, pois se n for par então n2
também será par, e inteiros pares não são primos, com excessão do 2.
Desse modo, veri�caremos os primos n ≥ 2
n = 2 =⇒ 22 − 2 = 2 é primo
n = 3 =⇒ 32 − 2 = 7 é primo
n = 5 =⇒ 52 − 2 = 23 é primo
4
n = 7 =⇒ 72 − 2 = 47 é primo
Logo, os cinco menores primos na forma n2 − 2 são 2, 7, 23, 47
7. Achar todos os pares de primos p e q, tais que p− q = 3.
Solução:
Observe que se p e q são primos, então p− q é ímpar
Desse modo p e q possuem paridades diferentes e o único primo par é 2, temos q = 2,
p− 2 = 3 =⇒ p = 5
Portanto o único par de primos, isto é, a única solução é p = 5 e q = 2.
8. Achar todos os primos que são iguais a um cubo perfeito menos 1.
Solução:
Temos n3 − 1 = (n− 1) · (n2 + n+ 1), onde (n− 1) e (n2 + n+ 1) são dois inteiros
Para que n3 − 1 seja múltiplo de dois inteiros e seja primo, um dos dois inteiros só pode
ser 1
Como (n2 + n+ 1) > n− 1, então n− 1 = 1 =⇒ n = 2
Assim,
n3 − 1 = 23 − 1 = 7
Portanto 7 é o único primo que pode ser da forma n3 − 1
9. Mostre que são primos gêmeos:
(a) 1949 e 1951
Solução:
Primos gêmeos são dois primos que são ímpares consecutivos
1a condição: 1949 e 1951 são dois ímpares consecutivos
2a condição: Devemos veri�car se ambos são primos
452 > 1949 > 442 e 452 > 1951 > 442
Como ambos não são divisíveis por
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 e 43
Logo, os dois são primos
Portanto são primos gêmeos
(b) 1997 e 1999
Solução:
5
1a condição: são ímpares consecutivos
2a 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
10. Achar uma sequência de quatro inteiros positivos consecutivos e compostos.
Solução:
A forma mais fácil para encontrar sequências como 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
Logo 5! + 2, 5! + 3, 5! + 4, 5! + 5
11. Achar uma sequência de 100 inteiros positivos consecutivos e compostos.
Solução:
Usando o mesmo raciocínio anterior temos
101! + 2, 101! + 3, 101! + 4, ..., 101! + 100, 101! + 101
De 2 a 101 temos 100 números
Portanto, 101! + 2, 101! + 3, 101! + 4, ..., 101! + 100, 101! + 101
12. Mostrar que a soma de dois inteiros í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. n
13. 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
6
Para n = 6k, n é múltiplo de 6, não é primo
Para n = 6k + 1, pode ser primo
Para n = 6k + 2, 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, 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, 6k + 4
Assim, n é primo para
6k + 1 e 6k − 1
14. 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
n3 − 1 = 23 − 1 = 7
e
n2 + n+ 1 = 22 + 2 + 1 = 7
Portanto, o único n3 − 1 primo é 7
15. Mostrar que, se n2 + 2 é primo, então 3|n.
Solução:
Todo número inteiro é da forma 3k, 3k + 1 e 3k + 2
Para n = 3k temos
(3k)2 + 2 = 9k2 + 2 = 3(3k2) + 2 = 3k′ + 2
Se n é da forma 3k + 1, teremos
n2 + 2 = (3k + 1)2 + 2 = 9k2 + 6k + 1 + 2 = 3 · (3k2 + 2k + 1)
7
Para números da forma 3k + 1, n2 + 2 é composto
Com n = 3k + 2
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
Portanto, n2 + 2 só poderá ser primo se n = 3k e de fato 3|3k
8