Lista02Comentada(1)

Prévia do material em texto

Resolução de Problemas
Lista 02
Soluções dos Exerćıcios de Divisibilidade
1. Prove que se n é ı́mpar
(a) n2 − 1 é diviśıvel por 8;
Demonstração. Como n é ı́mpar, temos que n = 2q + 1 para algum
q ∈ Z. Assim,
n2 − 1 = (2q + 1)2 − 1 = 4q2 + 4q + 1− 1 = 4q2 + 4q = 4q(q + 1).
Como q e q + 1 são consecutivos, um deles tem que ser par. Logo,
n2 − 1 é diviśıvel por 8.
(b) n3 − n é diviśıvel por 24;
Demonstração. Usaremos o fato que
se a, b são primos entre si, então c é diviśıvel por ab se, e somente
se, c é diviśıvel por a e por b.
Assim, para mostrar que n3 − n é múltiplo de 24, basta mostrar que
n3 − n é múltiplo de 3 e de 8, uma vez que 3 e 8 são primos entre si.
Observe que n3−n = n(n2− 1). Como n é ı́mpar, segue do exerćıcio
anterior que n3 − n é diviśıvel por 8. A divisibilidade por 3 decorre
do lema dos restos. De fato, se n ≡ 0 mod 3, n3 − n será múltiplo
de 3, claramente. Se n ≡ 1 mod 3, temos que n3 − n será múltiplo
de 3, já que
13 − 1 ≡ 0 mod 3.
Se n ≡ 2 mod 3, temos que n3 − n será múltiplo de 3, já que
23 − 2 ≡ 0 mod 3,
completando assim a prova.
(c) n2 + (n+ 2)2 + (n+ 4)2 + 1 é diviśıvel por 12.
Demonstração. Novamente, usaremos o fato que se a, b são primos entre
si, então c é diviśıvel por ab se, e somente se, c é diviśıvel por a e por
b. Assim, para mostrar que a expressão é múltiplo de 12, basta mostrar
que 3 e de 4. Vamos primeiro à divisibilidade por 4. Observe que como
n é ı́mpar, basta verificar os casos quando n ≡ 1 mod 4 e n ≡ 3 mod 4.
Quando n ≡ 1 mod 4 temos que
n2 +(n+2)2 +(n+4)2 +1 ≡ 12 +(1+2)2 +(1+4)2 +1 ≡ 36 ≡ 0 mod 4.
Do mesmo modo, quando n ≡ 3 mod 4 temos que
n2 +(n+2)2 +(n+4)2 +1 ≡ 32 +(3+2)2 +(3+4)2 +1 ≡ 84 ≡ 0 mod 4.
Para verificar a divisibilidade por 3, repetimos o argumento usando os
restos da divisão por 3. Observe que quando n ≡ 0 mod 3 temos que
n2 +(n+2)2 +(n+4)2 +1 ≡ 02 +(0+2)2 +(0+4)2 +1 ≡ 21 ≡ 0 mod 3.
Procedendo de modo inteiramente análogo para os casos n ≡ 1 mod 3 e
n ≡ 2 mod 3, completamos a prova.
2. Três números primos p, q e r, maiores que 3, formam uma progressão
aritmética, ou seja, q = p+ d e r = p+ 2d. Prove que d é diviśıvel por 6.1
Demonstração. Temos que d é par, já que d = q − p, com p e q primos
maiores que dois, logo ı́mpares. Basta mostrar que d é diviśıvel por 3.
Ora, supondo o contrário, temos que d ≡ 1 mod 3 ou n ≡ 2 mod 3.
Analisando o resto de q e r módulo 3 nas tabelas a seguir (em função dos
restos de d nas colunas e p nas linhas).
Para q temos
mod 3 d ≡ 1 d ≡ 2
p ≡ 1 2 0
p ≡ 2 0 1.
Para r temos:
mod 3 d ≡ 1 d ≡ 2
p ≡ 1 0 1
p ≡ 2 1 0.
1Foi demonstrado em 2004 pelos Matemáticos B. Green e T. Tao que existem progressões
aritméticas de tamanho arbitrariamente grande formadas somente por primos. A prova pode
ser encontrada em www.arxiv.org.
Logo, se d não é diviśıvel por 3, ou q ou r serão diviśıveis por 3, o que é
imposśıvel, já que são ambos números primos.
3. Mostre que 311 − 3 é diviśıvel por 112.
4. Um robô possui dois botões, permitindo que a cada momento ele suba a
degraus ou desça b degraus de uma escada com infinitos degraus. Sabendo
que o robô está no ińıcio da escada, pergunta-se:
(a) Se a = 12 e b = 3, é posśıvel que o robô visite todos os degraus após
uma sucessão desses movimentos?
Demonstração. Se apertamos o botão de subir x vezes e o de descer
y vezes, o robô irá subir ou descer 12x − 3b degraus. Note que esse
número é sempre múltiplo de 3, não sendo posśıvel para o robô com
uma sequência desses movimentos atingir um degrau com número
que não é diviśıvel por 3.
(b) Mostre que se a e b são primos entre si, o robô consegue visitar todos
os degraus.
Demonstração. Como a e b são primos entre si, pelo Teorema de
Bezout-Bachet, é posśıvel encontrar x e y de modo que ax− by = 1.
Assim, o robô pode sair do ńıvel inicial e ir para o degrau 1 apertando-
se x vezes o botão de subir e em seguida apertando-se y vezes o botão
de descer. Repetindo esse procedimento, o robô pode atingir qualquer
degrau.
5. Encontre o resto que deixa
(a) 2001 · 2002 · 2003 · 2004 + 20052 quando é dividido por 7;
Demonstração. Vamos usar o lema dos restos. 2001 quando dividido
por 7 deixa resto 6; Assim, 2002 é diviśıvel por 7 e 2005 deixa resto
3 quando dividido por 7. Logo, 20052 deixa resto 2, já que 32 deixa
resto 2 quando dividido por 7.
(b) 2100 quando é dividido por 3;
Demonstração. 22 resto 1 quando dividido por 3. Logo, 2100 = (22)50
deixa resto 1 quando dividido por 3.
(c)
(
1237156 + 34
)28
quando é dividido por 111.
6. Encontrar o último d́ıgito dos números
(a) 19892005;
(b) 777777 + 250;
(c) 1 + 22 + 32 + · · ·+ 20052.
7. Verifique que
111 . . . 1︸ ︷︷ ︸
2012 uns
= 222 . . . 2︸ ︷︷ ︸
1006 dois
+(333 . . . 3︸ ︷︷ ︸
1006 três
)2.
Demonstração. Observe que
111 . . . 1︸ ︷︷ ︸
2012 uns
=
102012 − 1
9
e que
222 . . . 2︸ ︷︷ ︸
1006 dois
= 2×
(
101006 − 1
)
9
e (333 . . . 3︸ ︷︷ ︸
1006 três
)2 = 9×
(101006 − 1
9
)2
.
Portanto, basta verificar que
102012 − 1
9
= 2× 10
1006 − 1
9
+ 9×
(101006 − 1
9
)2
,
De fato, cancelando 9 em ambos os lados
102012 − 1 = 2× (101006 − 1) + (101006 − 1)2,
como queŕıamos demonstrar.
8. Demonstre que o número 1 000 . . . 00︸ ︷︷ ︸
2012 zeros
1 é composto.
Demonstração. Para termos uma idéia da prova deste fato, vamos provar
que 1001 é composto. Ora, temos que
1001 = 11× 91.
Do mesmo modo, 100001 = 11 × 9091 e que 10000001 = 11 × 909091.
Assim, depois dessa análise inicial, fica bem claro que nosso candidato
para divisor do número pedido é o 11; Podemos verificar sem maiores
dificuldades que
1 000 . . . 00︸ ︷︷ ︸
2012 zeros
1 = 11× 9090 . . . 90︸ ︷︷ ︸
1005 vezes
91.
9. Considere o polinômio p(n) = amn
m+am−1n
m−1+ · · ·+a0 de grau m ≥ 1
com coeficientes inteiros e n ∈ N. Prove que p(n) é um número composto
para infinitos valores de n.2
10. Prove que se (x0, y0) é uma solução da equação diofantina linear ax−by =
1, então a área do triângulo cujos vértices são (0, 0), (b, a) e (x0, y0) é
1/2.
11. Ao entrar numa sala, João se depara com 100 interruptores e 100 lâmpadas,
numerados de 1 a 100. O interruptor n acende somente a lâmpada n, para
cada valor de n = 1, 2, . . . , 100. De ińıcio, todas as 100 lâmpadas estão
apagadas. João aperta todos os interruptores múltiplos de 2. A seguir,
aperta todos os múltiplos de 3, e assim sucessivamente, até o único inter-
ruptor múltiplo de 100. Ao final deste procedimento, pergunta-se:
(a) Quais lâmpadas estão apagadas?
Demonstração. Dado um número natural n = pα11 · · · p
αk
k , com p
′
is
primos e α′is ≥ 0, sabemos que o número de divisores de n é
d(n) = Πki=1(αi + 1).
Para responder essa pergunta, basta analisar quantos divisores cada
número de 1 a 100 possui. Na verdade, basta verificar a paridade
da quantidade de divisores de cada número, já que se d(n) for par,
a lâmpada n ficará acesa. Da expressão acima, é claro que d(n) é
ı́mpar se, e somente se, αi é par, para cada valor de i. Assim, d(n)
é ı́mpar se, e somente se, n é um quadrado. Logo, as lâmpadas que
ficarão apagadas são aquelas que têm número que é um quadrado
perfeito.
(b) Quantas lâmpadas acenderam exatamente 4 vezes?
Demonstração. Basta contar quantas lâmpadas tem 8 ou 9 diviso-
res. Fazendo a contagem usando a expressão em produto de primos,
obtemos a lista: 24, 30, 36, 40, 42, 54, 56, 66, 70, 78, 88 e 100.
(c) Qual é o número da lâmpada que mais acendeu?
Demonstração. Essa lâmpada corresponde aos números que tem mais
divisores. O problema está mal-formulado, já que temos cinco números
com exatamente 12 divisores: 60, 72, 84, 90 e 96.
2Sugestão: Use o fato de que existe a ∈ N tal que α = |p(a)| > 1 e mostre que α divide a
p(αk + a), para todo k ∈ Z.