Polos Olimpicos de Treinamento Curso de
Polos Olimpicos de Treinamento Curso de
Polos Olimpicos de Treinamento Curso de
O Algoritmo de Euclides
Exemplo 1. Seja S um conjunto infinito de inteiros não negativos com a seguinte propri-
edade: dados dois quaisquer de seus elementos, o valor absoluto da diferença entre eles
também pertence a S. Se d é o menor elemento positivo de S, prove que S consiste de
todos os múltiplos de d.
Como um inteiro não nulo possui apenas um número finito de divisores, se b e c são ambos
não nulos, o número mdc(b, c) sempre existe, isto é, sempre está bem definido.
mdc(123, 164) = mdc(123, 41) = mdc(41, 123) = mdc(41, 82) = mdc(41, 41) = 41.
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 3 - Samuel Feitosa
a) (819, 357)?
b) (19, 79)?
mdc(819, 357) = mdc(462, 357) = mdc(105, 357) = mdc(105, 252) = . . . = mdc(21, 21) = 21.
Pelo Lema de Euclides, o mdc entre os dois números em um ticket nunca muda. Como
mdc(1, 2) = 1 ̸= 21 = mdc(819, 357), não podemos alcançar o par do item a).
Para o item b), indiquemos com → uma operação de alguma das máquinas. Veja que:
R S R R R S R R R
(2, 1) → (3, 1) → (1, 3) → (4, 3) → . . . → (19, 3) → (3, 19) → (22, 19) → (41, 19) →
R
(60, 19) → (79, 19).
Observação 5. Procurar invariantes sempre é uma boa estratégia para comparar confi-
gurações diferentes envolvidas no problema. Confira o problema proposto 31.
Definição 6. Dizemos que dois inteiros p e q são primos entre si ou relativamente primos
se mdc(p, q) = 1. Dizemos ainda que a fração pq é irredutı́vel se p e q são relativamente
primos.
21n + 4
Exemplo 7. (IMO 1959) Prove que é irredutı́vel para todo número natural n.
14n + 3
Pelo lema de Euclides, mdc(21n+4, 14n+3) = mdc(7n+4, 14n+3) = mdc(7n+1, 7n+2) =
mdc(7n + 1, 1) = 1.
i) Se k =
̸ 0, mdc(ka, kb) = kd.
! "
a b
ii) mdc , = 1.
d d
iii) Se mdc(a, c) = 1, então mdc(a, bc) = d.
Exemplo 9. (Olimpı́ada Inglesa) Se x e y são inteiros tais que 2xy divide x2 + y 2 − x, prove
que x é um quadrado perfeito
2
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 3 - Samuel Feitosa
2abd2 | d2 a2 + d2 b2 − da ⇒
d2 | d2 a2 + d2 b2 − da ⇒
d2 | −da ⇒
d | a.
Exemplo 10. No planeta X, existem apenas dois tipos de notas de dinheiro: $5 e $78. É
possı́vel pagarmos exatamente $7 por alguma mercadoria? E se as notas fossem de $ 3 e $
78?
Queremos estudar a versão mais geral desse exemplo. Quais são os valores que podemos
pagar usando notas de $a e $b? Em particular, estaremos interessados em conhecer qual o
menor valor que pode ser pago. Para responder essa pergunta, precisaremos do algoritmo
de Euclides:
A sequência de restos não pode diminuir indefinidamente pois 0 ≤ ri < ri−1 e existe apenas
um número finito de naturais menores que c. Assim, para algum j, obteremos rj+1 = 0.
O maior divisor comum de b e c será rj , ou seja, o último resto não nulo da sequência de
divisões acima.
3
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 3 - Samuel Feitosa
Então,
mdc(b, c) = mdc(c, r1 ) = mdc(r1 , r2 ) = . . . = mdc(rj−1 , rj ) = rj .
Podemos extrair mais informações do Algoritmo de Euclides. Para isso, iremos organizar
as equações do exemplo acima de outra forma.
Essencialmente, a equação mdc(x+qy, y) = mdc(x, y) nos diz que podemos subtrair q vezes
um número de outro sem alterar o máximo divisor comum do par em questão. Realizando
esse procedimento sucessivas vezes, subtraindo o número menor do maior, podemos obter
pares com números cada vez menores até que chegarmos em um par do tipo (d, d). Como o
máximo divisor comum foi preservado ao longo dessas operações, d será o máximo divisor
comum procurado. Iremos repetir o exemplo anterior registrando em cada operação quantas
vezes um número é subtraido do outro. Isso será feito através de dois pares de números
auxiliares:
Da primeira linha para a segunda, como subtraı́mos 6 vezes o número 6409 de 42823,
subtraı́mos 6 vezes o par (0, 1) de (1, 0), obtendo: (1, 0) − 6(0, 1) = (1, −6). Se em uma
dada linha, temos:
(x, x + qy)) | (a, b)(c, d);
então, a próxima linha deverá ser:
4
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 3 - Samuel Feitosa
obtemos que:
Em cada linha, essa propriedade é mantida pois a mesma subtração que é realizada no
primeiro par também é realizada entre os dois últimos pares. Analisando o último par,
podemos escrever 17 como combinação de 42823 e 6409 de duas formas diferentes:
Teorema 13. (Bachet-Bèzout) Se d = mdc(a, b), então existem inteiros x e y tais que
ax + by = d.
Observação 14. (Para professores) A prova mais comum apresentada para o teorema an-
terior baseia-se na análise do conjunto de todas as combinações lineares entre a e b e quase
sempre se preocupa apenas com mostrar a existência de x e y. Acreditamos que o algoritmo
para encontrar x e y facilite o entendimento do teorema para os alunos mais jovens. Entre-
tanto, frequentemente utilizemos apenas a parte da existência descrita no enunciado. Além
disso, preferimos discutir um exemplo numérico ao invés de formalizarmos uma prova e
sugerimos que o professor faça o mesmo com mais exemplos em aula.
Exemplo 15. (Olimı́ada Russa 1995) A sequência a1 , a2 , ... de naturais satisfaz mdc(ai , aj ) =
mdc(i, j) para todo i ̸= j Prove que ai = i para todo i.
5
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 3 - Samuel Feitosa
Exemplo 17. (Olimpı́ada Russa 1964) Sejam x, y inteiros para os quais a fração
x2 + y 2
a=
xy
é inteira. Ache todos os possı́veis valores de a.
então
x2 + y 2 x 0 2 + y0 2
a= = ·
xy x 0 y0
Nessa condição, como x0 divide y02 e y0 divide x20 , cada um deles é igual a 1, donde
12 + 12
a= = 2.
1·1
6
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 3 - Samuel Feitosa
a(a + 5)
mmc(a, a + 5) = ,
mdc(a, a + 5)
b(b + 5)
mmc(b, b + 5) = .
mdc(b, b + 5)
7
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 3 - Samuel Feitosa
Exemplo 22. Uma máquina f executa operações sobre o conjunto de todos os pares de
inteiros positivos. Para cada par de inteiros positivos, ela fornece um inteiro dado pelas
regras:
f (x, x) = x, f (x, y) = f (y, x), (x + y)f (x, y) = yf (x, x + y).
Determine f (2012, 2012! + 1).
Temos então uma forte suspeita de que f = mmc. Seja S o conjunto de todos os pa-
res de inteiros positivos (x, y) tais que f (x, y) ̸= mmc(x, y), e seja (m, n) o par em S
com a soma m + n minima. Note que todo par da forma (n, n) não está em S pois
f (n, n) = n = mmc(n, n). Assim, devemos ter m ̸= n. Suponha sem perda de generalidade
que n > m. Portanto:
Como o par (m, m − n) não está em S, dado que a soma de seus elementos é menor que
m + n, temos:
f (m, n − m) = mmc(m, n − m) ⇒
n−m
· f (m, n) = (n − m)mmc(m, m + (n − m)) ⇒
n
f (m, n) = mmc(m, n)
Uma contradição. Desse modo, S deve ser um conjunto vazio e f (x, y) = mmc(x, y)
para todos os pares de inteiros positivos. Como 2012 | 2012!, mdc(2012, 2012! + 1) = 1 e
consequentemente mmc(2012, 2012! + 1) = 2012(2012! + 1).
Problemas Propostos
a) mdc(n, n2 + n + 1).
8
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 3 - Samuel Feitosa
240 + 1 8
! "
c) mdc ,2 + 1 .
28 + 1
Problema 24. Encontre mdc(2n + 13, n + 7)
12n+1
Problema 25. Prove que a fração 30n+2 é irredutı́vel.
a+b
Problema 26. Sejam a, b, c, d inteiros não nulos tais que ad − bc = 1. Prove que c+d é uma
fração irredutı́vel.
Problema 27. Mostre que mdc(am − 1, an − 1) = amdc(m,n) − 1.
Problema 28. Mostre que se mdc(a, b) = 1, então:
mdc(a + b, a2 − ab + b2 ) = 1 ou 3
mdc(a + b, 4) = 4.
mdc(n! + 1, (n + 1)! + 1) = 1.
Problema 31. No exemplo 4, determine todos os pares que podem ser obtidos começando-se
com o par (1, 2).
Problema 32. Qual o máximo divisor comum do conjunto de números:
Claramente, toda fração ab < 1 com mdc(a, b) = 1, está em algum Fn . Mostre que se m/n
e m′ /n′ são frações consecutivas em Fn temos |mn′ − nm′ | = 1.
Problema 34. (Resvista Quantum - Jornal Kvant) Todas as frações irredutı́veis cujos de-
nominadores não excedem 99 são escritas em ordem crescente da esquerda para a direita:
1 1 a 5 c
, ,..., , , ,...
99 98 b 8 d
a c 5
Quais são as frações e em cada lado de ?
b d 8
9
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 3 - Samuel Feitosa
1 1 1
Problema 35. (OBM) Para cada inteiro positivo n > 1, prove que 1 + 2 + 3 +...+ n não
é inteiro.
1 1
Problema 36. Determine todas as soluções em inteiros positivos para a + b = 1c .
Problema 37. Inteiros positivos a e b, relativamente primos, são escolhidos de modo que
a+b
seja também um inteiro positivo. Prove que pelo menos um dos números ab + 1 e
a−b
4ab + 1 é um quadrado perfeito.
Problema 38. (IMO 1979) Sejam p, q números naturais primos entre si tais que:
p 1 1 1 1
= 1 − + − ... − + .
q 2 3 1318 1319
Prove que p é divisı́vel por 1979.
23. (a)
(b)
Outra opção seria observar que o mdc procurado deve dividir o número 3(2 ×
2012 + 1) − 2(3 × 2012) = 3 e que 2 × 2012 + 1 não é múltiplo de 3.
(c)
240 + 1 8
! "
$ 32 24 16 8 8
%
mdc , 2 + 1 = mdc 2 + 2 + 2 + 2 + 1, 2 + 1 ,
28 + 1
= mdc (2 − 1) + (224 + 1) + (216 − 1) + (28 + 1) + 1, 28 + 1 ,
$ 32 %
= mdc(1, 28 + 1) = 1.
10
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 3 - Samuel Feitosa
24.
25.
11
36. Sejam d = mdc(a, b), a = dx, b = dy. Consequentemente mdc(x, y) = 1 e podemos
escrever a equação como:
1 1 1
+ = ⇒
a b c
bc + ac = ab
dyc + dxc = d2 xy
c(x + y) = dxy
1 1 1 1 1 1 1
1− + − + ... − = + + ... +
2 3 4 2n n+1 n+2 2n
1 1
Em seguida, agrupe os termos da forma + e analise o numerador da
n + i 2n − i + 1
fração obtida.
Referências
[1] S. B. Feitosa, B. Holanda, Y. Lima and C. T. Magalhães, Treinamento Cone Sul 2008.
Fortaleza, Ed. Realce, 2010.
[3] D. Fomin, S. Genkin and I. Itenberg, Mathematical Circles, Mathematical Words, Vol.
7, American Mathematical Society, Boston, MA, 1966.
7n + 2a
Problema 2. Encontre todos os valores de a tais que as frações da forma
n+5
sejam todas irredutı́veis.
Solução. Devemos ter, para todo n inteiro,
1 = mdc(7n + 2a, n + 5)
= mdc(7n + 2a − 7(n + 5), n + 5)
= mdc(2a − 35, n + 5).
Suponha que 2a − 35 é diferente de 1 e de −1. Então tomando n = |2a − 35| − 5 teremos mdc
igual a |2a − 35| , isto é, diferente de 1.
Logo, para que mdc(7n + 2a, n + 5) = 1 devemos ter 2a − 35 = ±1. Dessa forma, a = 18 ou
a = 17.
Solução. Vamos primeiramente descobrir o resto de 3600 na divisão por 7. Veja que 33 = 27
deixa resto 6 por 7. Logo, 36 deixa mesmo resto que 62 = 36, isto é, deixa resto 1 por 7.
Dessa forma, 3600 = (36 )100 deixa mesmo resto que 1100 = 1 na divisão por 7. Concluı́mos que
mdc(3600 , 7) = mdc(1, 7) = 1.
mdc(fn , fn 1) = mdc(fn 1 + fn 2 , fn 1 )
= mdc(fn 1 + fn 2 − fn 1 , fn 1 )
= mdc(fn 2 , fn 1 )
Proseguindo desta maneira, encontramos que o mdc inicial é igual a mdc(fn 2 , fn 3 ),
mdc(fn 3 , fn 4 ), . . .. De forma que mdc(fn , fn 1 ) é constante para todo n natural. Con-
sequentemente, este valor é sempre igual a mdc(f1 , f2 ) = mdc(1, 1) = 1.
Problema 5. Para quais inteiros positivos k ocorre mdc(n! + k, 3n) = 3 para todo n > 3?
(n − 1)!
Solução. Se n > 3 então q = é inteiro. Sendo assim temos que mdc(n! + k, 3n) =
3
mdc(n! + k − 3nq, 3n) = mdc(k, 3n) = 3. Devemos ter, então, k = 3t, t ∈ Z. Logo, deve
ocorrer mdc(t, n) = 1 para todo n. Como k é natural, t = 1 e k = 3. k só pode assumir um
valor natural.
Solução. Note que mdc(n, 2015 + n) = mdc(n, 2015 + n − n) = mdc(2015, n). Tomando
n = 2015 temos o mdc máximo e igual a 2015.
Solução. Pelo algoritmo de Euclides encontramos mdc(966, 462) = 42. Pelo teorema de
Bezout, existem x0 e y 0 tais que 42 = 462x0 + 966y 0 . Portanto, se 42 divide n, digamos
n = 42k, então existem x = k · x0 e y = k · y 0 tais que n = 42k = 462x + 966y. Além disso,
se n pode ser escrito dessa forma então, claramente, é múltiplo de 42. Concluı́mos que n pode
ser escrito na forma 462x + 966y se, e só se, for múltiplo de 42. Existem 2 múltiplode 42 entre
1 e 100. Sendo assim, a resposta é 2.
2
Como 2n + 1 é ı́mpar, multiplicar 122 + n2 por 2 não altera o mdc. Logo,
Novamente, como 2n + 1 é ı́mpar, multiplicar 244 − n por 2 não afetará o mdc. Dai,
Portanto, o maior valor para o mdc será 489, quando 2n + 1 for múltiplo de 489.
Problema 10. Qual é o menor valor positivo de N , tal que existem inteiros x e y satisfazendo
2013x + 3102y = N
.
Solução. Usando o algoritmo de Euclides:
O próximo teorema nos diz que os primos são as ”peças”fundamentais dos números inteiros:
Teorema 2. Todo inteiro n, maior que 1, pode ser expresso como o produto de número
primo.
Demonstração. Suponha, por absurdo, que exita apenas uma quantidade finita de primos:
p1 , p2 , . . . , pn . Considere o número X = p1 p1 . . . pn + 1. Pelo teorema anterior, esse número
deve ser o produto de alguns elementos do conjunto de todos os números primos. Entre-
tanto, nenhum dos primos pi divide X.
Exemplo 4. Existe um bloco de 1000 inteiros consecutivos não contendo nenhum primo?
Sim. Um exemplo é o conjunto 1001! + 2, 1001! + 3, . . . , 1001! + 1001. Veja i | 1001! + i para
todo i = 2, 3, . . . , 1001.
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 4 - Samuel Feitosa
Exemplo 5. (Torneio das Cidades) Existe um bloco de 1000 inteiros consecutivos contendo
apenas um primo?
Para cada bloco de 1000 números consecutivos, contemos sua quantidade de números pri-
mos. Por exemplo, no bloco 1, 2, 3, . . . , 1000, temos 168 números primos (mas só usaremos
o fato de que existem mais de dois primos nesse bloco). Comparando os blocos consecuti-
vos k + 1, k + 2, . . . , k + 1000 e k + 2, k + 3, . . . , k + 1001, ou o número de números primos
aumenta em uma unidade, ou fica constante ou diminui em uma unidade. Analisando to-
dos os blocos consecutivos desde 1, 2, . . . , 1000 até 1001! + 2, 1001! + 3, . . . , 1001! + 1001,
o número de números primos deve ser igual à 1 em algum deles. Para ver isso, usare-
mos um argumento de continuidade discreta: Começando com o número 168 e realizando
alterações de no máximo uma unidade na quantidade de primos em cada bloco, para che-
garmos no número 0, necessariamente deveremos passar pelo número 1 em algum momento.
2
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 4 - Samuel Feitosa
Então, mdc(m, n) = pγ11 pγ22 . . . pγkk e mmc(m, n) = pθ11 pθ22 . . . pθkk , onde γi é o menor dentre
{αi , βi } e θi é o maior dentre {αi , βi }.
Proposição 11. Se a e b são inteiros positivos, mostre que mmc(a, b)mdc(a, b) = ab.
max{x, y} + min{x, y} = x + y.
Exemplo 12. (Torneio das Cidades 1998) É possı́vel que mmc(a, b) = mmc(a + c, b + c)
para alguma conjunto {a, b, c} de inteiros positivos?
Não. Suponha que a + c e b + c possuem algum divisor primo p. Como p | mmc(a + c, b + c),
caso existam tais inteiros, devemos ter que p | mmc(a, b). Assim, usando que pelo menos
um dentre a e b é divisı́vel por p podemos concluir que c também é divisı́vel por p. Então,
podemos cancelar o fator p:
! " ! "
a b mmc(a, b) mmc(a + c, b + c) a+c b+c
mmc , = = = mmc , .
p p p p p p
Efetuando alguns cancelamentos, podemos supor então que a+c e b+c não possuem fatores
primos em comum. Obtivemos um absurdo pois:
Exemplo 13. (OCM 2005) Determinar os inteiros n > 2 que são divisı́veis por todos os
primos menores que n.
Como mdc(n, n − 1) = 1, se n − 1 possui algum fator primo, ele não dividirá n. Assim,
n − 1 < 2. Consequentemente não existe tal inteiro.
Exemplo 14. Mostre que n4 + n2 + 1 é composto para n >1.
Veja que n4 + n2 + 1 = n4 + 2n2 + 1 − n2 = (n2 + 1)2 − n2 = (n2 + n + 1)(n2 − n + 1).
Para n > 1, n2 − n + 1 = n(n − 1) + 1 > 1 e assim n4 + n2 + 1 é o produto de dois inteiros
maiores que 1.
Exemplo 15. Mostre que n4 + 4n é composto para todo n > 1.
Se n é par, certamente o número em questão é divisı́vel por 4. Para o caso em que n é
impar, iremos usar a fatoração:
a4 + 4b4 = a4 + 4a2 b2 + 4b4 − 4a2 b2 = (a2 + 2b2 ) − 4b2 b2 = (a2 − 2ab + 2b2 )(a2 + 2ab + 2b2 ).
3
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 4 - Samuel Feitosa
Sendo assim, se n possuı́sse algum divisor primo ı́mpar p com n = pb, poderı́amos escrever:
2n + 1 = (a + 1)(an−1 − an−2 + . . . − a + 1), onde a = 2b . Como an−1 − an−2 + . . . − a + 1 > 1,
o número 2n + 1 não seria primo.
Exemplo 17. Dados que p, p + 10 e p + 14 são números primos, encontre p.
Vamos analisar os possı́veis restos na divisão por 3 de p. Se p deixa resto 1, então p + 14
é um múltiplo de 3 maior que 3 e consequentemente não poderá ser um número primo. Se
o resto é 2, então p + 10 é um múltiplo de 3 maior que 3 e também não poderá ser um
número primo. Assim, o resto de p por 3 é 0 e consequentemente p = 3.
n
Exemplo 18. (Áustria-Polônia) Dados naturais n e a > 3 ı́mpar, mostre que a2 − 1 tem
pelo menos n + 1 divisores primos distintos.
Usando a fatoração da diferença de quadrados, temos que:
k k−1 k−2
a2 − 1 = (a2 + 1)(a2 + 1) . . . (a + 1)(a − 1).
m k
Assim, a2 + 1 | a2 − 1 se k > m. Como a é impar, podemos concluir que:
k m k m m
mdc(a2 + 1, a2 + 1) = mdc(a2 − 1 + 2, a2 + 1) = mdc(2, a2 + 1) = 2.
an+1 − an > c.
4
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 4 - Samuel Feitosa
Suponha, por absurdo, que exista c > 0 tal que an+1 − an ≤ c, ∀ n ∈ N. Isso significa que
as diferenças entre os termos consecutivos de (an )n≥1 pertencem ao conjunto {1, 2, . . . , c},
logo são finitas. Sejam d1 , d2 , . . . , dr essas diferenças. Seja αi o maior expoente de pi que
aparece na fatoração de todos os dj .
Considere então o número M = pα1 1 +1 pα2 2 +1 · · · pαk k +1 . É claro que M pertence à seqüência,
ou seja, M = an , para algum n. Vejamos quem será an+1 . Por hipótese, existe i tal que
an+1 − an = di . Como an+1 > an , existe um primo pj que divide an+1 com expoente maior
ou igual a αj + 1. Caso contrário,
Logo, o conjunto de todas as diferenças não pode ser finito e, portanto, dado qualquer
c > 0, existe um natural n tal que an+1 − an > c.
Problemas Propostos
5
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 4 - Samuel Feitosa
Problema 32. Suponha que n >1. Mostre que a soma dos inteiros dos inteiros positivos
não excedendo n divide o produto dos inteiros positivos não excedendo n se, e somente se,
n é composto.
Exemplo 33. (Rússia 1995) Encontre todos os primos p para os quais p2 + 11 tenha exata-
mente seis divisores distintos, incluindo 1 e p2 + 11.
Problema 34. (Irlanda 2002 ) Encontre todas as soluções inteiras positivas de p(p + 3) +
q(q + 3) = n(n + 3), onde p, q são primos.
Exemplo 35. Prove que qualquer quadrado perfeito positivo tem mais divisores que deixam
resto 1 na divisão por 3 do que divisores que deixam resto 2 na divisão por 3.
Dicas e Soluções
Assim, se k > m,
k m k m m
mdc(22 + 1, 22 + 1) = mdc(22 − 1 + 2, 22 + 1) = mdc(2, 22 + 1) = 1,
produzindo que quaisquer dois números de Fermat distintos são primos entre si e isso
necessariamente implica que o conjunto de seus divisores primos é infinito.
30. Dado 1 < n < 1998, se ele não for primo, usando o exercı́cio anterior, ele tem que
ter um fator primo menor que 1998, ou seja, um fator primo menor que 45. Como só
existem 14 primos menores que 45, e são 15 números, um deles será primo.
6
31. Escreva n = ab e analise as aparições de a e b no produto (n − 1) · (n − 2) . . . 2 · 1.
34. Seja
n = 3γ · pα1 1 · · · pαnn · q1β1 · · · qm
βm
Referências
[1] E. Carneiro, O. Campos and F. Paiva, Olimpı́adas Cearenses de Matemática 1981-2005
(Nı́veis Júnior e Senior), Ed. Realce, 2005.
[2] S. B. Feitosa, B. Holanda, Y. Lima and C. T. Magalhães, Treinamento Cone Sul 2008.
Fortaleza, Ed. Realce, 2010.
[4] D. Fomin, S. Genkin and I. Itenberg, Mathematical Circles, Mathematical Words, Vol.
7, American Mathematical Society, Boston, MA, 1966.
Problema 1. Um primo p pode ser expresso como a diferença de quadrados de dois inteiros
positivos. Encontre o resto da divisão de p2 + 138 por 4.
Problema 2. Encontre todos os primos p tais que p = 3m 3n , onde m, n são inteiros não
negativos.
Solução. Devemos ter n < m. Sendo assim, p = 3m 3n = 3n (3m−n 1). Como p é primo
e 3m−n 1 6= 1, devemos ter 3m−n 1 = p e 3n = 1. Concluı́mos que n = 0 e p = 3m 1 é
par. Dessa forma, p é igual ao único primo par, 2.
Solução. A soma dos três números é um número par, então plo menos um deles é par. O
único número primo par é 2. Só 3n 4 e 5n 3 podem ser pares. Resolvendo as equações
3n 4 = 2 e 5n 3 = 2 encontramos n = 2 e n = 1, respectivamente. É trivial conferir que
n = 2 torna todos os três números primos.
Solução. Se p não é múltiplo de 3 então p2 deixa resto 1 na divisão por 3, de forma que p2 + 8
é múltiplo de 3 e não é primo. Logo, p deve ser múltiplo de 3. Como é primo, p = 3. Daı́,
p3 + 8p + 2 = 53 que é primo.
Problema 7. Seja p um primo ı́mpar. Encontre os pares de inteiros positivos (x, y) tais que
x2 = p + y 2 .
1! + 2! + 3! + 4! + . . . + n! = 9 + 4! + . . . + n!.
Note que todos os termos são divisı́veis por 3, logo para n 4 não temos solução. Sendo
assim, o único inteiro n que satisfaz essa condição é n = 3.
Problema 9. Mostre que não existe nenhuma progressão aritmética infinita composta somente
de números primos.
Solução. Suponha que existe uma progressão deste tipo. Seja p1 o termo inicial e r a razão da
sequência. Então o termo geral da sequência é pn = p1 + (n 1)r. Tomando n = p1 + 1 temos
pp1 +1 = p1 + [(p1 + 1) 1]r = p1 (1 + r), um número composto. Chegamos a um absurdo.
Logo, não existe nenhuma P.A. infinita composta somente de primos.