Divisibilidade Parte 1

Prévia do material em texto

COMO FUI PARA A IMO
To´pico: Teoria dos Nu´meros
Leandro Farias
22 de julho de 2016
Cap´ıtulo 1
Divisibilidade I
Nesta sec¸a˜o, vamos aplicar os crite´rios de divisibilidade de forma mais efici-
ente, ale´m de aprender uma nova notac¸a˜o para a divisibilidade.
1.1 Conceitos Iniciais
Teorema 1.1.1 (Algoritmo da Divisa˜o) Para quaisquer inteiro a e b, com b >
0, enta˜o existe um u´nico par (q, r) de inteiros tais que
b = aq + r, sendo 0 ≤ r < a (1.1)
Demonstrac¸a˜o Considere o conjunto S de inteiros na˜o negativos definido da
seguinte forma
S = {a− bn | n ∈ Z e a− bn ≥ 0} (1.2)
Pelo Princ´ıpio da Boa Ordenac¸a˜o, sabemos que S tem um elemento mı´nimo,
digamos que seja r. Primeiramente, observe que
a− bq = r ⇒ a = bq + r , com 0 ≤ r (1.3)
O segundo fato e´ que r < b, pois caso contra´rio ter´ıamos 0 < r − b < r e
r − b = (a− bq)− b = a− b(q + 1) ∈ Z (1.4)
um absurdo, pois supomos que r = minS. Portanto 0 < r < b e o teorema esta´
provado.
Definic¸a˜o Sejam a e b nu´meros inteiros, com a 6= 0. Quando a divide b,
representamos por
a|b (1.5)
Proposic¸a˜o 1.1.2 Sejam a, b, c e d nu´meros inteiros. Enta˜o,
(a) Se d|a e d|b enta˜o d|(ax+ by), sendo x, y ∈ Z.
(b) Se a|b e b|c enta˜o a|c.
1
1.1. CONCEITOS INICIAIS
Demonstrac¸a˜o Perceba que
(a) Por definic¸a˜o,
a = d.a0 ⇒ a.x = d.(a0x)
b = d.b0 ⇒ b.y = d.(b0y)
Logo,
ax+ by = d.(a0x+ b0y)⇒ d|(ax+ by)
(b) Por definic¸a˜o,
b = a.a0 ⇒ b.b0 = a.(a0.b0)
c = b.b0 ⇒ c = a.(a0.b0)
assim, pela definic¸a˜o de divisibilidade, conclu´ımos que a|c.
Proposic¸a˜o 1.1.3 Todo natural e´ o produto de um ı´mpar e uma poteˆncia de 2.
Demonstrac¸a˜o Utilizaremos induc¸a˜o para resolver. Assim, faremos o passo a
passo:
(a) Casos iniciais: para
• n = 1 enta˜o n = 20 × 1.
• n = 2 enta˜o n = 21 × 1.
• n = 3 enta˜o n = 20 × 3.
(b) Hipo´tese: suponha que todo k, com 1 ≤ k ≤ n, possa ser escrito como uma
poteˆncia de 2 vezes um ı´mpar.
(c) Passo indutivo: vamos dividir em dois casos
• Se n+ 1 for ı´mpar, enta˜o n+ 1 = 20 × (n+ 1) e o problema acaba.
• Se n+ 1 for par, enta˜o n+ 1 = 2× (n+ 1)/2, sendo que
n+ 1
2
≤ n⇔ n+ 1 ≤ 2n⇔ 1 ≤ n (1.6)
enta˜o (n+ 1)/2 se encaixa na nossa hipo´tese de induc¸a˜o, o que nos permite
concluir que
n+ 1
2
= 2r × s , sendo s ı´mpar (1.7)
ou seja, n+ 1 = 2r+1 × s, conforme quer´ıamos.
Proposic¸a˜o 1.1.4 (Decomposic¸a˜o bina´ria) Todo n natural e´ soma de poteˆncias
distintas de 2.
Demonstrac¸a˜o O racioc´ınio e´ indutivo. Assim,
(a) Casos iniciais: se
Leandro Farias 2 fariasmaia@gmail.com
1.1. CONCEITOS INICIAIS
• n = 1 enta˜o n = 20.
• n = 2 enta˜o n = 21.
• n = 3 enta˜o n = 21 + 20.
• n = 4 enta˜o n = 22.
(b) Hipo´tese indutiva: suponha que todo k, 1 ≤ k ≤ n − 1, possa ser escrito
como soma de poteˆncias distintas de dois.
(c) Passo indutivo: seja p = blog2 nc, ou seja, p e´ tal que
2p ≤ n < 2p+1 (1.8)
Vamos olhar para o nu´mero n − 2p. Esse nu´mero satisfaz a hipo´tese de
induc¸a˜o, pois
n− 2p < 2p ⇔ n < 2p+1 (1.9)
Da´ı esse nu´mero pode ser escrito como soma de poteˆncias distintas de dois.
Ale´m disso, a maior poteˆncia e´ estritamente menor que 2p, uma vez que
n− 2p < 2p. Dessa forma, se
n− 2p =
j∑
i=1
2ri , com ra 6= rb e max{ri}1≤i≤j < p (1.10)
podemos concluir que
n = 2p +
j∑
i=1
2ri (1.11)
com ra 6= rb e ri < p, o que conclui a questa˜o.
Proposic¸a˜o 1.1.5 (Decomposic¸a˜o Canoˆnica) Todo nu´mero n pode ser escrito
como
n = pα11 p
α2
2 . . . p
αm
m (1.12)
sendo pi, para 1 ≤ i ≤ m, primo e pi 6= pj, para 1 < i < j < m.
Definic¸a˜o Sejam n um inteiro positivo e p um divisor primo de n. A maior
poteˆncia de p que divide n e´ presentado por α, onde
pα
∣∣∣∣∣∣n (1.13)
Proposic¸a˜o 1.1.6 Seja n um inteiro positivo, cuja fatorac¸a˜o canoˆnica e´ dada
por
n = pα11 p
α2
2 . . . p
αm
m (1.14)
enta˜o a soma dos divisores positivos de n e´ dada por
D(n) =
pα1+11 − 1
p1 − 1 ×
pα2+12 − 1
p2 − 1 × . . .×
pαm+1m − 1
pm − 1 (1.15)
Leandro Farias 3 fariasmaia@gmail.com
1.2. RESOLUC¸A˜O DE EXERCI´CIOS
Demonstrac¸a˜o Seja d um divisor de n. Assim, todos os fatores primos de d
tambe´m sa˜o de n. Ale´m disso, suponha que pk
∣∣∣d e
pβk
∣∣∣∣∣∣d (1.16)
enta˜o podemos concluir que β ≤ αk. Portanto, perceba que todo divisor de n
tem a seguinte representac¸a˜o canoˆnica
d = pβ11 p
β2
2 . . . p
βm
m (1.17)
sendo βi ≤ αi, com 1 ≤ i ≤ m. Dessa forma, ao expandirmos a expressa˜o(
1 + p1 + . . .+ p
α1
1
)(
1 + p2 + . . .+ p
α2
2
)
. . .
(
1 + pm + . . .+ p
αm
m
)
(1.18)
observamos que ha´ todos os divisores positivo de n e como
1 + pi + . . .+ p
αi
i =
pαi+1i − 1
pi − 1 (1.19)
conclu´ımos o que quer´ıamos.
1.2 Resoluc¸a˜o de Exerc´ıcios
Problema 1.2.1 C2003-P2
Sejam a1 = 19 e a2 = 98. Para n > 0, defina an+2 como sendo o resto de
(an + an+1) por 100. Qual o resto de a
2
1 + a
2
2 + . . .+ a
2
1998 por 8?
Soluc¸a˜o Primeiramente, note que para sabermos o resto de k2 por 8 basta
sabermos o resto de k por 4. Assim, se
4 | k ± 1 ⇒ 8 | k2 − 1
4 | k ⇒ 8 | k2
4 | k + 2 ⇒ 8 | k2 − 4
Agora, perceba que em algum momento os restos se repetira˜o. Como 4 | 100,
enta˜o vamos analisar essa peridiocidade atrave´s da divisa˜o por 4. Temos
4 | a1 + 1 ⇒ 8 | a21 − 1
4 | a2 + 2 ⇒ 8 | a22 + 4
4 | a3 − 1 ⇒ 8 | a23 − 1
4 | a4 + 1 ⇒ 8 | a24 − 1
4 | a5 + 0 ⇒ 8 | a25
4 | a6 + 1 ⇒ 8 | a26 − 1
4 | a7 + 1 ⇒ 8 | a21 − 1
4 | a8 + 2 ⇒ 8 | a21
4 | a1 − 1 ⇒ 8 | a21 − 1
Leandro Farias 4 fariasmaia@gmail.com
1.2. RESOLUC¸A˜O DE EXERCI´CIOS
assim, temos um ciclo de tamanho 6. Como 1998 = 6× 333, nossa soma inicial
deixa resto
333× (+1 + 4 + 1 + 1 + 0 + 1) = 8× 333 (1.20)
que e´ divis´ıvel por 8, deixando resto 0.
Problema 1.2.2 C2003-P5
Prove que para quaisquer inteiros a1, a2, ..., an, o nu´mero:
|a1 − a2|+ |a2 − a3|+ ...+ |an − a1|
e´ par.
Soluc¸a˜o Perceba que para qualquer inteiro x
2
∣∣∣|x|+ x (1.21)
pois se x e´ na˜o negativo enta˜o |x|+ x = 2x e se x e´ negativo enta˜o |x|+ x = 0.
Dessa forma, a expressa˜o em questa˜o apresenta o mesmo resto por 2 que
(a1 − a2) + (a2 − a3) + . . .+ (an − a1) = 0 (1.22)
ou seja, nossa expressa˜o e´ par.
Problema 1.2.3 C2003-P8
Encontre o menor inteiro positivo k tal que 224 + k e´ divis´ıvel por 127.
Soluc¸a˜o Primeiramente perceba que 127 = 27 − 1. Agora, sabemos que
221 − 1 = (27)3 − 1 = (27 − 1)
( k=2∑
k=0
27k
)
(1.23)
ou seja, 27 − 1
∣∣∣221 − 1. Note, ainda, que 224 = 8 × 221 = 8 × (221 − 1) + 8.
Portanto, queremos k tal que
27 − 1
∣∣∣8× (221 − 1) + 8⇔ 27 − 1∣∣∣k + 8 (1.24)
enta˜o o menor k positivo e´ 27 − 1− 8 = 119.
Problema 1.2.4 C2003-P3
(Ru´ssia/97) Os nu´meros de 1 a 37 foram escritos em uma linha de modo que a
soma dos nu´meros nas n primeiras posic¸o˜es e´ divisivel pelo nu´mero na posic¸a˜o
n + 1, para n ∈ {1, 2, . . . , 36}. Sabemos que o primeiro e´ 37 e que o segundo e´
1, ache o terceiro nu´mero.
Soluc¸a˜o Seja a o terceiro elemento. Assim, por hipo´tese
a
∣∣∣1 + 37⇒ a∣∣∣38⇒ a = 1, 2, 19 ou 38 (1.25)
Como a ≤ 37 ja´ sabemos que a 6= 38. Como o primeiro e´ 1, logo a 6= 1. Assim
nos resta saber se a = 2 ou 19.
Leandro Farias 5 fariasmaia@gmail.com
1.2. RESOLUC¸A˜O DE EXERCI´CIOS
Vamos olhar para o u´ltimo elemento dessa fila. Suponha que seja b. Enta˜o,
por hipo´tete
b
∣∣∣(1 + 2 + . . . 37− b)⇒ b∣∣∣1 + 2 + . . .+ 37⇒ b∣∣∣37× 19 (1.26)
dessa forma, b = 1, 19 ou 37, pore´m 1 e 37 sa˜o o primeiro e o segundo, respec-
tivamente, elemento da lista. Logo b = 19 e, como consequeˆncia, a = 2.
Problema 1.2.5 C2003-P24
(Irlanda/98) Encontre todos os inteiros n que possuam exatamente 16 divisores
inteiros positivos d1, d2, d3, ..., d16 tais que
1 = d1 < d2 < d3 < ..... < d16
e d6 = 18, d9 − d8 = 17.
Soluc¸a˜o Como d6 = 18 = 2 × 32 e os 6 divisores positivos ded6 tambe´m
sa˜o de n, podemos concluir que d1 = 1, d2 = 2, d3 = 3, d4 = 6 e d5 = 9.
Podemos concluir tambe´m que se existir outro primo que divide n, esse primo
devera´ ser maior do que 18, uma vez que di, com 1 ≤ i ≤ 6, ja´ tem seus valores
estabelecidos.
Vamos agora utilizar o fato que n tem 16 divisores positivo. Ora, isso nos
faz concluir que existe apenas duas possibilidades para n: 2× 37 ou 2× 33 × p,
sendo p um primo maior que 18.
• Se n = 2 × 37. Mas isso nos faz ter d9 = 162 e d7 = 27, que na˜o pode
acontecer, uma vez que d9 − d7 = 17.
• Se n = 2× 33 × p. Vamos separar em algums casos para descobrir valores
de di, para i > 6.
– Se 18 < p < 27. Enta˜o d7 = p, d8 = 27 e d9 = 2p (esse u´ltimo pois
2p < 54). Logo
2p− 27 = 17⇒ 2p = 44⇒ p = 22 (1.27)
um absurdo.
– Se 27 < p < 54. Enta˜o d7 = 27, d8 = p e d9 = 54. Logo
54− p = 17⇒ p = 37 (1.28)
– Se 54 < p. Enta˜o d7 = 27, d8 = 54 e d9 = p. Logo
p− 54 = 17⇒ p = 71 (1.29)
Portanto p = 37 ou p = 71.
Problema 1.2.6 (Teorema de Fermat) Sejam p um nu´mero primo e a um
nu´mero inteiro. Demonstre que
p
∣∣∣ap − a (1.30)
Leandro Farias 6 fariasmaia@gmail.com
1.2. RESOLUC¸A˜O DE EXERCI´CIOS
Soluc¸a˜o Utilizaremos o conceito de induc¸a˜o para nos auxiliar a concluir o pro-
blema. A induc¸a˜o sera´ feita em a. Mas antes, vamos fazer a parte o caso p = 2.
Ora, de imediato sabemos que 2
∣∣∣a(a− 1) e o caso esta´ solucionado.
Agora considere p > 2. Perceba que se a for negativo, basta tomarmos
b = −a que o problema fica o mesmo, pois
ap − a = (−b)p − (−b) = −bp + b = −(bp − b) (1.31)
recaindo no caso a positivo. Portanto basta mostrarmos para a > 0. Conforme
o processo de induc¸a˜o estabelece, faremos os treˆs passos de induc¸a˜o:
a) Casos Iniciais: para a = 0 e a = 1, verifica-se facilmente a veracidade do
Teorema.
b) Hipo´tese de Induc¸a˜o: suponha que p
∣∣∣bp − b para 0 ≤ b ≤ a.
c) Passo indutivo: Perceba que
(a+ 1)p − (a+ 1) = (ap − a) +
p−1∑
k=1
(
p
k
)
(1.32)
Por hipo´tese de induc¸a˜o ja´ sabemos que p
∣∣∣ap − a. Agora veja que(
p
k
)
=
p!
k!(p− k)! (1.33)
e como p | p!, p - k! e p - (p− k)!, conclu´ımos que
p
∣∣∣(p
k
)
, para 1 ≤ k ≤ p− 1 (1.34)
portanto p
∣∣∣(a+ 1)p − (a+ 1) e, por induc¸a˜o, podemos garantir a veracidade
do Teorema.
Problema 1.2.7 C2003-P26
Sejam n > 2 e k inteiros positivos. Prove que
(n− 1)2
∣∣∣nk − 1⇔ n− 1∣∣∣k (1.35)
Soluc¸a˜o Perceba que
nk − 1 = ((n− 1) + 1)k − 1 = (n− 1)× k +
k∑
i=2
(
k
i
)
(n− 1)i (1.36)
sabemos que (n− 1)2
∣∣∣(n− 1)i, para 2 ≤ i ≤ k, ou seja,
(n− 1)2
∣∣∣ k∑
i=2
(
k
i
)
(n− 1)i (1.37)
Assim podemos afirmar que
(n− 1)2
∣∣∣nk − 1⇔ (n− 1)2∣∣∣(n− 1)× k ⇔ n− 1∣∣∣k (1.38)
Leandro Farias 7 fariasmaia@gmail.com
1.2. RESOLUC¸A˜O DE EXERCI´CIOS
Problema 1.2.8 Prove que, para cada n natural, o produto
(n+ 1)(n+ 2) . . . (2n) (1.39)
e´ divis´ıvel por 2n.
Soluc¸a˜o Perceba que
(n+ 1)(n+ 2) . . . (2n) =
(2n)!
n!
(1.40)
para cada k, com 1 ≤ k ≤ n, no fator n!, existe o fator 2k em (2n)!. Logo,
(n+ 1)(n+ 2) . . . (2n) = 2n × 1× 3× . . . (2n− 1) (1.41)
o que conclui nossa soluc¸a˜o.
Problema 1.2.9 C2003-P28
A soma digital D(n) de um inteiro positivo n e´ definida recursivamente como
segue:
D(n) =
{
n , se 1 ≤ n ≤ 9
D(a1 + a2 + . . .+ am) , se 10 ≤ n (1.42)
Demonstre que para qualquer n tem-se que D(1234× n) = D(n)
Soluc¸a˜o Primeiramente, perceba que D(n) e´ um nu´mero de um d´ıgito. Perceba
tambe´m que n e D(n) tem o mesmo resto da divisa˜o por 9, uma vez que em cada
passo e´ comparado o nu´mero com a soma de seus d´ıgitos. Consequentemente,
D(n) e´ o resto da divisa˜o de n por 9. Como 1234× n deixa o mesmo resto que
(1+2+3+4)×n = 10×n por 9, e 10×n deixa o mesmo resto que n na divisa˜o
por 9, conclu´ımos que
D(1234× n) = D(n) (1.43)
Problema 1.2.10 C2003-P80
(Teste IMO Brasil) Determine todos os inteiros positivos m e n com n ≥ m tal
que
• m2 − n2
∣∣∣n2 +m;
• n2 −m
∣∣∣m2 + n
Soluc¸a˜o O segundo item nos permite concluir que
n2 −m ≤ m2 + n⇒ n2 − n ≤ m2 +m⇒ n(n− 1) +m+ 1 ≤ (m+ 1)2 (1.44)
Sabemos que n(n− 1) e´ uma func¸a˜o crescente. Caso n > m+ 1 enta˜o
n(n− 1) +m+ 1 > (m+ 1)m+m+ 1 = m2 + 2m+ 1 = (m+ 1)2 (1.45)
o que e´ um absurdo. Portanto n = m ou n = m + 1. Caso n = m + 1, atrave´s
da equac¸a˜o 1 obtemos
n2 −m2
∣∣∣n2 +m⇒ 2m+ 1∣∣∣m2 + 3m+ 1 (1.46)
Leandro Farias 8 fariasmaia@gmail.com
1.2. RESOLUC¸A˜O DE EXERCI´CIOS
ou seja,
2m+ 1
∣∣∣(m2 + 3m+ 1)2− (2m+ 1)m = 5m+ 2 (1.47)
utilizando as propriedades da divisibilidade,
2m+ 1
∣∣∣− (5m+ 2)2 + (2m+ 1)5⇒ 2m+ 1∣∣∣1 (1.48)
ou seja, na˜o existe m ∈ N nesse caso.
Caso n = m, na˜o existe soluc¸a˜o, pois n2 −m2 = 0 que na˜o divide nenhum
inteiro na˜o nulo. Logo na˜o ha´ soluc¸o˜es.
Problema 1.2.11 C2003-P129
(Ru´ssia/2002) Um nu´mero de quatro algarismo e´ escrito em um quadro negro.
E´ permitido adicionar 1 ou subtrair 1 de quaiquer dois algarismos adjacentes,
desde que eles sejam diferentes de 9 e 0, ou seja, na˜o pode adicionar 1 ao 9 nem
subtrair 1 de 0. Partindo de 1234, e´ possivel obtermos 2002 apo´s efetuarmos
essas operac¸o˜es?
Soluc¸a˜o Perceba que a operac¸a˜o deixa o resto da divisa˜o por 11 do nu´mero ini-
cial constante. Como os dois nu´meros no enunciado apresentam resto distintos,
na˜o e´ poss´ıvel obter um a partir do outro.
Problema 1.2.12 C2004-P21
(Hungria/2001) Sejam m,n inteiros tais que 1 ≤ m ≤ n. Prove que m e´ um
divisor de:
n×
m−1∑
k=0
(−1)k
(
n
k
)
Soluc¸a˜o Vamos tentar reduzir o valor desse somato´rio. Atrave´s da Relac¸a˜o de
Stifel, sabemos que (
n
0
)
=
(
n− 1
0
)
(
n
1
)
=
(
n− 1
1
)
+
(
n− 1
0
)
(
n
2
)
=
(
n− 1
2
)
+
(
n− 1
1
)
...(
n
m− 1
)
=
(
n− 1
m− 1
)
+
(
n− 1
m− 2
)
Potanto, nosso somato´rio, em mo´dulo, se reduz para
n×
(
n− 1
m− 1
)
= n× (n− 1)!
(m− 1)!(n−m)! = m×
n× (n− 1)!
m!(n−m)! = m×
(
n
m
)
(1.49)
que e´ divis´ıvel por m.
Leandro Farias 9 fariasmaia@gmail.com
1.2. RESOLUC¸A˜O DE EXERCI´CIOS
Problema 1.2.13 C2004-P12
(Cone Sul/2003) Considere a sequeˆncia {an} definida da seguinte maneira:
a1 = 1, a2 = 3, an+2 = 2an+1an + 1, para todo inteiro n ≥ 1. Prove que a
ma´xima poteˆncia de 2 que divide a4006 − a4005 e´ 22003.
Soluc¸a˜o Vamos fazer alguns casos iniciais para estudar como se comporta essa
sequeˆncia, ale´m da nova sequeˆncia xk = ak − ak−1. Temos
• a1 = 1, a2 = 3 e x2 = 2
• a3 = 7 e x3 = 4
• a4 = 43 e x4 = 36
Vamos mostrar por induc¸a˜o que 2n
∣∣∣∣∣∣x2n e 2n+1∣∣∣x2n+1. Os casos iniciais sa˜o
verdade. Suponha enta˜o que nossa hipo´tese de induc¸a˜o seja va´lida. Queremos
mostrar que
2n+1
∣∣∣∣∣∣x2n+2 e 2n+2∣∣∣x2n+3 (1.50)
Ora, pela pro´pria definic¸a˜o de an temos que
x2n+2 = a2n+2 − a2n+1 (1.51)
e, conforme hipo´tese de formac¸a˜o da sequeˆncia,
x2n+2 = (2a2n+1a2n + 1)− (2a2na2n−1 + 1) = 2a2n(a2n+1 − a2n−1) (1.52)
Assim, vamos determinar qual a maior poteˆncia de 2 que divide a2n+1 − a2n−1.
Pela nossa hipo´tese de induc¸a˜o, sabemos que
x2n+1 = 2
n+1k1 e x2n = 2
nk2 (1.53)
sendo k2 ı´mpar. Portanto,
a2n+1 − a2n−1 = x2n+1 + x2n = 2n(2k1 + k2) (1.54)
assim, uma vez que k2 e´ ı´mpar, podemos concluir que 2
n
∣∣∣∣∣∣(a2n+1 − a2n−1), o
que nos permite afirmar que 2n+1
∣∣∣∣∣∣x2n+2 ja´ que an e´ ı´mpar.
Agora, vamos a segunda parte da nossa induc¸a˜o. Perceba que
x2n+3 = a2n+3 − a2n+2 = 2a2n+1(a2n+2 − a2n) (1.55)
mas sabemos que
x2n+2 = 2
n+1k1 e x2n+1 = 2
n+1k2 (1.56)
logo
a2n+2 − a2n = x2n+2 − x2n+1 = 2n+1(k1 − k2) (1.57)
portanto 2n+2
∣∣∣x2n+3 e, conforme o princ´ıpio da induc¸a˜o, o problema esta´ solu-
cionado.
Leandro Farias 10 fariasmaia@gmail.com
1.2. RESOLUC¸A˜O DE EXERCI´CIOS
Problema 1.2.14 C2004-P4
(Poloˆnia/1992) Parao natural n > 0, seja S(n) a soma dos divisores positivos
de n. Prove que para todo inteiro n > 1, o produto S(n− 1)S(n)S(n+ 1) e´ par.
Soluc¸a˜o Suponha que
n− 1 =
a∏
i=1
pαii , n =
b∏
i=1
qβii , n+ 1 =
c∏
i=1
rγii (1.58)
Vamos dividir em dois casos para que possamos identificar o mdc entre n− 1 e
n+ 1.
a) Caso n− 1 e n+ 1 forem ı´mpares.
Enta˜o, perceba que para S(n − 1)S(n)S(n + 1) seja ı´mpar, e´ preciso que
S(n− 1) e S(n+ 1) sejam ı´mpares. Mas sabemos que
S(n− 1) =
a∏
i=1
(1 + pi + . . .+ p
αi
i ) (1.59)
e para que S(n− 1) seja ı´mpar, para cada 1 ≤ i ≤ a, a soma
1 + pi + . . .+ p
αi
i (1.60)
deve ser ı´mpar, ou seja, αi deve ser par, uma vez que pi 6= 2. Logo n−1 deve
ser quadrado perfeito. Analogamente, para que S(n + 1) seja ı´mpar, enta˜o
n + 1 deve ser quadrado perfeito. Mas isso e´ um absurdo, pois na˜o existem
dois quadrados perfeitos cuja diferenc¸a seja 2.
b) Caso n− 1 e n+ 1 forem pares.
Enta˜o, analogamente ao que foi feito para o n − 1 no caso (a), conclu´ımos
que n deve ser quadrado perfeito. Agora vamo estudar n−1 e n+1. Perceba
que apenas um deles 21 e´ a maior poteˆncia de 2 que o divide, pois mdc(n−
1, n+ 1) = 2. Vamos dividir em mais dois casos
i) se 21
∣∣∣∣∣∣n− 1.
Enta˜o, do mesmo racioc´ınio utilizado no item (a) podemos garantir que
(n − 1)/2 sera´ um quadrado perfeito. Perceba que a poteˆncia de 2 que
divide n+1 pode ser 2par ou 2impar o que nos permite concluir que n+1
e´ quadrado perfeito ou (n+ 1)/2. Nos resta testar esses dois casos.
Suponha primeiro que n+ 1 seja quadrado perfeito. Como n tambe´m e´
quadrado perfeito, so´ existe a possibilidade n = 0, mas assim (n−1)/2 =
−1/2 quado perfeito.
Suponha agora aque (n+ 1)/2 seja quadrado perfeito. Como (n− 1)/2
tambe´m e´ quadrado perfeito, so´ existe a possibilidade (n− 1)/2 = 0, ou
seja, n = 1. Mas n > 1, por hipo´tese.
ii) se 21
∣∣∣∣∣∣n+ 1.
Analogamente, (n+1)/2 e´ quadrado perfeito e devemos separar em dois
casos: n− 1 e´ quadrado perfeito ou (n− 1)/2 e´ quadrado perfeito. Em
ambos os casos e´ fa´cil ver que chegaremos a um absurdo.
Leandro Farias 11 fariasmaia@gmail.com
1.3. PROBLEMAS PROPOSTOS
1.3 Problemas Propostos
C2003-P28
Problema 7. Determine todos os inteiros positivos x e y tais que
x2 − 200! = y!
C2003-P29
Problema 8. Mostre que dados 5 inteiros quaisquer na˜o necessariamente dis-
tintos, podemos sempre escolher treˆs deles tais que sua soma e´ divisilvel por 3.
C2003-P35
Problema 9 ( Primo de Mersene ). Sejam os inteiros a e n, com n 6= 2 e
a 6= 2. Se an − 1 e´ primo, enta˜o a = 2 e n e´ primo.
C2003-P38
Problema 10. Se 2n + 1 e´ primo e n > 2, enta˜o 2n + 1 e´ composto.
C2003-P39
Problema 11. Mostre que se 2n + 1 e´ primo, sendo n ∈ N e n > 0, enta˜o n
deve ser uma poteˆncia de 2.
C2003-P40
Problema 12. Prove que:
641
∣∣∣232 + 1
C2003-P41
Problema 13. Seja n = 2p−1(2p − 1) e seja 2p − 1 um nu´mero primo. Prove
que a soma dos divisores positivos de n e´ 2n.
C2003-P44
Problema 14. Seja an = 11...11 um nu´mero que apresenta n 1’s. Prove que
se an e´ primo, enta˜o n e´ primo.
C2003-P47
Problema 15 Provar que para todo inteiro positivo n o nu´mero
an = 2903
n − 803n − 464n + 261n
e´ divis´ıvel por 1897.
C2003-P50
Problema 16 Demonstre que
n∏
k=1
(a+ k)
e´ divisivel por n!.
Leandro Farias 12 fariasmaia@gmail.com
1.3. PROBLEMAS PROPOSTOS
C2003-P60
Problema 17 Dados seis inteiros quaiquer, nunhum dos quais mu´ltiplo de 11,
mostre que ou ha´ dois deles que deixam um mesmo resto quando divididos por
11 ou ha´ dois deles cuja soma e´ um multiplo de 11.
C2003-P61
Problema 18 (Ru´ssia). Sa˜o dados 15 nu´meros inteiros de 2 a 1992, dois a
dois primos entre si, mostre que ao menos um desses nu´meros e´ primo.
Leandro Farias 13 fariasmaia@gmail.com
1.3. PROBLEMAS PROPOSTOS
Dicas
Problema 1
Problema 2
Problema 3
Problema 4 e 5
Problema 6
Problema 7
Leandro Farias 14 fariasmaia@gmail.com
1.3. PROBLEMAS PROPOSTOS
Soluc¸a˜o dos Problemas Propostos
Leandro Farias 15 fariasmaia@gmail.com
1.3. PROBLEMAS PROPOSTOS
Refereˆncias Bibliogra´ficas
[1] Notas de aula do Professor Emanuel Carneiro.
[2] Artigo de desigualdades do Prof Caminha na Eureka nr ?.
[3] Putnam and Beyond
[4] www.mathlinks.ro
[5] Notas de aula do Prof Shine
Leandro Farias 16 fariasmaia@gmail.com