A maior rede de estudos do Brasil

Grátis
132 pág.
Problemas em Teoria dos Números (Resolvidos e Propostos) do prof Diego Marques

Pré-visualização | Página 5 de 23

Escrevendo n = 2k + 1 em= 2t + 1, temos, 
o que claramente é um múltiplo de 8. 
OBS.: Usamos que (a+ 1)4 = a4 + 4a3 + 6a2 + 4a + 1. 
40. Encontrar o menor inteiro positivo da forma 36x + 54y onde x e y são inteiros. 
o 
o 
Solução: Usaremos a observação do Teorema 1.3, que diz que o menor inteiro positivo da forma 
ax + by, com x, y E Z, é exatamente (a, b), ou seja, (a, b) = min (N n {ma+ nb I m, n E Z} ). Daí 
basta calcular (36, 54). Portanto (36, 54) = (22 • 32 ,2 · 33) = 2 · 32 = 18. O 
41. Utilizando o processo descrito no Teorema 1.17 expressar o número 274 nas bases 2,5,7 e 9. 
Capítulo 1. Problemas resolvidos 19 
Solução: Na demonstração do Teorema 1.17, vimos que se 
n = bqo + ao, O ~ ao < b 
qo = bq1 + a1, O ~ a1 < b 
Ql = bq2 + a2, O ~ a2 < b 
então n = (akak-l ... a1ao)b. Daí 274 pode ser expresso na, 
(i) Base 2, 
então 274 = (100010010)2. 
(ii) Base 5, 
então 274 = (2044)s. 
(iii)Base 7, 
então 274 = (541)7. 
(iv) Base 9, 
então 274 = (334)g. 
.· .. ·274 = 2. 137 +o, 
137 = 2 . 68 + 1, 
. 68 = 2 . 34 + o, 
34 = 2. 17 +o, 
17 = 2. 8 + 1, 
8 = 2. 4 +o, 
4 = 2. 2 +o, 
2 = 2 ·1 +o, 
1 = 2. o+ 1, 
274 = 5. 54+ 4, 
54= 5 ·10 + 4, 
10 = 5. 2 +o, 
2 = 5. o+ 2, 
{
274 = 7. 39 + 1, 
39 = 7. 5 + 4, 
5 = 7. o+ 5, 
{ 
27 4 = 9 . 30 + 4, 
30 = 9. 3 + 3, 
3 = 9. o+ 3, 
o 
20 Problemas em Teoria dos Números (Resolvidos e Propostos) 
42. Transformar para a base 10 os seguintes números 
(a) (2351)7 
(b) (1001110)2 
(c) (7706)s 
(d) (11122)4 
Solução: 
(a) (2351)7 = 1 · 'fl + 5 · 71 + 3 · 72 + 2 · 73 = 1 + 35 + 147 + 686 = 869. 
(b) (1001110)2 =o. 2° + 1. 21 + 1. 22 + 1. 23 +o. 24 +o. 25 + 1. 26 = 2 + 4 + 8 + 64 = 78. 
(c) (7706)s = 6 · 8° +O· 81 + 7 · 82 + 7 · 83 = 6 + 448 + 3584 = 4038, 
(d) (11122)4 = 2. 4° + 2. 41 + 1. 42 + 1. 43 + 1. 44 = 2 + 8 + 16 + 64 + 256 = 346. 
43. Mostrar que se 2n + 1 é um primo ímpar, então n é uma potência de 2. 
o 
Solução: Suponha que n não é potência de 2, isto é, n = 2am, com m > 1 ímpar e a~ O. Usando 
que se t é ímpar, então 
at + 1 =(a+ 1)(at-1 - at-2 + · · · + 1), 
obtemos, 2n + 1 = (22a)m + 1 = (22a + 1)(22a(m-1) - 22a(m-2) + · · · + 1), que é um número 
composto. O 
44. Provar que se d = (a, b), então d é o número de inteiros na sequência a, 2a, 3a, ... , ba que são 
divisíveis por b. 
Solução: (i) Solução 1. Suponha que ja é divisível por b, para algum 1 ~ j ~ b. Então b I ja e 
a I ja, portanto [a, b]l ja (isso porque ja seria um múltiplo comum de a e b). Daí ja = k[a, b], 
para algum k E Z. Para saber a quantidade de possíveis j, é suficiente encontrar a quantidade 
de possíveis k. Como ja ~ ab, então k é o maior inteiro tal que 
ab 
k[a, b] ~ ab ==? k ~ [a, b] =(a, b), 
onde usamos o Teorema 1.16. Logo, existem (a, b) possíveis k o que implica na existência de 
(a, b) possíveis j E {1, ... , b} tais que b I ja. 
(i i) Solução 2. O número de múltiplos de b no conjunto {a, 2a, ... , ba} é o mesmo número de 
múltiplos de ~ no conjunto {a, 2a, ... , ba}· Como (a,~) = 1, então é o número de múltiplos de 
~ no conjunto {1, 2, ... , b} que é igual a l l J = d, onde usamos o seguinte fato: 
O número de múltiplos de k no conjunto { 1, ... , n} é lI J . 
D 
Capítulo 1. Problemas resolvidos 21 
1. 2 Congruência 
Problemas resolvidos do Capítulo 2 
1. Mostrar que 47 J (223 - 1) 
Solução: Temos que 26 = 64 = 17 (mod 47). Elevando ao cubo, obtemos 
Finalmente, multiplicando por 25 obtemos, 
223 = 25 · 32 = 800 = 1 (mod 47). 
Portanto 47J 223 - 1. O 
2. Encontrar o resto da divisão de 734 por 51 e o resto da,-divisão de 563 por 29. 
Solução: Para resolver este problema usaremos o Teorema 2.3, que diz: 
Se ac = bc (mod m) e (c, m) = 1, então a- b (mod m). 
(i) Note que 72 = -2 (mod 51) e daí 734 = (72 ) 17 = ( -2)17 = -217 (mod 51). Por outro 
lado, 26 = 13 (mod 51) e então 212 = (26 ) 2 = 132 = 169 = 16 = 24 (mod 51). Aplicando o 
Teorema citado com a= 28 , b = 1, c= 24 em= 51, obtemos a congruência 28 = 1 (mod 51) 
e logo -217 = -2·(28) 2 = -2 (mod 51). Assim, 734 = -2 = 49 (mod 51). Portanto, o resto é 49. 
(ii) Como 29 é primo, então pelo Pequeno Teorema de Fermat, temos que 528 = 1 (mod 29) e, 
portanto, 
563 = 52-28+7 = (528)2. 57= 57 (mod 29). 
Mas 52 = -4 (mod 29) e daí, 
57 = 52·3+1 = (52) 3 • 5 = ( -4)3 • 5 = 23 · 5 = 28 (mod 29). 
Portanto, temos que 563 = 28 (mod 29) e o resto em questão é 28. o 
3. Mostrar que se pé um ímpar e a2 + 2b2 = 2p, então a é par e b é ímpar. 
Solução: Note que a é par, pois a2 = 2(p- b2). Suponha, por absurdo, que b é par. Então a= 2k 
e b = 2t. Daí 
2p = a 2 + 2b2 = 4k2 + 8t2 
e logo p = 4(k2 + 2t2) é par, contradizendo o fato de p ser ímpar. o 
4. Provar que para p primo (p- 1)! = p- 1 (mod 1 + 2 + 3 + · · · + (p- 1)). 
Solução: Queremos mostrar que (p-1)! ::=p-1 (mod 1+2+· · ·+(p-1)), ou seja, (p-1)! =p-1 
22 Problemas em Teoria dos Números (Resolvidos e Propostos) 
(mod (p-;)·P). Se p = 2, então 1! = 1 (mod 1). Se p > 2, então P21 é inteiro e assim basta-nos 
mostrar que (p- 1)! = p- 1 (mod p) e (p- 1)! = p- 1 (mod P21 ) pois (p, P21 ) = 1. 
Pelo Teorema de Wilson, temos (p- 1)! = -1 = p- 1 (mod p). Como P21 I (p- 1), então 
P21 I (p -1)!- (p- 1) e, portanto, (p -1)! = p -1 (mod P21 ) o que conclui a demonstração. O 
5. Encontrar o máximo divisor comum de (p- 1)!- 1 e p! (p primo). 
Solução: Suponha que d = ((p- 1)!- 1,p!), então dI ((p- 1)!- 1) e dI p!. Daí 
d I p( (p - 1)! - 1) - p! = -p e, portanto, d = 1 ou d = p. Mas pelo Teorema de Wilson, 
(p- 1)! = -1 (mod p). Assim, se d = p teríamos 1 = -1 (mod p) ::::} p = 2 logo se p = 2, 
((p- 1)!- 1,p!) = 2. Se p > 2, então 1 = d = ((p- 1)!- 1,p!). O 
6. Mostrar que para n ~ 4 o resto da divisão por 12 de 1! + 2! + 3! + · · · + n! é 9. 
Solução: Se n > 4, então n! =O (mod 12). Daí 1! + 2! + · · · + n! = 1! + 2! + 3! = 1 + 2 + 6 = 9 
(mod 12). O 
7. Mostrar que para n inteiro 3n2 - 1 nunca é um quadrado. 
Solução: Para solucionar esse problema usaremos o seguinte fato: 
Se x E .Z, então x 2 =O (mod 3) ou x 2 = 1 (mod 3). 
Na verdade, sabemos que dado x E .Z temos que x = 3.k + j com j E {0, 1, 2}. Assim, x 2 = 
(3k + j) 2 = 3(3k2 + 2kj) + j 2 . Mas 02 = O (mod 3), 12 = 1 (mod 3) e 22 = 4 = 1 (mod 3). 
Suponha, por absurdo, que 3n2 - 1 = m 2 . Claramente 3 não divide m (caso contrário 3 dividiria 
1). Logo m2 = 1 (mod 3) e, portanto, 1 = m 2 = 3n2 - 1 =O- 1 = -1 (mod 3) ::::} 3 I 2 o que é 
um absurdo. O 
8. Resolver as seguintes congruências. 
(a) 5x = 3 (mod 24) 
(b) 3x = 1 (mod 10) 
(c) 23x = 7 (mod 19) 
(d) 7x = 5 (mod 18) 
(e) 25x = 15 (mod 120) 
Solução: 
(a) x = 5 ( 5x) · 5 · 3 = 15 ( mod 24) 
(b) x = 7(3x) = 7 · 1 = 7 (mod 10) 
(c) Como 23x = 4x (mod 19), então queremos resolver 4x = 7 (mod 19). Daí x = 5(4x) = 
5 · 7 = 35 = 16 (mod 19). 
(d) -x = 5(7x) = 5 · 5 = 25 (mod 18) e daí x = -25 = 11 (mod 18) 
Capítulo 1. Problemas resolvidos 23 
(e) 5(5x) = 5 · 3 (mod 120), então pelo Teorema 2.3 implica que 5x = 3 (mod 24) e daí x = 
5(5x) = 5 · 3 = 15 (mod 24). 
o 
9. Mostrar que 5n3 + 7n5 = O (mod 12) para todo inteiro n. 
Solução: Temos que 5n3 + 7n5 = n 3 (5 + 7n2). Logo basta-nos mostrar que 3 I n 3 (5 + 7n2) e 
41 n 3 (5 + 7n2). Para isso usaremos que 
(i) se 3 não divide x, então x2 = 1 (mod 3); 
(ii) se 2 não divide x, então x2 = 1 (mod 4). 
Note que, se 3 I n, então 3 I n 3 (5 + 7n2) e se 3 não divide n, então n 2 = 1 (mod 3). Portanto, 
5 + 7n2 = 5 + 7 · 1 = 12 =O (mod 3). Se 2 I n, então 4 I n3 e, logo, 4 I n 3 (5 + 7n2). Por outro 
lado, se 2 não divide n, então n 2 = 1 (mod 4) e, portanto, 5 + 7n2 = 5 + 7 ·1 = 12 =O (mod 4). 
o 
10. Seja f(x) =ao+ a1x + · · · + anxn um polinômio com coeficientes inteiros onde an >O e n 2: 1. 
Mostrar que f(x) é composto para infinitos valores da variável x. 
Solução: Apresentamos duas soluções para esse problema. 
Solução 1. Primeiramente, observamos que como an > O, temos 
lim f(x) = +oo 
x~oo 
o que implica a existência de k E Z tal que f(y) > f(x) >O para todo y > x > k. Desta forma, 
se f(x) não assume nenhum valor primo

Crie agora seu perfil grátis para visualizar sem restrições.