Obra: Apostila OBMEP 1
Matéria: Matemática
Nível: fundamental
da adição, mostre que os 12 modos de somar três números a, b e c:
(a + b) +c, a + (b + c), (a + c) +b, a + (c + b), (b + a) +c, b + (a + c),
(b + c) + a, b + (c + a), c + (b + a), (c + a) + b, c + (a + b), (c + b) + a,
dão o mesmo resultado.
Adição e Ordem. Há uma relação de compatibilidade entre a ordem
Note que o único múltiplo de 0 é apenas o 0. Todos os números
são múltiplos de 1 e de si próprios. Note também que, pela definição
de múltiplo, um múltiplo não nulo, isto é diferente de zero, de um
número a > 0 é sempre maior ou igual do que a.
Assim, temos a seguinte propriedade importante:
Se a × b = 0, então a = 0 ou b = 0.

“principal”
2010/4/19
page 15
Estilo
OBMEP
▲ SEC. 2.5: O CRIVO DE ERATÓSTENES 35
n2 n3 ̸ 4 n5 ̸ 6 n7 ̸ 8 ̸ 9 ̸ 10 n11 ̸ 12
n13 ̸ 14 ̸ 15 ̸ 16 n17 ̸ 18 n19 ̸ 20 ̸ 21 ̸ 22 n23 ̸ 24
̸ 25 ̸ 26 ̸ 27 ̸ 28 n29 ̸ 30 n31 ̸ 32 ̸ 33 ̸ 34 ̸ 35 ̸ 36
n37 ̸ 38 ̸ 39 ̸ 40 n41 ̸ 42 n43 ̸ 44 ̸ 45 ̸ 46 n47 ̸ 48
̸ 49 ̸ 50 ̸ 51 ̸ 52 n53 ̸ 54 ̸ 55 ̸ 56 ̸ 57 ̸ 58 n59 ̸ 60
n61 ̸ 62 ̸ 63 ̸ 64 ̸ 65 ̸ 66 n67 ̸ 68 ̸ 69 ̸ 70 n71 ̸ 72
n73 ̸ 74 ̸ 75 ̸ 76 ̸ 77 ̸ 78 n79 ̸ 80 ̸ 81 ̸ 82 n83 ̸ 84
̸ 85 ̸ 86 ̸ 87 ̸ 88 n89 ̸ 90 ̸ 91 ̸ 92 ̸ 93 ̸ 94 ̸ 95 ̸ 96
n97 ̸ 98 ̸ 99 ̸100 
101 ̸102 
103 ̸104 ̸105 ̸106 
107 ̸108
109 ̸110 ̸111 ̸112 
113 ̸114 ̸115 ̸116 ̸117 ̸118 ̸119 ̸120
̸121 ̸122 ̸123 ̸124 ̸125 ̸126 
127 ̸128 ̸129 ̸130 
131 ̸132
̸133 ̸134 ̸135 ̸136 
137 ̸138 
139 ̸140 ̸141 ̸142 ̸143 ̸144
̸145 ̸146 ̸147 ̸148 
149 ̸150 
151 ̸152 ̸153 ̸154 ̸155 ̸156
157 ̸158 ̸159 ̸160 ̸161 ̸162 
163 ̸164 ̸165 ̸166 
167 ̸168
̸169 ̸170 ̸171 ̸172 
173 ̸174 ̸175 ̸176 ̸177 ̸178 
179 ̸180
181 ̸182 ̸183 ̸184 ̸185 ̸186 ̸187 ̸188 ̸189 ̸190 
191 ̸192
193 ̸194 ̸195 ̸196 
197 ̸198 
199 ̸200 ̸201 ̸202 ̸203 ̸204
̸205 ̸206 ̸207 ̸208 ̸209 ̸210 
211 ̸212 ̸213 ̸214 ̸215 ̸216
̸217 ̸218 ̸219 ̸220 ̸221 ̸222 
223 ̸224 ̸225 ̸226 
227 ̸228
229 ̸230 ̸231 ̸232 
233 ̸234 ̸235 ̸236 ̸237 ̸238 
239 ̸240
241 ̸242 ̸243 ̸244 ̸245 ̸246 ̸247 ̸248 ̸249 ̸250
comum de a e b.
(iv) Se m e m′ são múltiplos comuns de a e b, então m + m′ e m − m′
são também múltiplos comuns de a e b.
(v) Se m e m′ são múltiplos comuns de a e b, então e × m + f × m′ é
múltiplo comum de a e b, quaisquer que sejam os inteiros e e f (note
que (iv) é um caso particular da presente propriedade).
(vi) Se m + m′ ou m − m′ é múltiplo comum de a e b e m é múltiplo
Por exemplo, dado um número n = nr . . . n1n0 na sua represen-
tação decimal, temos o resultado:
n é divisível por 2 (ou seja múltiplo de 2) se e somente se n0 é um
número par.
1Isto absolutamen te não quer dizer que podemos dividir zero por zero, pois
como 0 = c × 0 para todo c, o “quociente” de 0 por 0 poderia ser qualquer número,
Como exemplo de aplicação, vejamos como isto vai permitir o
cálculo de mdc (3 264, 1 234):
mdc(3 264, 1 234) = mdc(1 234, 3 264 − 1 234) =
mdc(1 234, 2 030) = mdc(1 234, 2 030 − 1 234) =
mdc(1 234, 796) = mdc(796, 1 234 − 796) =
mdc(796, 438) = mdc(796 − 438, 438) =
mdc(358, 438) = mdc(358, 438 − 358) =
mdc(358, 80) = mdc(358 − 80, 80) =
mdc(278, 80) = mdc(198, 80) =
mdc(118, 80) = mdc(38, 80) =
mdc(38, 42) = mdc(38, 4) =
mdc(34, 4) = mdc(30, 4) =
mdc(26, 4) = mdc(22, 4) =
mdc(18, 4) = mdc(14, 4) =
mdc(10, 4) = mdc(6, 4) = 2

“principal”
2010/4/19
page 52
úmeros é múltiplo de 3, a saber, a.
2) Suponha que a deixe resto 1 quando dividido por 3, ou seja,
a = 3q + 1. Logo, a + 1 = 3q + 2 e a + 2 = 3q + 3 = 3(q + 1).
Assim, um e apenas um dos três números é múltiplo de 3, a saber,
a + 2.
3) Suponha que a deixe resto 2 quando dividido por 3, ou seja,
a = 3q +2. Logo, a+1 = 3q +3 = 3( q+1) e a+2 = 3q +4 = 3( q+1)+1.
Assim, um e apenas um dos três números é múltiplo de 3, a saber,
a + 1.
Estilo
OBMEP
▲ SEC. 3.8: ALGORITMO DO MDC DE EUCLIDES 69
18 =
162 − 48 × 3
48 = 372 − 162 × 2
Donde,
n6 = 18 − 12 × 1 = 18 − (48 − 18 × 2)
= 18 × 3 − 48
= (162 − 48 × 3) × 3 − 48
= 162 × 3 − 48 × 10
= 162 − (372 − 162 × 2) × 10
= 162 × 23 − 372 × 10.
Assim, podemos escrever:
n6 = mdc(372, 162) = 162 × 23 + 372 × (−10).
Por exemplo, os divisores positivos de 60 = 2 2 × 3 × 5 são:
20 × 30 × 50 = 1, 20 × 31 × 50 = 3, 20 × 30 × 51 = 5
20 × 31 × 51 = 15, 21 × 30 × 50 = 2, 21 × 31 × 50 = 6,
21 × 30 × 51 = 10, 21 × 31 × 51 = 30, 22 × 30 × 50 = 4,
22 × 31 × 50 = 12, 22 × 30 × 51 = 20, 22 × 31 × 51 = 60.
O número de divisores de n = pa1
1 × · · · × par
r é exatamente o
número de números inteiros b1, . . . , br satisfazendo às desigualdades

“principal”
2010/4/19
page 74
Se a equação ax + by = c admite uma solução, então o número
d = mdc(a, b) divide c e, portanto, temos que a = a′× d, b = b′× d e
c = c′× d, onde mdc (a′, b′) = 1 (Problema 3.17).
Assim, é imediato verificar que x0, y0 é uma solução da equação
ax + by = c se, e somente se, é solução da equação a′x + b′y = c′, onde
por x = 0 + 5 t e y = 10 − 3t. Se estivermos à procura de soluções
não negativas então deveríamos ter 10 − 3t ≥ 0, o que implica que
t = 0, 1, 2 ou 3. Assim, o Problema 3.54 admite as seguintes soluções:
(a) 10 selos de 5 reais.
(b) 5 selos de 3 reais e 7 selos de 5 reais.
(c) 10 selos de 3 reais e 4 selos de 5 reais.
(d) 15 selos de 3 reais e um selo de 5 reais.
O único verdadeiro trabalho que se tem para resolver uma equação
Observe inicialmente que
10 ≡ 4 mod 6,
102 ≡ 42 ≡ 4 mod 6,
103 ≡ 102 × 10 ≡ 4 × 4 ≡ 4 mod 6,
104 ≡ 103 × 10 ≡ 4 × 4 ≡ 4 mod 6.
Você tem ainda alguma dúvida de que 10i ≡ 4 mod 6, para todo
número natural i > 0?
Assim, se um número natural n é escrito no sistema decimal como
nr . . . n1n0, temos que
n = n0 +10n 1 +10 2n2 +· · ·+10 rnr ≡ n0 +4n 1 +4n 2 +· · ·+4n r mod 6.
Escrevendo um número n na representação decimal como
nr . . . n2n1n0, temos, módulo 7, 11 ou 13, que
n = n2n1n0 + n5n4n3 × 103 + n8n7n6 × 106 + · · ·
≡ n 2n1n0 − n 5n4n3 + n8n7n6 − · · · .
Assim, o resto da divisão de n por 7,11 ou 13 é igual ao resto da 
divisão de n2n1n0 − n5n4n3 + n8n7n6 − · · · por 7, 11 ou 13, respecti-
tervalo [1, 174]?
(b) Quantos múltiplos de 7 existem em cada um dos intervalos
[70, 342] e [72, 342]?
S-3.3 Dados 0 < a ≤ n < m, mostre que no intervalo [1, n] existem
q múltiplos de a, onde q é o quociente da divisão de n por q. Quantos
são os múltiplos de a no intervalo [n, m]? (Na última situação, divida
a análise em dois casos: n múltiplo de a e o contrário.)
S-3.4 Mostre que dados m inteiros consecutivos um, e apenas um,
Estilo
OBMEP
102 ■ CAP. 5: PROBLEMAS SUPLEMENTARES
(b) Mostre que se n é ímpar, então n(n2 − 1) é múltiplo de 24.
(c) Mostre que se n não é múltiplo de 2 nem de 3, então n2 − 1 é
múltiplo de 24. Mostre que o mesmo vale para n2 + 23.
S-3.8
(a) Mostre que se um número a não é divisível por 3, então o resto
da divisão de a2 por 3 é 1.
(b) A partir desse dado, mostre que se um inteiro da forma a2 + b2
é múltiplo de 3, então a e b são ambos múltiplos de 3.
S-3.9 Mostre que se n > 1, então o número n4 + 4 é composto.
S-3.10
(a) Mostre que o único número primo da forma n3 + 1 é 2.
(b) Mostre que o único número primo da forma n3 − 1 é 7.
S-3.11* Mostre que, dado n > 2, entre n e 2 × 3 × · · · × n existe
da forma 4n2 + 1?Teste o seu resultado para números da forma
an2 + bn + c, onde a, b, c ∈ Z, com a e b não simultaneamente
nulos.
(e) Mostre que existem infinitos múltiplos de 7 da forma 8n2+3n+4.
S-3.13
(a) Sejam dados os dois números a = 10c + r e b = c − 2r, com
c, r ∈ Z. Mostre que a é múltiplo de 7 se, e somente se, b é
múltiplo de 7.
(b) Deduza o seguinte critério de multiplicidade de 7:
O número n = ar · · ·a1a0 é múltiplo de 7 se, e somente se, o
número ar · · ·a1 − 2a0 é múltiplo de 7.
(c) Utilize repetidas vezes o critério acima para verificar se 2 368 é
ou não múltiplo de 7.
Um número inteiro n é dito um quadrado se existe a ∈ Z tal que
n = a2. Dizemos que n é uma potência m-ésima quando n = am.
S-3.14
(a) Mostre que o algarismo das unidades de um quadrado só pode
Estilo
OBMEP
104 ■ CAP. 5: PROBLEMAS SUPLEMENTARES
(b) Mostre que nenhum dos números 22, 222, 2 222, . . ., ou
33, 333, 3 333, . . ., ou 77, 777, 7 777, . . ., ou ainda
88, 888, 8 888, . . . pode ser um quadrado.
S-3.15
(a) Mostre que todo quadrado ímpar é da forma 4n + 1.
(b) Mostre que nenhum número na sequência 11, 111, 1 111, 11 111
etc., é um quadrado.
(c) Mostre que nenhum número na sequência 44, 444, 4 444, 44 444
etc., é um quadrado.
(d) Mostre que nenhum número na sequência 99, 999, 9 999, 99 999
etc., é um quadrado.
(e) Mostre que nenhum número na sequência 55, 555, 5 555, 55 555
etc., é um quadrado.
S-3.16
(a) Mostre que nenhum número da forma 4n + 2 é um quadrado.
(b) Mostre que nenhum dos números 66, 666, 6 666, . . . é um
Diremos que m ̸= 0 é livre de cubos quando não houver nenhum
número a ̸= ±1 tal que a3 divide m.
S-3.23
(a) Mostre que m é livre de quadrados se, e somente se, a decom-
posição de m em fatores primos é da forma ±p 1 · · ·pr, onde
p1, . . . , pr são primos distintos.
(b) Mostre que m é livre de cubos se, e somente se, a decomposição
Estilo
OBMEP
 
S-3.26 Mostre que
se n é composto, então n divide o produto
1 × 2 × 3 × · · · × (n − 1).
S-3.27 Dados dois inteiros a e b distintos, mostre que existem infini-
tos números n para os quais mdc (a + n, b + n) = 1.
S-3.28 Calcule mdc (n + 1, n2 + 1), para n ∈ Z.
S-3.29 Mostre que se a e b são dois números naturais tais que
mdc(a, b) = mmc(a, b), então a = b.
S-3.30 Resolva o seguinte sistema de equações:
mdc(x, y) = 6
mmc(x, y) = 60
S-3.31 Observe que mdc(x, y) divide mmc(x, y), quaisquer que sejam
x, y ∈ Z, não nulos.
forma 2p − 1, onde p é primo são chamados primos de Mersenne .
S-3.34
(a) Mostre que todo cubo que é também um quadrado é da forma
5n, 5n+1 ou 5n+4 (ou seja, nunca é da forma 5n+2 ou 5n+3).
(b) Mostre que todo cubo que é também um quadrado é da forma
7n, 7n + 1.
S-3.35
(a) Mostre que todo primo maior do que 3 é da forma 3n + 1 ou
3n + 2.

“principal”
2010/4/19
page 109
todo p primo p ≤ 7.
(b) Verifique que se p não divide a, com p nas condições de (a),
então p divide ap− 1 − 1, para todo a ∈ Z.
(c) Ache o resto da divisão por 7 do número 16 + 26 + 36 + · · ·+ 156.
(d) Mostre que se a e b são primos com 7, então b6 − a6 é múltiplo
de 7. Em particular, 236 − 186 é múltiplo de 7.
Estilo
OBMEP
112 ■ CAP. 5: PROBLEMAS SUPLEMENTARES
(c) Generalize.
S-3.48 Sejam a e b inteiros e n um número natural. Mostre que
se a × b é uma potência n-ésima e mdc (a, b) = 1, então a e b são
potências n-ésimas.
S-3.49 (Esse é um problema proposto no século 16) Um total de
41 pessoas entre homens, mulheres e crianças foram a um banquete
cavalos e quantos bois foram comprados?
S-3.52
(a) Dados a e b inteiros fixados, quando é que os números da forma
ax + by, com x, y ∈ Z representam todos os inteiros?
(b) Quais são os números representados por 2x + 3y?
(c) Quais são os números representados por 6x + 9y?

“principal”
2010/4/19
page 113
certo país, as cédulas são de $4 e $7. Quais das afir-
mações a seguir são verdadeiras? Com elas é possível pagar, sem tro-
co, qualquer quantia inteira
(a) a partir de $11, inclusive.
(b) a partir de $18, inclusive.
(c) ímpar, a partir de $7, inclusive.
(d) que seja $1 maior do que um múltiplo de $3.
(e) que seja $1 menor do que um múltiplo de $3.
S-3.54 Em um quintal onde são criados coelhos e galinhas contaram-
se 400 pés. Quantas são as galinhas e quantos são os coelhos, sabendo
admite nenhuma solução em x, y e z, com x e y ímpares.
S-3.56 Mostre que a equação x2 + y2 = z2 não admite nenhuma so-
lução em x, y e z, com x e y ambos primos com 3.
S-3.57 Mostre que se m e n são números inteiros, então x = 2mn,
y = m2 − n2 e z = m2 + n2 são soluções da equação pitagórica
x2 + y2 = z2.

“principal”
2010/4/19
page 114
conclua que
a soma de n inteiros consecutivos quando dividida
por n deixa resto zero se n é ímpar e metade de n, se n é par.
(c) Ache os restos da divisão de 2 356 + 2 357 + 2 358 + 2 359 + 2 360
por 5 e de 32 141+32 142+ · · ·+32 149+32 150+32 151+32 152
por 12.
S-4.2 Mostre que, para todo n ∈ N,
(a) 7 divide 32n+1 + 2n+2.
(b) 9 divide 10n + 3 × 4n+2 + 5.
(c) 24 divide 2 × 7n + 3 × 5n − 5.
(d) 35 divide 36n − 26n.
(e) 64 divide 72n + 16n − 1.

“principal”
2010/4/19
page 115
Estilo
OBMEP
 
S-4.3 Sabendo
que 74 = 2 401, ache os últimos dois dígitos de 799 999.
S-4.4 Ache o resto da divisão de 21 000 000 por 77.
S-4.5 Mostre que 1436 + 9110 + 7712 − 1 é múltiplo de 1 001.
S-4.6 Mostre que 2 2225 555 + 5 5552 222 é múltiplo de 7.
S-4.7 Mostre que 19 nunca divide um número da forma 4n2 + 4.
S-4.8 Quais são os dois últimos algarismos na representação no sis-
tema decimal do número 3400? E do número 2400?
S-4.9 Qual é o algarismo da unidade na representação decimal do
número 999
? E do número 777
S-4.10 Ache os algarismos das centenas e das unidades na represen-
tação decimal dos números 7999 999 e 771 000
S-4.11 Ache o resto da divisão
(a) de 560 por 26. (b) de 3100 por 34 (c) de 21 000 000 por 77.
S-4.12 Determine os restos da divisão por 4 dos números:
(a) 1 + 2 + 2 2 + 23 + · · · + 2100 (b) 15 + 25 + 35 + · · · + 205.
S-4.13 Mostre que a congruência x2 + 1 ≡ 0 mod 7 não possui so-
luções. Conclua que a equação x2 − 6x − 77 = 7y não admite soluções
Estilo
OBMEP
116 ■ CAP. 5: PROBLEMAS SUPLEMENTARES
S-4.15 Mostre que se um número da forma 7n − 5 é múltiplo de 5,
então o número 12n2 + 19n − 19 é múltiplo de 25.
S-4.16 Mostre que se um número da forma 2n + 1 é múltiplo de 3,
então o número 28n2 − 13n − 5 é múltiplo de 9.
S-4.17 Mostre que valem as seguintes congruências:
(a) n13 ≡ n mod p, para p = 2, 3, 5, 7 e 13, e para todo n ∈ Z.
(b) Se mdc (n, p) = 1, mostre que n12 ≡ 1 mod p, para p = 2, 3, 5, 7
e 13.
que o número de múltiplos de 8 é 1 000 − 4 + 1 = 997.
(b) Considerando a sequência 1 606 × 2, . . . ,3 160 × 2, segue que o
número de números pares é 3 160 − 1 606 + 1 = 1 555.
(c) 15 e 18 dúzias, respectivamente.
(d) 40 e 51 semanas, respectivamente.
1.23 28, 56, 84, . . .

“principal”
2010/4/19
page 119
seria um divisor comum de a e b maior do que d, absurdo.
3.18 43 = 3 × 14 + 1, 43 = 5 × 8 + 3, 233 = 4 × 58 + 1,
1 453 = 10 × 145 + 3, 1 453 = 100 × 14 + 53, 1 453 = 1 000 × 1 + 453
e 1 453 = 10 000 × 0 + 1 453.
3.20 −43 = 3( −15) + 2, −43 = 5( −9) + 2 −233 = 4( −59) + 3,
−1 453 = 10 × (−146) + 7, −1 453 = 100( −15) + 47, −1 453 =
1 000(−2) + 547, −1 453 = 10 000( −1) + 8 547.