MA14 - Aritmética

Lista 1

Unidades 1 e 2

Abramo Hefez

PROFMAT - SBM

05 a 11 de agosto 2013
Unidade 1
1. Mostre, por indução matemática, que, para todo n ∈ N ∪ {0},
a) 8|32n + 7 b) 9|10n + 3.4n+2 + 5
2. Mostre que, para todo n ∈ N ∪ {0},
a) 19|32n+1 + 44n+2 b) 17|102n+1 + 72n+1 c) 14|34n+2 + 52n+1
3. Sejam a, b ∈ Z.
a) Se a 6= b, mostre que, para todo n ∈ N, n > 2,
an − b n
= an−1 + an−2 b + · · · + ab n−2 + b n−1 .
a−b
b) Se a + b 6= 0, mostre que, para todo n ∈ N,
a2n+1 + b 2n+1
= a2n − a2n−1 b + · · · − ab 2n−1 + b 2n .
a+b
c) Se a + b 6= 0, mostre que para todo n ∈ N,
a2n − b 2n
= a2n−1 − a2n−2 b + · · · + ab 2n−2 − b 2n−1 .
a+b
PROFMAT - SBM Aritmética - Lista 1 - Unidades 1 e 2 slide 2/5
Unidade 1 - Continuação

4. Para quais valores de a ∈ N

a) a − 2|a3 + 4?
b) a + 3|a3 − 3?
c) a + 2|a4 + 2?
d) a + 2|a4 + 2a3 + a2 + 1?

5. Mostre que, para todos a, m, n ∈ Z,

n m
m > n > 0 =⇒ a2 + 1|a2 − 1.

6. Mostre, para todo n ∈ N, que n2 |(n + 1)n − 1.

7. Mostre, para todo a ∈ Z, que

a) 2|a2 − a b) 3|a3 − a c) 5|a5 − a d) 7|a7 − a

PROFMAT - SBM Aritmética - Lista 1 - Unidades 1 e 2 slide 3/5

Unidade 2
1. a) Mostre que um número natural a é par se, e somente se, an é
par, qualquer que seja n ∈ N.
b) Mostre que an ± am é sempre par, quaisquer que sejam
n, m ∈ N.
c) Mostre que, se a e b são ı́mpares, então a2 + b 2 é divisı́vel por 2
mas não divisı́vel por 4.

2. Quais são os números que, quando divididos por 5, deixam

resto igual
a) à metade do quociente? b) ao quociente?
c) ao dobro do quociente? d) ao triplo do quociente?

3. Seja n um número natural. Mostre que um, e apenas um,

número do terno abaixo é divisı́vel por 3.
n, n + 10, n + 23

PROFMAT - SBM Aritmética - Lista 1 - Unidades 1 e 2 slide 4/5

Unidade 2 - Continuação

4. a) Mostre que, se um número a não é divisı́vel por 3, então a2

deixa resto 1 na divisão por 3.
b) A partir desse fato, prove que, se a e b são inteiros tais que 3
divide a2 + b 2 , então a e b são divisı́veis por 3.

5. O resto da divisão do inteiro N por 20 é 8. Qual é o resto da

divisão de N por 5?

6. Ache o menor múltiplo de 5 que deixa resto 2 quando dividido

por 3 e por 4.

PROFMAT - SBM Aritmética - Lista 1 - Unidades 1 e 2 slide 5/5

MA14 - Aritmética
Lista 2

Unidades 3 e 4

Abramo Hefez

PROFMAT - SBM

12 a 18 de agosto 2013
Unidade 3
1. Um certo número de três algarismos na base 10 aumenta de 36
se permutarmos os dois algarismos da direita, e diminui de 270 se
permutarmos os dois algarismos da esquerda. O que acontece ao
número se permutarmos os dois algarismos extremos?
2. Critério de divisibilidade por uma potência de 2 Seja dado
um número a, representado na base 10 por a = an an−1 . . . a0 .
Usando o fato de que 2k |10k , mostre que 2k divide a se, e somente
se, o número ak−1 . . . a1 a0 é divisı́vel por 2k . Em particular, a é
divisı́vel por 2 se, e somente se, a0 é 0, 2, 4, 6 ou 8; também, a é
divisı́vel por 4 se, e somente se, a1 a0 é divisı́vel por 4.
3. Escolha um número abc de três algarismos no sistema decimal,
de modo que os algarismos das centenas a e o das unidades c
difiram de, pelo menos, duas unidades. Considere os números abc
e cba e subtraia o menor do maior, obtendo o número xyz. A
soma de xyz com zyx vale 1 089. Justifique esse fato.

PROFMAT - SBM Aritmética - Lista 2 - Unidades 3 e 4 slide 2/5

Unidade 3 - Continuação

4. Seja dado o número 4 783 na base 10; escreva-o nas seguintes

bases: 2, 7, 12 e 15.

5. O número 3 416 está na base 7; escreva-o nas bases 5 e 12.

6. Um número na base 10 escreve-se 37; em que base

escrever-se-á 52?

7. Considere 73 na base 10; em que base ele escrever-se-á 243?

8. Escreva a tabuada na base 5.

Use-a para calcular [132]5 + [413]5 e [23]5 × [342]5 .

9. Utilize o método do Exemplo 4.10 para calcular 527 × 72.

PROFMAT - SBM Aritmética - Lista 2 - Unidades 3 e 4 slide 3/5

Unidade 3 - Continuação

10. Escreva:
a) O número 2n − 1 na base 2.
bn − 1
b) O número na base b.
b−1

11. Sendo a = [an . . . a1 a0 ]b , mostre que o número

a − (a0 + · · · + an ) é divisı́vel por b − 1.

PROFMAT - SBM Aritmética - Lista 2 - Unidades 3 e 4 slide 4/5

Unidade 4

1. Determine, em cada caso apresentado abaixo, se a posição é

segura ou insegura.
a) || ||
b) ||| || ||
c) || | |
d) | |

2. Determine qual das seguintes situações iniciais no Jogo de Nim

permite ao primeiro jogador traçar uma estratégia vencedora.

a) (12, 14, 15), b) (7, 9, 14), c) (7, 9, 15, 17).

Em tal caso faça uma jogada que lhe será favorável.

PROFMAT - SBM Aritmética - Lista 2 - Unidades 3 e 4 slide 5/5

MA14 - Aritmética
Lista 3

Unidades 5 e 6

Abramo Hefez

PROFMAT - SBM

19 a 25 de agosto 2013
Unidade 5
1. Para cada par de números naturais a e b dados abaixo, ache
(a, b) e determine números inteiros m e n tais que
(a, b) = ma + nb.
a) 637 e 3 887 b) 648 e 1 218 c) 551 e 874
d) 7 325 e 8 485.
2. Seja n ∈ N. Mostre que
a) (n, 2n + 1) = 1;
b) (n + 1, n2 + n + 1) = 1;
c) (2n + 1, 9n + 4) = 1;
d) (n! + 1, (n + 1)! + 1) = 1.
3. Mostre que (a, a2 + na + b)|b, quaisquer que sejam a, b, n ∈ N.
4. Seja dado a ∈ Z \ {−1}.
a) Se m ∈ N, mostre que
 2m 
a −1
, a + 1 = (a + 1, 2m).
a+1
PROFMAT - SBM Aritmética - Lista 3 - Unidades 5 e 6 slide 2/6
Unidade 5 - Continuação
b) Se m ∈ N ∪ {0}, mostre que
 2m+1 
a +1
, a + 1 = (a + 1, 2m + 1).
a+1

5. Calcule
340 − 1 5 510 − 1
   
a) 5
,3 − 1 b) ,6
 340 − 1   50 6 
2 +1 8 2 + 1 10
c) , 2 + 1 d) , 2 + 1 .
28 + 1 210 + 1

6. Sejam a e n números naturais com a 6= 1. Mostre que

(a − 1)2 |an − 1 ⇐⇒ a − 1|n.

PROFMAT - SBM Aritmética - Lista 3 - Unidades 5 e 6 slide 3/6

Unidade 6
1. Sejam a, b, d ∈ Z com d > 0. Mostre que se I (a, b) = dZ,
então d = (a, b).
2. Mostre que
a) se (a, b) = 1, a|c e b|c, então ab|c.
b) se (a, b) = 1, então (ac, b) = (c, b).
c) (ac, b) = 1 se, e somente se, (a, b) = (c, b) = 1.
d) (a, b) = (a, d) = (c, b) = (c, d) = 1 se, e somente se,
(ac, bd) = 1.
e) se (a, b) = 1, então (an , b m ) = 1, para todos n, m ∈ N ∪ {0}.
3. Para todos a, b ∈ Z e todo n ∈ N, mostre que

(an , b n ) = (a, b)n .

4. a) Mostre que, se n é ı́mpar, então n(n2 − 1) é divisı́vel por 24.

b) Mostre que 24 divide n(n2 − 1)(3n + 2) para todo n ∈ N.
PROFMAT - SBM Aritmética - Lista 3 - Unidades 5 e 6 slide 4/6
Unidade 6 - Continuação
5. a) Mostre que n5 − n é divisı́vel por 30.
b) Mostre que n5 e n possuem o mesmo algarismo das unidades.
6. Mostre que se a e b não são ambos nulos, então a|bc se, e
a
somente se, |c.
(a, b)
7. Sejam a e b dois números inteiros com (a, b) = 1.
a) Mostre que (b + a, b − a) é 1 ou 2.
b) Mostre que (a + b, a2 + b 2 ) é 1 ou 2.
8. Mostre que, se a, b, x, y ∈ Z, com ax + by = (a, b), então,
(x, y ) = 1.
9. Sejam a e b dois números naturais com (a, b) = 1. Mostre que
a b
se é par. então é ı́mpar. Vale a recı́proca?
(a, b) (a, b)

PROFMAT - SBM Aritmética - Lista 3 - Unidades 5 e 6 slide 5/6

Unidade 6 - Continução
10. Um prédio possui duas escadarias, uma delas com 780 degraus
e a outra com 700 degraus. Sabendo que os degraus das duas
escadas só estão no mesmo nı́vel quando conduzem a um andar,
descubra quantos andares tem o prédio.
11. Calcule (1 116, 984, 855).
12. Mostre que se três números inteiros são tais que dois deles são
coprimos, então eles são coprimos. Mostre que não vale a
recı́proca; isto é, exiba três números inteiros coprimos mas que não
são dois a dois coprimos.

PROFMAT - SBM Aritmética - Lista 3 - Unidades 5 e 6 slide 6/6

MA14 - Aritmética
Lista 4

Unidades 7 e 8

Abramo Hefez

PROFMAT - SBM
Unidade 7
1. Calcule o mmc dos pares de números:
a) 38, 46; b) 35, 75; c) 235, 740.
2. a) Mostre que [ca, cb] = |c| [a, b].
b) Se m é um múltiplo comum positivo de a e b, mostre que
m m
m = [a, b] ⇐⇒ , = 1.
a b
c) Se r e s não são nulos e ra = sb > 0, mostre que

ra sb
= = [a, b].
(r , s) (r , s)

3. Sejam a, b, c três números naturais. Mostre que

abc = [a, b, c](ab, ac, bc).

PROFMAT - SBM Aritmética - Lista 4 - Unidades 7 e 8 slide 2/7

Unidade 7 - Continuação
4. Seja n ∈ N; calcule [n2 + 1, n + 1].
5. Mostre que
a) (a, b) = [a, b] ⇐⇒ a = b, ∀a, b ∈ N.
b) [an , b n ] = [a, b]n , ∀a, b ∈ Z, ∀n ∈ N.
6. Sejam a, b ∈ Z ambos não nulos. Considere o conjunto

M(a, b) = aZ ∩ bZ
= {x ∈ Z; ∃m, n ∈ Z tais que x = ma e x = nb}.

a) Mostre que [a, b] = min (M(a, b) ∩ N).

b) Mostre que M(a, b) = [a, b]Z.
7. Sejam d, m ∈ N. Mostre que uma condição necessária e
suficiente para que existam a, b ∈ Z tais que (a, b) = d e
[a, b] = m é que d|m.

PROFMAT - SBM Aritmética - Lista 4 - Unidades 7 e 8 slide 3/7

Unidade 7 - Continuação

8. Sejam a1 , . . . , an ∈ Z \ {0}. Mostre que

(ai , aj ) = 1, i 6= j ⇐⇒ [a1 , . . . , an ] = |a1 · · · an |.

9. Mostre que

[a1 , a2 , . . . , an−1 , an ] = [[a1 , a2 , . . . , an−1 ], an ].

PROFMAT - SBM Aritmética - Lista 4 - Unidades 7 e 8 slide 4/7

Unidade 8
1. Resolva em Z as equações:
a) 90X + 28Y = 22 b) 50X − 56Y = 74
c) 40X − 65Y = 135 d) 8X − 13Y = 23
2. Para quais valores de c em N a equação 10X + 14Y = c não
possui soluções em N ∪ {0}?
3. Resolva em N ∪ {0} as equações:
a) 16X + 7Y = 601 b) 30X + 17Y = 201
c) 47X + 29Y = 1288 d) 8X + 13Y = 23
4. Dispondo de R$100, 00, quais são as quantias que se podem
gastar comprando selos de R$5, 00 e de R$7, 00?
5. Determine os múltiplos naturais de 11 e de 9 cuja soma é igual
a
a) 79 b) 80 c) 270
6. Determine o menor inteiro positivo que tem restos 11 e 35
quando dividido, respectivamente, por 37 e 48.
PROFMAT - SBM Aritmética - Lista 4 - Unidades 7 e 8 slide 5/7
Unidade 8 - Continuação
7. Numa criação de coelhos e galinhas, contaram-se 400 pés.
Quantas são as galinhas e quantos são os coelhos, sabendo que a
diferença entre esses dois números é a menor possı́vel?
8. Subindo uma escada de dois em dois degraus, sobra um degrau.
Subindo a mesma escada de três em três degraus, sobram dois
degraus. Determine quantos degraus possui a escada, sabendo que
o seu número é múltiplo de 7 e está compreendido entre 40 e 100.
9. (ENC 2002) Em certo paı́s, as cédulas são de $4 e $7. Com
elas, é possı́vel pagar, sem troco, 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 $5.

PROFMAT - SBM Aritmética - Lista 4 - Unidades 7 e 8 slide 6/7

Unidade 8 - Continuação
10. De quantas maneiras pode-se comprar selos de R$3, 00 e de
R$5, 00 de modo que se gaste R$50, 00?
11. Sejam a1 , a2 , . . . , an , c ∈ Z. Mostre que a equação

a1 X1 + a2 X2 + · · · + an Xn = c

possui soluções inteiras se, e somente se, (a1 , a2 , . . . , an )|c.

PROFMAT - SBM Aritmética - Lista 4 - Unidades 7 e 8 slide 7/7

MA14 - Aritmética
Lista 5

Unidades 10 e 11

Abramo Hefez

PROFMAT - SBM

9 a 15 de setembro 2013
Unidade 10

1. Sejam a, m, n ∈ N, a > 1. Mostre que an − 1|am − 1 se, e

somente se, n|m.
m
2. Sejam n, m ∈ N com n|m e ı́mpar. Se a ∈ N, mostre que
n
(am + 1, an + 1) = an + 1.

3. Sejam a, m, n ∈ N, com m > n. Mostre que

m n n
a2 − 1, a2 + 1 = a2 + 1.

4. Calcule
a) (5202 + 1, 574 + 1)
b) (36497 + 1, 36210 + 1)
c) (3144 − 1, 378 + 1)

PROFMAT - SBM Aritmética - Lista 5 - Unidades 10 e 11 slide 2/4

Unidade 10 - Continuação

5. Seja (Mn )n a sequência definida por Mn = 2n − 1. Mostre que

a) 3|Mn se, e somente se, n é par.
b) 5|Mn se, e somente se, n é múltiplo de 4.
c) 9|Mn se, e somente se, n é múltiplo de 6.

PROFMAT - SBM Aritmética - Lista 5 - Unidades 10 e 11 slide 3/4

Unidade 11

1. Mostre que, se na sequência de Fibonacci existir um termo

divisı́vel por um número natural m, então, existem infinitos tais
termos.
2. Na sequência de Fibonacci, mostre que
a) um é par se, e somente se, m é divisı́vel por 3.
b) um é divisı́vel por 5 se, e somente se, m é divisı́vel por 5.
c) um é divisı́vel por 13 se, e somente se, m é divisı́vel por 7.
3. Na sequência de Fibonacci, mostre que
a) um é divisı́vel por 21 sempre que m for divisı́vel por 8.
b) um é divisı́vel por 8 sempre que m for divisı́vel por 6.

PROFMAT - SBM Aritmética - Lista 5 - Unidades 10 e 11 slide 4/4

MA14 - Aritmética
Lista 6

Unidades 12 e 13

Abramo Hefez

PROFMAT - SBM
Unidade 12
1. Ache os possı́veis valores de n, m ∈ N ∪ {0} de modo que o
número 9m 10n tenha:
a) 27 divisores b) 243 divisores.
2. Qual é a forma geral dos números naturais que admitem:
a) um só divisor além de 1 e dele próprio?
b) um número primo de divisores?
3. Sejam a, b ∈ N, com (a, b) = 1. Mostre que, se ab é um
quadrado, então a e b são quadrados. Generalize para ab uma
potência r -ésima.
4. Seja m ∈ N. Pode o número m(m + 1) ser a sétima potência
de um número natural? (Generalize.)
5. (ENC-2002) Qual é o menor valor do número natural n que
torna n! divisı́vel por 1000?
6. Mostre que a soma de todos os números naturais menores ou
iguais a n divide o seu produto se, e somente se, n + 1 é composto.
PROFMAT - SBM Aritmética - Lista 6 - Unidades 12 e 13 slide 2/5
Unidade 12 - Continuação
7. Usando a caracterização de mdc e mmc de dois números
naturais a e b através da fatoração em primos desses números,
prove que
(a, b)[a, b] = ab.
8. Mostre que todo número primo p > 2 escreve-se de modo
único como diferença de dois quadrados.
9. Seja p > 1 um número natural com a seguinte propriedade:
Se p divide o produto de dois números naturais quaisquer, então p
divide um dos fatores.
Mostre que p é necessariamente primo.
10. Mostre que, se n e m são dois números naturais não nulos
tais que (n, m) = 1, então d(nm) = d(n)d(m).
11. Mostre que, se n é composto, então o n-ésimo número de
Fibonacci un é composto.

PROFMAT - SBM Aritmética - Lista 6 - Unidades 12 e 13 slide 3/5

Unidade 13
1. Mostre que 42|a7 − a para todo número natural a.
2. Ache o resto da divisão de 12p−1 por p quando p é primo.
3. Mostre que, para todo n ∈ N, é natural o número
3 5 2 3 11
n + n + n.
5 3 15
4. Mostre que, para todo n ∈ N, 15|3n5 + 5n3 + 7n.
5. Seja n ∈ N. Mostre que
a) Se 5 6 | n, 5 6 | n − 1, 5 6 | n + 1, então 5|n2 + 1.
b) Se 7 6 | n, 7 6 | n − 1, 7 6 | n3 + 1, então 7|n2 + n + 1.
6. Sejam a ∈ N. Mostre que 7|a18 − 1, se (a, 7) = 1. Generalize.
7. Um terno de primos é dito de primos trigêmeos se for da forma
p, p + 2 e p + 4. Mostre que 3, 5 e 7 é o único terno de primos
trigêmeos.
PROFMAT - SBM Aritmética - Lista 6 - Unidades 12 e 13 slide 4/5
Unidade 13 - Continuação
8. Mostre que a12 − b 12 é divisı́vel por 13, se a e b são primos
com 13. Mostre também que é divisı́vel por 91, se a e b são
primos com 91.

PROFMAT - SBM Aritmética - Lista 6 - Unidades 12 e 13 slide 5/5

MA14 - Aritmética
Lista 7

Unidades 15 e 16

Abramo Hefez

PROFMAT - SBM
 Unidade 15
Problemas 1.1 a 1.7 do Capı́tulo 8, Seção 1.

Unidade 16
Problemas 2.1 a 2.6 do Capı́tulo 8, Seção 2.

PROFMAT - SBM Aritmética - Lista 7 - Unidades 15 e 16 slide 2/2

MA14 - Aritmética
Lista 8

Unidades 17 e 18

Abramo Hefez

PROFMAT - SBM
Unidade 17 - Capı́tulo 8, Seção 3

8.3.1 Ache a decomposição em fatores primos de 50! e determine

com quantos zeros termina esse número.
8.3.2 a) Ache as maiores potências de 2 e de 5 que dividem 1000!.
b) Determine com quantos zeros termina o número 1000!.
c) Ache a maior potência de 104 que divide 1000!.
d) Ache o menor número natural n tal que 57 |n!.
 
2357
8.3.3(Profmat 2011) É possı́vel repartir exatamente
528
objetos entre 49 pessoas?
8.3.4 Mostre que não há nenhum número natural n tal que 37
seja a maior potência de 3 que divida n!.
8.3.5 Mostre que, se m, n ∈ N são tais que (m, n) = 1, então,
(m + n − 1)!
∈ N.
m!n!
PROFMAT - SBM Aritmética - Lista 8 - Unidades 17 e 18 slide 2/7
 8.3.6 a) Mostre que, para todo n ∈ N, tem-se que 2n 6 | n!.
b) Mostre que 2n−1 | n! se, e somente se, existe m ∈ N tal que
n = 2m .
c) Determine todos os números naturais n tais que 2n−2 | n!.
d) Se r ∈ N, determine todos os números naturais n tais que
2n−r | n!.
8.3.7 Sejam n, m ∈ N; mostre que (nm)! é divisı́vel por
[(n!)m , (m!)n ].
8.3.8 Para todo n ∈ N, mostre que (n!)(n−1)! divide (n!)!.
8.3.9 Seja m, n ∈ N, com n > m > 1. Mostre que é inteiro o
número  
(n, m) n
n m

PROFMAT - SBM Aritmética - Lista 8 - Unidades 17 e 18 slide 3/7

Exercı́cios Suplementares

8.S.1 Mostre que 2n divide (2n)!. Mostre que, geralmente, o

produto de 2n números naturais consecutivos é divisı́vel por 2n .
8.S.2 Mostre que 2n |(n + 1)(n + 2) · · · (2n), mas
2n+1 6 | (n + 1)(n + 2) · · · (2n).
8.S.3 Mostre que n!2n 3n divide (3n)!.
pn
 
8.S.4 Se 1 6 r 6 p n com Ep (r ) = k, mostre que é divisı́vel
r
por p n−k , mas não por p n−k+1 .
8.S.5 Mostre que

21000 |1001 × 1002 × · · · × 2000,

mas que
21001 6 | 1001 × 1002 × · · · × 2000.
PROFMAT - SBM Aritmética - Lista 8 - Unidades 17 e 18 slide 4/7
Unidade 18 - Capı́tulo 9, Seção 1

9.1.1 Sejam a, p ∈ N, com p primo. Mostre que, se

a2 ≡ 1 mod p, então a ≡ 1 mod p ou a ≡ −1 mod p.
9.1.2 Ache o resto da divisão
a) de 710 por 51 b) de 2100 por 11
c) de 521 por 127 d) de 14256 por 17
17 21
e) de (116 + 17 ) por 8 f) de 1316 − 225 515 por 3
g) de 1! + 2! + · · · + (1010 )! por 40.
9.1.3(ENC 98) O resto da divisão de 1212 por 5 é:
(A) 0 (B) 1 (C) 2 (D) 3 (E) 4
9.1.4 Para todo n ∈ N, mostre que
a) 1016n − 1 é divisı́vel por 70; b) 198n − 1 é divisı́vel por 17.
9.1.5 Determine o resto da divisão por 7 do número
2 3 100
a) 1010 + 1010 + 1010 + · · · + 1010 b) 17 + 27 + · · · + 1007
c) 16 + 26 + · · · + 1006 d) 22225555 + 55552222
PROFMAT - SBM Aritmética - Lista 8 - Unidades 17 e 18 slide 5/7
 9.1.6 Determine o resto da divisão por 4 do número
a) 1 + 2 + 22 + · · · + 219 b) 15 + 25 + · · · + 1005
9
9.1.7 Determine o algarismo das unidades do número 99 .
9.1.8 Ache os algarismos das centenas e das unidades do número
7999999 .
9.1.9 Mostre, para todo n ∈ N, que
a) 102n ≡ 1 mod 11 b) 102n+1 ≡ −1 mod 11
9.1.10(ENC 2000) Se x 2 ≡ 1 mod 5, então,
(A) x ≡ 1 mod 5 (B) x ≡ 2 mod 5 (C) x ≡ 4 mod 5
(D) x ≡ 1 mod 5 ou x ≡ 4 mod 5
(E) x ≡ 2 mod 5 ou x ≡ 4 mod 5

PROFMAT - SBM Aritmética - Lista 8 - Unidades 17 e 18 slide 6/7

 9.1.11 Suponha que m = p1α1 · · · prαr . Mostre que

a ≡ b mod m ⇐⇒ a ≡ b mod piαi , i = 1, . . . , r .

9.1.12 Ache o menor número natural que deixa restos 5, 4, 3 e 2

quando dividido, respectivamente, por 6, 5, 4 e 3.
9.1.13 Mostre que a soma dos quadrados de quatro números
naturais consecutivos nunca pode ser um quadrado.

PROFMAT - SBM Aritmética - Lista 8 - Unidades 17 e 18 slide 7/7

MA14 - Aritmética
Lista 9

Unidades 19 e 20

Abramo Hefez

PROFMAT - SBM
Unidade 19 - Capı́tulo 9, Seção 2
9.2.1 a) Usando o fato de que 100 é divisı́vel por 4, 25 e 100,
ache critérios de divisibilidade por 4, 25 e 100.
b) Considerando que 1000 é divisı́vel por 8, 125 e 1000, ache
critérios de divisibilidade por 8, 125 e 1000.
9.2.2 Mostre que um número natural na base 10 é divisı́vel por 6
se, e somente se, a soma do algarismo da unidade com o
quádruplo de cada um dos outros algarismos é divisı́vel por 6.
9.2.3 Usando o fato de que
103 ≡ −1 mod 7, 103 ≡ −1 mod 11, 103 ≡ −1 mod 13,
prove o seguinte critério de divisibilidade por 7, 11 e 13:
Um número natural n = nr . . . n2 n1 n0 , escrito na base 10, é
divisı́vel por 7, 11 ou 13, se, e somente se,
n2 n1 n0 − n5 n4 n3 + n8 n7 n6 − n11 n10 n9 + · · · ≡ 0 mod 7,
n2 n1 n0 − n5 n4 n3 + n8 n7 n6 − n11 n10 n9 + · · · ≡ 0 mod 11
e
PROFMAT - SBM Aritmética - Lista 9 - Unidades 19 e 20 slide 2/9
 9.2.4 Analisando a tabela do Exemplo 2.14 (do livro texto),
determine os números de Fibonacci que são divisı́veis por 8, por
11, por 13 ou por 16.
9.2.5 Mostre que um número da forma an = 2n−1 (2n − 1) para
n > 2 é congruente a 1 módulo 9. Conclua que todo número
perfeito par maior do que 6, assim como a soma de seus
algarismos, é da forma 9k + 1.
Sugestão. Utilize as fórmulas do Problema 8.2.3 e indução.
9.2.6 Mostre que se n > 2, então o número de Fermat Fn tem
algarismo da unidade igual a 7.
9.2.7 a) Mostre que para todo n > 1 tem-se que Fn ≡ 5 mod 12.
b) Mostre que nenhum número de Fermat pode ser um quadrado
ou um cubo.

PROFMAT - SBM Aritmética - Lista 9 - Unidades 19 e 20 slide 3/9

 9.2.8 Seja a ∈ N com a > 1. Considere a sequência
an − 1
α(a, n) = .
a−1
a) Mostre que α(a, n) ≡ 0 mod (a − 1) se, e somente se, a − 1|n.
b) Mostre que α(a, n) ≡ 0 mod (a + 1) se, e somente se, n é par.
c) Enuncie esses resultados para a = 10.

PROFMAT - SBM Aritmética - Lista 9 - Unidades 19 e 20 slide 4/9

Unidade 20 - Capı́tulo 10, Seções 1 e 2

10.1.1 Ache o resto da divisão de

a) 560 por 26 b) 3100 por 10.
10.1.2 Mostre que, se m > 2, então ϕ(m) é par.
10.1.3 Mostre que, se p é um número primo, então, para todo
a ∈ Z e para todo k ∈ N, tem-se que

ak(p−1)+1 ≡ a mod p.

10.1.4 a) Mostre que

X 1
i= m ϕ(m).
2
(i, m) = 1
16i <m

b) Mostre que, se m1 , . . . , mϕ(m) é um sistema reduzido de

resı́duos módulo m, então m divide m1 + · · · + mϕ(m) .
PROFMAT - SBM Aritmética - Lista 9 - Unidades 19 e 20 slide 5/9
 10.1.5 Resolva em m ∈ N as equações
a) ϕ(m) = 12 b) ϕ(m) = 8
c) ϕ(m) = 16 d) ϕ(m) = 24
10.1.6 Supondo que (a, m) = (a − 1, m) = 1, mostre que

1 + a + a2 + · · · + aϕ(m)−1 ≡ 0 mod m.

10.1.7 Mostre que, se ϕ(m) = 2r , para algum r ∈ N, então m é

um produto de uma potência de 2 e de primos de Fermat distintos.
Essa equação aparece na resolução dada por Gauss do problema
clássico da construtibilidade com régua e compasso dos polı́gonos
regulares inscritos numa circunferência.
10.1.8 Supondo que (m, n) = 1, mostre que

mϕ(n) + nϕ(m) ≡ 1 mod nm.

PROFMAT - SBM Aritmética - Lista 9 - Unidades 19 e 20 slide 6/9

 10.1.9 Sejam a, m ∈ Z, com m > 1, tais que (a, m) = 1. Mostre
que, se n1 ≡ n2 mod ϕ(m), então an1 ≡ an2 mod m.
10.1.10 Mostre que 2730|n13 − n, para todo n ∈ Z.
10.1.11 Sejam a ∈ Z e n, r ∈ N, com (r , n) = 1. Mostre que no
conjunto
{a, a + r , . . . , a + (n − 1)r },
há exatamente ϕ(n) números primos com n.
10.1.12 Quais são os possı́veis restos da divisão de a100 , onde
a ∈ Z, quando dividido por 125?

PROFMAT - SBM Aritmética - Lista 9 - Unidades 19 e 20 slide 7/9

 10.2.1 Mostre que o número primo p é o menor inteiro maior do
que 1 que divide o número (p − 1)! + 1.
10.2.2 Mostre que, se p > 2 é um número primo, então
a) p|(p − 2)! − 1 b) p|(p − 3)! − (p − 1)/2
10.2.3 Seja p > 3 um número primo.
a) Mostre que p! e (p − 1)! − 1 são primos entre si.
b) Prove que, se n ∈ N e n ≡ (p − 1)! − 1 mod p!, então os p − 2
inteiros que precedem n e os p inteiros que sucedem n são
compostos.
10.2.4 Seja p um número primo e a ∈ N. Mostre que
a) ap + (p − 1)!a ≡ 0 mod p b) (p − 1)!ap + a ≡ 0 mod p
10.2.5 Seja p um número primo tal que p ≡ 3 mod 4. Mostre que
  2
p−1
! ≡ 1 mod p.
2
PROFMAT - SBM Aritmética - Lista 9 - Unidades 19 e 20 slide 8/9
 10.2.6 Seja p um número primo ı́mpar e seja
N = 1 · 3 · 5 · · · (p − 2). Mostre que N ≡ 1 mod p ou
N ≡ −1 mod p.
10.2.7 Seja p um número primo ı́mpar. Mostre que
a) 12 32 · · · (p − 2)2 ≡ 22 42 · · · (p − 1)2 mod p;
b) se p ≡ 1 mod 4, então 22 42 · · · (p − 1)2 ≡ −1 mod p;
c) se p ≡ 3 mod 4, então 22 42 · · · (p − 1)2 ≡ 1 mod p.

PROFMAT - SBM Aritmética - Lista 9 - Unidades 19 e 20 slide 9/9

MA14 - Aritmética
Lista 10

Unidades 21 e 22

Abramo Hefez

PROFMAT - SBM
Unidade 21 - Capı́tulo 11, Seções 1 e 2
11.1.1 Pode o dobro de um número natural deixar resto igual a 9
quando dividido por 26? E quando dividido por 25?
11.1.2 Resolva, quando possı́vel, as congruências:
a) 3X ≡ 5 mod 7; b) 6X ≡ 21 mod 18;
c) 12X ≡ 36 mod 28; d) 12X ≡ −36 mod 28;
e) 151X ≡ 11 mod 245.
11.1.3 Seja p um número primo e seja a um número inteiro tal
que p 6 | a. Mostre que a única solução módulo p da congruência
aX ≡ b mod p é x = ap−2 b.
11.1.4 Sejam a, m ∈ Z, com m > 2 e (a, m) = 1. Mostre que a
única solução módulo m da congruência aX ≡ b mod m é
x = aϕ(m)−1 b.
11.1.5 Mostre que a congruência X 2 + 1 ≡ 0 mod 7 não possui
soluções. Conclua que a equação X 2 − 7Y 2 − 14X + 7Y − 6 = 0
não admite soluções inteiras.
PROFMAT - SBM Aritmética - Lista 10 - Unidades 21 e 22 slide 2/7
 11.2.1 Ache todos os números inteiros que deixam restos 2, 3 e 4
quando divididos por 3, 4 e 5, respectivamente.
11.2.2 Ache o menor número natural que deixa restos 1, 3 e 5
quando dividido por 5, 7 e 9, respectivamente.
11.2.3 Dispomos de uma quantia de x reais menor do que 3 000.
Se distribuirmos essa quantia entre 11 pessoas, sobra R$1, 00; se a
distribuirmos entre 12 pessoas, sobram R$2, 00 e se a distribuirmos
entre 13 pessoas, sobram R$3, 00. De quantos reais dispomos?
11.2.4 Um macaco, ao subir uma escada de dois em dois degraus,
deixa de sobra um degrau; ao subir de três em três degraus,
sobram dois degraus; e ao subir de cinco em cinco degraus, sobram
três degraus. Quantos degraus possui a escada, sabendo que o
número de degraus está entre 150 e 200 ?
11.2.5 Resolva o sistema:
3X ≡ 1 mod 7, 5X ≡ 2 mod 11, 4X ≡ 3 mod 13.
PROFMAT - SBM Aritmética - Lista 10 - Unidades 21 e 22 slide 3/7
 11.2.6 Levando em consideração que 2275 = 25 × 13 × 7, resolva
a congruência 3X ≡ 11 mod 2275.
11.2.7 Resolva o sistema:
X ≡ 2 mod 3, X ≡ 3 mod 4, X ≡ 4 mod 5, X ≡ 5 mod 6.
11.2.8 Resolva o sistema:
X ≡ 2 mod 3, X ≡ 3 mod 4, X ≡ 4 mod 5, X ≡ 2 mod 6.
11.2.9 (Yi Shing, aprox. 700d.C.) Ache os inteiros que deixam
restos 1, 2, 5 e 5 quando divididos respectivamente por 2, 3, 6 e 12.
11.2.10 Sejam F1 , . . . , Fn os n primeiros números de Fermat.
Mostre que existe um número natural N tal que Fi divide
N + i − 1 para i = 1, . . . , n.

PROFMAT - SBM Aritmética - Lista 10 - Unidades 21 e 22 slide 4/7

Unidade 22 - Capı́tulo 11, Seção 3

11.3.1 Seja {a1 , . . . , am } um sistema completo de resı́duos

módulo m.
a) Mostre que se a é um inteiro, então {a1 + a, . . . , am + a} é um
sistema completo de resı́duos módulo m.
b) Se (a, m) = 1, então {a · a1 , . . . , a · am } é um sistema completo
de resı́duos módulo m. Mostre que vale a recı́proca.
c) Se p é primo e a um inteiro que não é múltiplo de p, mostre que
ap−1 ≡ 1 mod p (Pequeno Teorema de Fermat).
d) Mostre que se (r , m) = 1, então {a, a + r , . . . , a + (m − 1)r } é
um sistema completo de resı́duos módulo m.
Sugestão. (para c) Considere os dois sistemas completos de
resı́duos mod p: {0, 1, . . . , p − 1} e {0, a · 1, . . . , a(p − 1)} e note
que
1 · · · (p − 1) ≡ ap−1 · 1 · · · (p − 1) mod p.

PROFMAT - SBM Aritmética - Lista 10 - Unidades 21 e 22 slide 5/7

 11.3.2 Construa as tabelas da adição e da multiplicação para Z6 e
Z7 .
11.3.3 Ache os elementos invertı́veis de Z6 , Z7 , Z8 e Z9 .
11.3.4 Ache os inversos de
a) [5] em Z6 b) [3], [4] e [5] em Z7
c) [3], [5], e [7] em Z8 d) [5], [4] e [8] em Z9
e) [1 951] em Z2 431 f) [3], [5] e [7] em Z8
11.3.5 a) Seja {a1 , . . . , aϕ(m) } um sistema reduzido de resı́duos
módulo m. Mostre que se (a, m) = 1, então {a · a1 , . . . , a · aϕ(m) }
é um sistema reduzido de resı́duos módulo m.
b) Utilize o item anterior para dar uma outra demonstração do
Teorema de Euler.

PROFMAT - SBM Aritmética - Lista 10 - Unidades 21 e 22 slide 6/7

 11.3.6 Considere Zm para m > 2. Mostre que
(a) Zm tem um número par de elementos invertı́veis;
(b) se [a] é invertı́vel, então −[a] é invertı́vel e [a] 6= −[a].
(c) Mostre que a soma dos elementos invertı́veis de Zm é igual a
[0].
(d) Mostre que a soma de todos os elementos de um sistema
reduzido qualquer de resı́duos módulo m é sempre múltiplo de m.
11.3.7 (Enade 2008) No anel dos inteiros módulo 12, R = Z12 ,
(A) não há divisores de zero.
(B) todo elemento não nulo é invertı́vel.
(C) o subconjunto dos elementos invertı́veis forma um subanel de
R.
(D) a multiplicação não é comutativa.
(E) há exatamente quatro elementos invertı́veis.
PROFMAT - SBM Aritmética - Lista 10 - Unidades 21 e 22 slide 7/7