MA553

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

MA553/Plínio soluções cap.1 .pdf
1
Teoria dos Nu´meros
Soluc¸o˜es dos Exercı´cios do Capı´tulo 1
1. Encontrar, usando o algoritmo da divisa˜o de Euclides, o ma´ximo divisor comum dos seguintes pares
de nu´meros:
(a) 542 e 234: 2
(b) 9652 e 252: 4
(c) 24573 e 1387: 1
(d) 4276 e 1234: 2
(e) 48762 e 176: 2
(f) 42516 e 97421: 1
(g) 8374 e 24517: 1
(h) 35262 e 12753: 1
2. Achar o mı´nimo mu´ltiplo comum dos seguintes pares de nu´meros:
(a) 44 e 32: 352
(b) 234 e 12: 468
(c) 35 e 24: 840
(d) 142 e 742: 52682
(e) 17 e 141: 2397
(f) 42 e 52: 1092
(g) 501 e 2141: 438905
(h) 144 e 64: 576
3. Encontrar uma sequeˆncia de pelo menos 30 inteiros consecutivos e compostos.
Soluc¸a˜o: Para ak = 31! + k + 1, temos que a1 = 31! + 2 e´ composto (coloque o 2 em evideˆncia),
temos que a2 = 31! + 3 e´ composto (coloque aqui o 3), temos que a3 = 31! + 4 tambe´m e´ composto,
e assim por diante, ate´ o a30 = 31! + 31. Com isso, obtemos uma sequeˆncia de 30 inteiros compostos
consecutivos.
4. Mostrar, por induc¸a˜o, que:
(a)
12 + 22 + 32 + . . .+ n2 =
n(n+ 1)(2n+ 1)
6
Soluc¸a˜o: De fato, para n = 1, 12 = 1 = 1(1+1)(2·1+1)
6
= 1·2·3
6
. Supondo va´lida para um n = k,
analisemos o caso n = k + 1:
(k + 1)((k + 1) + 1)(2(k + 1) + 1)
6
=
(k + 1)(k + 2)(2k + 3)
6
=
(k + 1)(2k2 + 7k + 6)
6
=
(k + 1)[6(k + 1) + k(2k + 1)]
6
=
6(k + 1)2 + k(k + 1)(2k + 1)
6
= (k+1)2+
k(k + 1)(2k + 1)
6
=
(k + 1)2 + k2 + . . .+ 32 + 22 + 11
(b) 1 + 3 + 5 + . . .+ (2n− 1) = n2
Soluc¸a˜o: De fato, para n = 1, 1 = 12. Supondo va´lida para um n = k, analisemos o caso n = k + 1:
(k + 1)2 = k2 + 2k + 1 = k2 + 2(k + 1)− 1 = (2(k + 1)− 1) + (2k − 1) + . . .+ 5 + 3 + 1.
(c)
1 · 2 + 2 · 3 + 3 · 4 + . . .+ n(n+ i) = n(n+ 1)(n+ 2)
3
2
Soluc¸a˜o: De fato, para n = 1, 1 · 2 = 2 = 1(1+1)(1+2)
3
= 1·2·3
3
. Supondo va´lida para n = k,
analisemos o caso n = k + 1:
(k + 1)((k + 1) + 1)((k + 1) + 2)
3
=
(k + 1)(k + 2)(k + 3)
3
=
3(k + 1)(k + 2) + k(k + 1)(k + 2)
3
=
(k + 1)(k + 2) +
k(k + 1)(k + 2)
3
= (k + 2)(K + 1) + (k + 1)k + . . .+ 4 · 3 + 3 · 2 + 2 · 1
(d) n! > 2n, ∀n ≥ 3
Soluc¸a˜o: De fato, para n = 4, 4! = 24 > 16 = 24. Supondo va´lida para n = k, analisemos o caso
n = k + 1: (k + 1)! = (k + 1)k! > (k + 1)2k > k2k > 2 · 2k = 2k+1, pois k ≥ 3, por hipo´tese.
(e) n2 > 2n+ 1, ∀n ≥ 3
Soluc¸a˜o: De fato, para n = 3, 32 = 9 > 7 = 2 · 3 + 1. Supondo va´lida para n = k, analisemos o
caso n = k + 1: (k + 1)2 = 1 + 2k + k2 > 1 + 2k + 2k + 1 = 2k + 2k + 2 > 2k + 2k + 1 >
2k + 2 + 1 = 2(k + 1) + 1.
(f) 9|(10n+1 − 9n− 10),∀n ≥ 1
Soluc¸a˜o: De fato, para n = 1, 102−9−10 = 100−19 = 81, que e´ mu´ltiplo de nove. Supondo va´lida
para n = k, analisemos o caso n = k+1: 10(k+1)+1−9(k+1)−10 = 10 ·10k+1−9k−9−10, mas
10k+1−9k−10 = 9q, q ∈ Z⇒ 10k+1 = 9q+9k+10, logo 10 ·10k+1−9k−9−10 = 10(9q+9k+
10)−9k−19 = 90q+90k+100−9k−19 = 90q+90k−9k+81 = 90q+81k+81 = 9(10q+9k+9),
que e´ mu´ltiplo de nove. Portanto, vale tambe´m para n = k + 1.
5. Provar que o produto de 3 inteiros consecutivos e´ divisı´vel por 6.
Soluc¸a˜o:
Lema: O produto de dois nu´meros consecutivos e´ par. De fato, m(m + 1) e´ par, pois, se m for par,
m(m + 1) = 2λ(2λ + 1) = 2p, p ∈ Z, e, se m for ı´mpar, m(m + 1) = (2λ + 1)(2λ + 2) =
2(2λ+ 1)(λ+ 1) = 2q, q ∈ Z.
Queremos mostrar que 6|(n− 1)n(n+1). Note que (n− 1)n(n+1) = (n2 − 1)n = n3 −n. Para
n = 1, n3−n = 0 e 6|0. Suponha´que 6|k3−k, ou seja, k3−k = 6q, q ∈ Z; analisemos o caso n = k+1:
(k+1)3−(k+1) = k3+3k2+3k+1−k−1 = k3−k+3k2+3k = 6q+3k2+3k = 6q+3k(k+1).
Pelo lema, 6q + 3k(k + 1) = 6q + 3 · 2q′ = 6q + 6q′ = 6(q + q′), que e´ mu´ltiplo de 6. Observe que
6|(n− 1)n(n+ 1)⇒ 6|(1− n)(−n)(−n− 1). Com isso, ∀n ∈ Z, 6|(n− 1)n(n+ 1).
6. Provar que, para todo n ∈ N, 32n+1 + 2n+2 e´ mu´ltiplo de 7 e que 32n+2 + 26n+1 e´ mu´ltiplo de
11.
Soluc¸a˜o:
* Para n = 1, 32·1+1+21+2 = 33+23 = 27+8 = 35 = 7 ·5, que e´ mu´ltiplo de 7. Suponha va´lido
para n = k, ou seja, 7q = 32k+1 + 2k+2 ⇒ 32k+1 = 7q − 2k+2, q ∈ Z; analisemos o caso n = k+ 1:
32(k+1)+1+2k+1+2 = 32k+2+1+2k+2+1 = 32 ·32k+1+2 ·2k+2 = 32 · (7q−2k+2)+2 ·2k+2 =
7 · 9q − 9 · 2k+2 + 2 · 2k+2 = 7 · 9q − 7 · 2k+2 = 7 · (9q − 2k+2).
** Para n = 1, 32·1+2 + 26·1+1 = 34 + 27 = 81 + 128 = 209 = 11 · 19. Supondo va´lida para
n = k, ou seja, 32k+2 + 26k+1 = 11q ⇒ 32k+2 = 11q − 26k+1; analisemos o caso n = k + 1:
32(k+1)+226(k+1)+1 = 32 · 32k+2 + 26 · 26k+1 = 9 · 32k+2 + 64 · 26k+1 = 9 · (11q − 26k+1) +
64 · 26k+1 = 11 · 9q − 9 · 26k+1 + 64 · 26k+1 = 11 · 9q + 55 · 26k+1 = 11 · (9q + 5 · 26k+1).
7. Encontrar inteiros x y tais que
(a) 93x+ 81y = 3 ⇒ 31x+ 27y = 1
31 = 27 · 1 + 4⇒ 4 = 31− 27
3
27 = 4 · 6 + 3⇒ 3 = 27− 4 · 6
4 = 3 · 1 + 1⇒ 1 = 4− 3
1 = 31− 27− (27− (31− 27) · 6)
= 31− 27− 27 + (31− 27) · 6
= 31− 27− 27 + 6 · 31− 6 · 27
= 7 · 31− 8 · 27
= 7 · 31− 8 · 27 + 27 · k · 31− 31 · k · 27
= (7 + 27k) · 31− (8 + 31k) · 27
(x, y) = (7 + 27k,−8− 31k), k ∈ Z
(b) 43x+ 128y = 1
128 = 43 · 2 + 42⇒ 42 = 128− 2 · 43
43 = 42 · 1 + 1⇒ 1 = 43− 42
1 = 43− (128− 2 · 43)
= 43− 128 + 2 · 43
= 3 · 43− 128
= 3 · 43− 128 + 43 · k · 128− 128 · k · 43
= (3− 128k) · 43− (128− 43k) · 128
(x, y) = (3− 128k, 43k − 128), k ∈ Z
8. Mostrar que se a b sa˜o inteiros positivos, com (a, b) = [a, b], enta˜o a = b.
Soluc¸a˜o: Como sabemos, [a, b] = ab
(a,b)
. Com isso, temos (a, b) = ab
(a,b)
. Como (a, b)|a e (a, b)|b,
temos a
(a,b)
· b
(a,b)
= 1⇒ a
(a,b)
= b
(a,b)
= 1⇒ a = b = (a, b).
9. Mostrar que n5 − n e´ divisı´vel por 30 para todo inteiro n.
Soluc¸a˜o:
Lema 1: Para todon natural, n(7+6n+2n2) e´ mu´ltiplo de 3. De fato, paran = 1, 1·(7+6·1+2·12) =
7 + 6 + 2 = 15 = 3 · 5. Supondo va´lida para n = k, ou seja, 7k + 5k2 + 2k3 = 3q; analisemos o caso
n = k+1: (k+1)(7+6 · (k+1)+2 · (k+1)2) = (k+1)(13+10k+2k2) = 15k+10k2+2k3+
15+10k+2k2 = (2k3+6k2+7k)+6k2+18k+15 = 3q+6k2+18k+15 = 3 ·(q+2k2+6k+5).
Lema 2: Para todo n natural, n(n + 1)(n2 + n + 1) e´ mu´ltiplo de 6. De fato, para n = 1, 1 ·
(1 + 1) · (12 + 1 + 1) = 2 · 3 = 6. Supondo va´lida para n = k, ou seja, k(k + 1)(k2 + k + 1) =
k4+2k3+2k2+k = 6q; analisemos o caso para n = k+1: (k+1)((k+1)+1)((k+1)2+(k+1)+1) =
(k + 1)(k + 2)(k2 + 3k + 3) = (k2 + 3k + 2)(k2 + 3k + 3) = k4 + 6k3 + 14k2 + 15k + 6 =
(k4+2k3+2k2+k)+4k3+12k2+14k+6 = 6q+4k3+12k2+14k+6 = 6q+2k(7+6k+2k2)+6.
Pelo lema 1, 6q + 2k(7 + 6k + 2k2) + 6 = 6q + 2 · 3q′ + 6 = 6q + 6q′ + 6 = 6 · (q + q′ + 1).
Com isso, podemos provar que 30|(n5 − n). Para n = 1, n5 − n = 15 − 1 = 0, e 30|0. Supondo
va´lida para n = k, ou seja, k5 − k = 30q; analisemos o caso para n = k + 1: (k + 1)5 − (k + 1) =
k5 + 5k4 + 10k3 + 10k2 + 5k + 1 − k − 1 = k5 − k + 5k4 + 10k3 + 10k2 + 5k = 30q + 5k4 +
10k3 + 10k2 + 5k = 30q + 5k(k3 + 2k2 + 2k + 1) = 30q + 5k(k + 1)(k2 + k + 1). Pelo lema
4
2, 30q + 5k(k + 1)(k2 + k + 1) = 30q + 5 · 6q′ = 30q + 30q′ = 30(q + q′). Por outro lado, como
30|(n5 − n), temos que 30|((−n)5 − (−n)); logo, ∀n ∈ Z, 30|(n5 − n).
10. Mostrar que a equac¸a˜o x3 + 7x+ 17 = 0 na˜o tem soluc¸a˜o inteira.
Soluc¸a˜o: Se x3+7x+17 = 0⇒ x3+7x = −17 admite soluc¸a˜o inteira, enta˜o, ja´ que x|(x3+7x),
x| − 17. Como 17 e´ primo, os possı´veis valores de x pertencem a {−17,−1, 1, 17}. Por outro lado,
(−17)3+7 ·(−17) < −17, (−1)3+7 ·(−1) = −8 6= −17, 13+7 ·1 = 8 6= −17 e 173+7 ·17 > −17.
Portanto, na˜o admite soluc¸a˜o inteira.
11. Mostrar que, para nenhum n ∈ N, 2n + 1 e´ um cubo.
Soluc¸a˜o:
Lema: Para todo x natural, x2 + x e´ par. De fato, x = 2k ou x = 2k + 1; assim, x2 + x =
(2k)2 + (2k) = 4k2 + 2k = 2 · (2k2 + k), que e´ par, ou x2 + x = (2k + 1)2 + (2k
+ 1) =
4k2 + 4k + 1 + 2k + 1 = 4k2 + 6k + 2 = 2 · (2k2 + 3k + 1), que tambe´m e´ par.
Suponha que 2n + 1 = m3, logo terı´amos 2n = m3 − 1 = (m − 1)(m2 +m + 1). Como 2|2n,
∀n ∈ N, temos que 2|(k− 1)(k2+ k+1). Mas 2 6 |(k2+ k+1), pois k2+ k e´ par e k2+ k+1 e´ ı´mpar.
Assim, 2|(k − 1), para todo k, absurdo.
11. Pode o nu´mero A = 111 . . . 1 formado por trezentos 1’s ser um quadrado?
Soluc¸a˜o:
Lema: Todo quadrado perfeito na˜o deixa resto 3 na divisa˜o por 4. De fato, se um nu´mero e´ par, (2m)2 =
4m2, que deixa resto 0, se e´ ı´mpar, (2m + 1)2 = 4m2 + 4m + 1 = 4(m2 +m) + 1, que deixa resto 1
na divisa˜o por 4. Assim, todo quadrado perfeito deixa resto 0 ou 1. Logo, na˜o deixa resto 3.
O nu´mero na˜o e´ um quadrado, pois deixa resto 3 na divisa˜o por 4. Observe que 111 . . . 111 =
111 . . . 100 + 11 = 100 · 111 . . . 1 + 8 + 3 = 4 · (25 · 111 . . . 1 + 2) + 3 que deixa resto 3 na di-
visa˜o por 4.
13. Sejam F1 = 1, F2 = 1 e Fn = Fn−1 + Fn−2, n ≥ 3 (Fn e´ chamado n-e´simo nu´mero do
Fibonacci). Mostre que
(a) F1 + F3 + F5 + . . .+ F2n−1 = F2n
Soluc¸a˜o: De fato, para n = 1, F2·1−1 = F1 = 1 = F2 = F2·1. Supondo va´lida para n = k,
analisemos o caso para n = k+1: F2(k+1) = F2k+2 = F2k+1 +F2k = F2(k+1)−1 +F2k−1 + . . .+
F5 + F3 + F1.
(b) F2 + F4 + F6 + . . .+ F2n = F2n+1 − 1
Soluc¸a˜o: De fato, para n = 1, F2·1 = F2 = F3 − F1 = F2·1+1 − 1. Supondo va´lida para
n = k, analisemos o caso para n = k + 1: F2(k+1)+1 − 1 = F2k+3 − 1 = F2k+2 + F2k+1 − 1 =
F2(k+1) + F2k + . . .+ F6 + F4 + F2.
(c) F1 + F2 + F3 + . . .+ Fn = Fn+2 − 1
Soluc¸a˜o: De fato, para n = 1, F1 = F3−F2 = F1+2− 1. Supondo va´lida para n = k, analisemos o
caso para n = k+1: Fk+1+2−1 = Fk+3−1 = Fk+2+Fk+1−1 = Fk+1+Fk+ . . .+F3+F2+F1.
(d) F1F2 + F2F3 + F3F4 + . . .+ F2nF2n+1 = F 22n+1 − 1
Soluc¸a˜o: De fato, para n = 1, F1F2 + F2F3 = F1(F3 − F1) + (F3 − F1)F3 = F1F3 −
F 21 + F
2
3 − F1F3 = F 23 − F 21 = F 23 − 1. Supondo va´lida para n = k, analisemos o caso para
n = k + 1: F1F2 + F2F3 + . . . + F2kF2k+1 + F2k+1F2k+2 + F2k+2F2k+3 = F 22k+1 − 1 +
F2k+1F2k+2+F2k+2F2k+3 = F
2
2k+1− 1+(F2k+3−F2k+1)F2k+3+F2k+1(F2k+3−F2k+1) =
F 22k+1 − 1 + F 22k+3 − F2k+1F2k+3 + F2k+1F2k+3 − F 22k+1 = F 22k+3 − 1 = F2(k+1)+1 − 1.
5
14. Mostrar que, para os nu´meros de Fibonacci, definidos no problema anterior, satisfazem:
(a) (Fn, Fn+1) = 1
Soluc¸a˜o: De fato, para n = 1, (F1, F2) = (1, 1) = 1. Supondo va´lida para n = k, analisemos o caso
para n = k + 1: (Fk+1, Fk+2) = (Fk+1, Fk+1 + Fk) = (Fk+1, Fk) = 1.
(b) (Fn, Fn+3) = 1 ou 2
Soluc¸a˜o:
Lema: Se a e´ ı´mpar e (a, b) = 1, enta˜o (a, 2b) = 1, com b inteiro. Certamente, se tive´ssemos
(a, 2b) = k, com k 6= 1, terı´amos que a = αk e 2b = βk, logo a
α
= 2b
β
. Como 2| 2b
β
, 2| a
α
; com isso,
terı´amos que 2|a, absurdo, pois a e´ ı´mpar.
Observe que (Fn, Fn+3) = (Fn, Fn+2 + Fn+1) = (Fn, Fn + 2Fn+1) = (Fn, 2Fn+1). E´ fato
que, se Fn for par. Fn+1 sera´ ı´mpar, se Fn for ı´mpar, Fn+1 podera´ ser par ou ı´mpar. Se Fn for par,
(Fn, 2Fn+1) = 2(
Fn
2
, Fn+1) = 2 · 1 = 2, pois (Fn, Fn+1) = 1. Se Fn for ı´mpar, temos, pelo lema,
que, independente de Fn+1, (Fn, 2Fn+1) = 1, ja´ que Fn e´ ı´mpar e (Fn, Fn+1) = 1.
15. Mostrar que, ale´m de 2 = 13 + 1, nenhum nu´mero da forma n3 + 1 e´ primo.
Soluc¸a˜o: Basta observar que n3 + 1 = (n+ 1)(n2 − n+ 1), que e´ composto para n 6= 1.
16. Utilizando a sequeˆncia Rn = n! + 1, n ≥ 1, fornecer uma outra demonstrac¸a˜o para a infinitude
dos primos.
Soluc¸a˜o:
Lema: Se a|b, enta˜o a 6 |b + 1. Suponha que a|b + 1, logo b + 1 = ak ⇒ b = ak − 1 ⇒ ak′ =
ak − 1⇒ ak − ak′ = 1⇒ a(k − k′) = 1⇒ a|1, absurdo.
Suponha que a sequeˆncia dos primos seja finita. Seja a subsequeˆncia (p1, p2, . . . , pn) dos primos que
podem ser escritos na forma pn = n! + 1. Supondo pn sendo o u´ltimo dos primos da forma n! + 1, temos
pn+1 = (n+1)!+1 = (n+1)n!+1+(n+1)−(n+1) = (n+1)(n!+1)+1−(n+1) = (n+1)pn−n.
Se existe um nu´mero que divida Pn+1, sena˜o ele mesmo ou 1, esse nu´mero divide (n + 1)pn − n. Seja
k esse nu´mero. Pelo lema, k na˜o pode dividir (n + 1)pn − n, ale´m de pn ser primo. Logo, pn+1 e´ outro
primo da forma (n+ 1)! + 1 que na˜o esta´ na sequeˆncia dos primos, absurdo.
17. Mostrar que todo inteiro maior do que 11 e´ a soma de dois inteiros compostos.
Soluc¸a˜o: Queremos mostrar que n = aα+ bβ, com n > 11, a, b,α e β inteiros diferentes de 1. Se n
for composto, ou seja, n = λµ, temos que n = λ(k + k′), onde k e k’ sa˜o inteiros; assim, n = λk + λk′,
e segue o resultado. Se n for primo, temos que e´ da forma 6m + 1 ou 6m + 5; para n = 6m + 1,
n = 6(k + 8) + 1, onde k e´ inteiro, logo, n = 6k + 48 + 1 = 6m + 49, e segue o resultado; para
n = 6m+5, n = 6(k′+10)+5 = 6k′+60+5 = 6k′+65, e segue o resultado. Observe que a hipo´tese
de n > 11 foi satisfeita; portanto, todo inteiro maior do que onze e´ soma de dois inteiros compostos.
18. Mostrar que 3 e´ o u´nico primo p tal que p, p+ 2 e p+ 4 sa˜o todos primos.
Soluc¸a˜o: Suponha que exista outro p 6= 3 tal que p, p + 2 e p + 4 sejam todos primos. p = 2 ou
p = 5? Na˜o, pois 2 + 2 = 4 e 5 + 4 = 9, que sa˜o compostos. Logo, p e´ da forma 6k + 1 ou 6k + 5. Se
p = 6k+1, temos que p+2 = 6k+1+2 = 6k+3 = 3(2k+1), que e´ composto. Se p = 6k+5, temos
que p + 4 = 6k + 5 + 4 = 6k + 9 = 3(2k + 3), que e´ composto. Com isso, obtemos um contradic¸a˜o.
Portanto, para nenhum p 6= 3, p+ 2 e p+ 4 sa˜o primos tambe´m. Assim, 3 e´ o u´nico.
19. Achar a soma de todos os nu´meros formados pelas permutac¸o˜es dos dı´gitos 1, 2, 3, 4 e 5, isto e´:
12345 + . . .+ 54321.
Soluc¸a˜o: Observe que 1 + 2 + 3 + 4 + 5 = 15. Logo, temos:
6
5 4 3 2 1
...
...
...
...
...
+ 1 2 3 4 5
1 6 6 6 6 5
20.Provar que na˜o existe n ∈ N tal que 7|(4n2 − 3).
Soluc¸a˜o:
Lema: Se n e´ natural, enta˜o 7 - (n2 + 1). Como n e´ natural, ele e´ da forma 7k, 7k ± 1, 7k ± 2
ou 7k ± 3, com k natural. Para n = 7k,n2 + 1 = 49k2 + 1 na˜o e´ mu´ltiplo de 7. Para n = 7k ± 1,
n2 + 1 = (7k ± 1)2 + 1 = 49k2 ± 14k + 2 = 7(7k2 ± 2k) + 2 na˜o e´ mu´ltiplo de 7. Para n = 7k ± 2,
n2 + 1 = (7k ± 2)2 + 1 = 49k2 ± 28k + 5 = 7(7k2 ± 4k) + 5 na˜o e´ mu´ltiplo de 7. Para n = 7k ± 3,
n2 + 1 = (7k ± 3)2 + 1 = 49k2 ± 42k + 9 = 7(7k2 ± 6k + 1) + 2 tambe´m na˜o e´ mu´ltiplo de 7.
Portanto, 7 6 |(n2 + 1).
Suponha que exista n ∈ N tal que 7|(4n2 − 3). Logo, 4n2 − 3 = 7q ⇒ 4n2 − 3+ 7 = 7(q+1)⇒
4n2 + 4 = 7(q + 1)⇒ 4(n2 + 1) = 7(q + 1)⇒ 7|(n2 + 1). Pelo lema, chegamos numa contradic¸a˜o.
21. Sabendo que o resto da divisa˜o de um inteiro b por 7 e´ 5, calcular o resto da divisa˜o por 7 dos
seguintes nu´meros:
(a) −b
b = 7q + 5⇒ −b = −7k − 5 = 7(−k) + 7− 7− 5 = 7(−k)− 7 + 2 = 7(−k − 1) + 2.
−b deixa resto 2.
(b) 2b
2b = 14q + 10 = 14q + 7 + 3 = 7(2q + 1) + 3
2b deixa resto 3.
(c) 3b+ 7
3(7q + 5) + 7 = 21q + 15 + 7 = 21q + 22 = 21q + 21 + 1 = 7(3q + 3) + 1
3b+ 7 deixa resto 1.
(d) 10b+ 1
10(7q + 5) + 1 = 70q + 50 + 1 = 70q + 49 + 2 = 7(10q + 7) + 2
10b+ 1 deixa resto 2.
(e) b2 + b+ 1
(7q+5)2+(7q+5)+1 = 49q2+70q+25+7q+5+1 = 49q2+77q+31 = 49q2+77q+28+3 =
7(7q2 + 11q + 4) + 3
b2 + b+ 1 deixa resto 3.
22. Seja Un = 111 . . . 1 um nu´mero formado por n 1’s. Provar que Un primo implica n primo.
Soluc¸a˜o: Suponha n = pq, com p e q diferentes de 1. Temos que Un = 111 . . . 1 = 10
n−1
9
=
10pq−1
9
=
(10p)q−1
9
= 10
p−1
9
· ((10p)q−1 + (10p)q−2 + . . . + (10p) + 1). Logo, Un e´ composto,
absurdo.
23. Mostrar que, se, para algum n, m|(35n+ 26), m|(7n+ 3) e m > 1, enta˜o m = 11.
Soluc¸a˜o: m|(35n + 26) e m|(7n + 3) ⇒ 35n + 26 = k1m e 7n + 3 = k2m ⇒ k1 − 4k2 =
35n+26−4(7n+3) = 35n+26−28n−12 = 7n+14⇒ m(k1−4k2) = 7n+14⇒ m|(7n+14).
Comomk
= 7n+14 = 7n+3+11, em|(7n+3), m|11, ou sejam = 11 oum = 1 (pois 11 e´ primo).
Como m > 1, concluı´mos que m = 11.
7
24. Sendo 1
a
+ 1
b
um inteiro, onde a e b sa˜o inteiros positivos, mostrar que a=b. Mostrar tambe´m que
a = 1 ou a = 2.
Soluc¸a˜o: 1
a
+ 1
b
= b
ab
+ a
ab
= a+b
ab
⇒ ab|(a + b) ⇒ a + b = abq ⇒ a − abq + b = 0 ⇒
a(1−bq) = −b⇒ a|b. Por outro lado, a−abq+b = 0⇒ a−b(aq−1) = 0⇒ a = b(aq−1)⇒ b|a.
Portanto, a = b. Logo, a+ b = abq ⇒ a+ a = aaq ⇒ 2a = qa2 ⇒ q = 2a
a2
= 2
a
⇒ a|2⇒ a = 1 ou
a = 2, pois 2 e´ primo.
25. Mostrar que, se (a, b) = 1, enta˜o (2a+ b, a+ 2b) = 1 ou 3.
Soluc¸a˜o: (2a+b, a+2b) = d. Logo, 2a+b = k1d e a+2b = k2d e, portanto, d(2k1−k2) = 2(2a+
b)−(a+2b) = 4a+2b−a−2b = 3a e d(−k1+2k2) = −(2a+b)+2(a+2b) = −2a−b+2a+4b = 3b.
Como sabemos, (3a, 3b) = 3(a, b) = 3. Mas (3a, 3b) = (d(2k1 − k2), d(−k1 + 2k2)) = d(2k1 −
k2,−k1 + 2k2) = 3. Fazendo (2k1 − k2,−k1 + 2k2) = k, dk = 3⇒ d = 1 ou d = 3.
26. Mostrar que, sendo n um inteiro, o nu´mero n(n+ 1)(n+ 2)(n+ 3) + 1 e´ um quadrado perfeito.
Soluc¸a˜o: Basta observar quen(n+1)(n+2)(n+3)+1 = n4+6n3+11n2+6n+1 = (n2+3n+1)2.
27. Determinar todos os nu´meros de 3 algarismos divisı´veis por 8, 11 e 12.
Soluc¸a˜o:
* 104 + 8n, 0 ≤ n ≤ 111.
** 110 + 11n, 0 ≤ n ≤ 80.
*** 108 + 12n, 0 ≤ n ≤ 74.
28. Encontrar todos os inteiros positivos n para os quais (n+ 1)|(n2 + 1).
Soluc¸a˜o: Se (n + 1)|(n2 + 1), enta˜o n2 + 1 = (n + 1)q ⇒ n2 − 1 + 2 = (n + 1)q ⇒
(n + 1)(n − 1) + 2 = (n + 1)q ⇒ n − 1 + 2
n+1
= q ⇒ 2
n+1
= q − n + 1 ⇒ 2
n+1
e´ um
inteiro. Como 2 e´ primo, n+ 1 = 1 ou n+ 1 = 2⇒ n = 0 ou n = 1.
29. Dados a e b inteiros, com b 6= 0, mostrar que existem inteiros q e r satisfazendo a = qb ± r,
0 ≤ r ≤ b/2.
Soluc¸a˜o: Pelo algoritmo da divisa˜o, existem m e n tais que a = mb + n, 0 ≤ n < b. Se b for par, n
pode ser b
2
, pois b
2
< b. Se b for ı´mpar, n < b
2
ou n > b
2
. Para qualquer b, se 0 ≤ n ≤ b
2
, fac¸a m = q e
n = r; se b
2
< n < b, temos− b
2
> −n > −b⇒ b− b
2
> b− n > 0⇒ b
2
> b− n > 0, fac¸a m = q e
r = −n.
30. Mostrar que, se a e b sa˜o inteiros, (a, 3) = (b, 3) = 1, enta˜o a2 + b2 na˜o e´ um quadrado perfeito.
Soluc¸a˜o:
Lema: Todos os quadrados perfeitos deixam resto 1 ou 0 na divisa˜o por treˆs. De fato, se a = 3k,
a2 = 9k2, que deixa resto 0; se a = 3k ± 1, a2 = 9k2 ± 6k + 1 = 3(3k2 ± 2k) + 1, que deixa resto
resto 1. Logo, segue o resultado.
Suponha que a2 + b2 = c2. Pelo lema, os quadrados de nu´meros 6= 3q deixam resto 1 na divisa˜o por
treˆs. Como (a, 3) = 1 e (b, 3) = 1, temos que a 6= 3q e b 6= 3q′; assim, a2 e b2 deixam resto 1 na divisa˜o
por treˆs. Ou seja, a2 = 3k1 + 1 e b2 = k2 + 1⇒ a2 + b2 = 3(k1 + k2) + 2, que deixa resto 2, e na˜o 1;
logo, a2 + b2 na˜o e´ um quadrado perfeito, contradic¸a˜o.
31. Mostrar que, para n > 1, os nu´meros n4 + 4 e n4 + n2 + 1 sa˜o ambos compostos.
Soluc¸a˜o: Basta observar que:
*n4+4 = n4+4n2+4−4n2 = (n2+2)2−4n2 = (n2+2)2−(2n)2 = (n2+2+2n)(n2+2−2n),
que e´ composto, para n > 1.
8
**n4+n2+1 = n4+2n2−n2+1 = n4+2n2+1−n2 = (n2+1)2−n2 = (n2+1−n)(n2+1+n),
que e´ composto, para n > 1.
32. Demonstrar os itens (a), (b) e (c) do problema 13 sem fazer uso de induc¸a˜o.
(a) F1 + F3 + F5 + . . .+ F2n−1 = F2n
Soluc¸a˜o: F2n = F2n−1 + F2n−2 = F2n−1 + F2n−3 + F2n−4 = F2n−1 + F2n−3 + F2n−5 +
F2n−6 = F2n−1 + F2n−3 + F2n−5 + . . . + F6 = F2n−1 + F2n−3 + F2n−5 + . . . + F5 + F4 =
F2n−1 + F2n−3 + . . .+ F5 + F3 + F2 = F2n−1 + . . .+ F5 + F3 + F1.
(b) F2 + F4 + F6 + . . .+ F2n = F2n+1 − 1
Soluc¸a˜o: F2n+1−1 = F2n+F2n−1−1 = F2n+F2n−2+F2n−3−1 = F2n+F2n−2+F2n−4+
F2n−5−1 = F2n+F2n−2+F2n−4+ . . .+F7−1 = F2n+F2n−2+F2n−4+ . . .+F6+F5−1 =
F2n+F2n−2+. . .+F6+F4+F3−1 = F2n+. . .+F6+F4+F2+F1−1 = F2n+. . .+F6+F4+F2.
(c) F1 + F2 + F3 + . . .+ Fn = Fn+2 − 1
Soluc¸a˜o: Fn+2−1 = Fn+1+Fn−1 = Fn+Fn−1+Fn−1+Fn−2−1 = Fn+Fn−1+Fn−2+
Fn−2 +Fn−3 − 1 = Fn +Fn−1 +Fn−2 +Fn−3 + . . .+F4 +F4 +F3 − 1 = Fn +Fn−1 + . . .+
F4+F3+F3+F2− 1 = Fn+ . . .+F4+F3+F2+F2+F1− 1 = Fn+ . . .+F4+F3+F2+F1.
33. Mostrar que (a, bc) = 1 se, e somente se, (a, b) = (a, c) = 1.
Soluc¸a˜o:
*(a, bc) = 1⇒ a 6 |bc e b 6 |a e c 6 |a⇒ a 6 |b e b 6 |a e a 6 |c e c 6 |a⇒ (a, b) = (a, c) = 1.
**(a, b) = 1 e (a, c) = 1 ⇒ ∃x1, x2, y1, y2 ∈ Z; 1 = x1a + y1b e 1 = x2a + y2c ⇒ x1a +
y1b(x2a+y2c) = 1, pois 1 = x2a+y2c,⇒ x1a+x2y1ab+y1y2bc = 1⇒ a(x1+x2y1b)+y1y2bc =
1⇒ x3a+ y3bc = 1. Como bc 6 |(x3a+ y3bc), bc 6 |x3a⇒ bc 6 |a, e, como a 6 |b e a 6 |c, (a, bc) = 1.
34. Mostrar que se b|c, enta˜o (a+ c, b) = (a, b).
Soluc¸a˜o: De b|c, temos c = kb. Logo, (a+ c, b) = (a+ kb, b) = (a, b).
35. Mostrar que se (a, c) = 1, enta˜o (a, bc) = (a, b).
Soluc¸a˜o: Suponha (a, bc) = d e (a, b) = d′. Temos que a = q1d e bc = q2d. Como (a, c) = 1,
existem x e y inteiros tais que xa + yc = 1. Logo, x(q1d) + yc = 1 ⇒ xq1db + ycb = b ⇒
xq1db + y(q2d) = b ⇒ d(xq1b + yq2) = b ⇒ d|b ⇒ d|(a, b) ⇒ d|d′. Se (a, b) = d′, temos d′|a e
d′|b⇒ d′|a e d′|bc⇒ d′|(a, bc)⇒ d′|d. Portanto, d = d′.
36. Mostrar que (a, b, c) = ((a, b), c).
Soluc¸a˜o: Por definic¸a˜o, sendo (a, b, c) = d e ((a, b), c) = d′, de (a, b, c) = d, tem-se que d|a, d|b e
d|c ⇒ d|(a, b) e d|c ⇒ d|((a, b), c) ⇒ d|d′. Por outro lado, de ((a, b), c) = d′, tem-se que d′|(a, b) e
d′|c⇒ d′|a e d′|b e d′|c⇒ d′|(a, b, c)⇒ d′|d. Portanto, (a, b, c) = ((a, b), c).
37. Dizer qual e´ o maior inteiro que pode ser somado ao dividendo sem alterar o quociente quando se
divide 431 por 37.
Soluc¸a˜o: Observe que 431 = 11 · 37 + 24.
431 | 37
− 407 11
(24)
Note que o maior numero que pode ser somado a 431 e´ 12, pois 431 + 12 = 11 · 37 + 36, e se
pude´ssemos somar um maior do que 12, como 13, terı´amos: 431 + 13 = 11 · 37 + 37 = 12 · 37, que
alteraria o quociente.
9
38. Para cada par de inteiros a e b dado abaixo, encontrar o quociente q e o resto r satisfazendo o
algoritmo da divisa˜o de Euclides.
(a) a = 59, b = 6. q=9 e r=5
59 | 6
− 54 9
(5)
(b) a = −71, b = 5. q=-15 e r=4
−71 | 5
− −75 −15
(4)
(c) a = −48, b = −7. q=7 e r=1
−48 | −7
− −49 7
(1)
(d) a = 67, b = −13. q=-5 e r=2
67 | −13
− 65 −5
(2)
39. Mostrar que se n e m sa˜o inteiros ı´mpares, enta˜o 8|(n4 +m4 − 2).
Soluc¸a˜o: Por hipo´tese, n = 2k1 + 1 e m = 2k2 + 1; logo, n4 + m4 − 2 = (2k1 + 1)2 +
(2k2 + 1)2 − 2 = 16k41 + 32k31 + 24k21 + 8k1 + 1 + 16k42 + 32k32 + 24k22 + 8k2 + 1 − 2 =
8(2k41 + 4k
3
1 + k1 + 2k
4
2 + 4k
3
2 + 3k
2
2 + k2).
40. Encontrar o menor inteiro positivo da forma 36x+ 54y onde x e y sa˜o inteiros.
Soluc¸a˜o: Sendo d o menor inteiro positivo da forma 36x + 54y, d = (36, 54). Pelo algoritmo de
Euclides, d = 18.
54 = 1 · 36 + 18
36 = 2 · 18 + 0
41. Utilizando o processo descrito no Teorema 1.17, expressar o nu´mero 274 nas bases 2, 5, 7 e 9.
Soluc¸a˜o:
*274 = 256 + 18 = 28 + 16+ 2 = 28 + 24 + 21 = 1 · 28 + 0 · 27 + 0 · 26 + 0 · 25 + 1 · 24 + 0 ·
23 + 0 · 22 + 1 · 21 + 0 · 20 = (100010010)2.
**274 = 125 + 149 = 125 + 125 + 24 = 2 · 125 + 5 + 5 + 5 + 5 + 4 = 2 · 125 + 4 · 5 + 4 =
2 · 53 + 0 · 52 + 4 · 51 + 4 · 50 = (2044)5.
***274 = 49+49+49+49+49+29 = 5·49+29 = 5·49+7+7+7+7+1 = 5·49+4·7+1 =
5 · 72 + 4 · 71 + 1 · 70 = (541)7.
****274 = 81 + 81 + 81 + 31 = 3 · 81 + 31 = 3 · 81 + 9 + 9 + 9 + 4 = 3 · 81 + 3 · 9 + 4 =
3 · 92 + 3 · 91 + 4 · 90 = (334)9.
42. Transformar para a base 10 os seguintes nu´meros
(a) (2351)7
Soluc¸a˜o:(2351)7 = 2·73+3·72+5·7+1 = 2·343+3·49+5·7+1 = 686+147+35+1 = (869)10.
(b) (1001110)2
Soluc¸a˜o: (1001110)2 = 0·20+1·21+1·22+1·23+0·24+0·25+1·26 = 2+4+8+64 = (78)10.
(c) (7706)8
10
Soluc¸a˜o: (7706)8 = 6 ·80+0 ·81+7 ·82+7 ·83 = 6+7 ·64+7 ·512 = 6+448+3584 = 4038.
(d)
(11122)4
Soluc¸a˜o: (11122)4 = 2 · 40 + 2 · 41 + 1 · 42 + 1 · 43 + 1·4 = 2 + 2 · 4 + 16 + 64 + 256 =
2 + 8 + 16 + 64 + 256 = 346.
43. Mostrar que se 2n + 1 e´ um primo ı´mpar, enta˜o n e´ uma poteˆncia de 2.
Soluc¸a˜o: Suponha n 6= 2m, temos n = 2m · pα11 · pα22 · . . . · pαλλ = 2mk. Note que k e´ ı´mpar.
Logo, 2n +1 = 22
mk +1 = (22
m
)k +1 = (22
m
+1)((22
m
)k−1 − (22m )k−2 + (22m )k−3 − . . .−
22
m
+1). Como ((22
m
)k−1 − (22m )k−2︸ ︷︷ ︸
>0
+(22
m
)k−3 − (22m )k−4︸ ︷︷ ︸
>0
+ . . .+(22
m
)2 − 22m︸ ︷︷ ︸
>0
+1) > 1
e 22
m
+ 1 > 1, temos que 2n + 1 e´ composto, absurdo.
44. Provar que se d = (a, b), enta˜o d e´ o nu´mero de inteiros na sequeˆncia a, 2a, 3a, . . ., ba que sa˜o
divisı´veis por b.
Soluc¸a˜o: Se b|ia, para 1 ≤ i ≤ b, temos que ia = tb. Mas a = Ad e b = Bd, com (A,B) =
1. Assim, ia = tb ⇒ iAd = tBd ⇒ iA = tB. Como B - A, temos que B|i. Considere X =
{1, 2, 3, . . . , b}. E´ fato que o nu´mero de elementos em x que sa˜o divisı´veis por B e´ q, onde b = qB. Logo,
b = qB ⇒ Bd = qB ⇒ q = d. Com isso, o nu´mero de inteiros na seuqueˆncia a, 2a, 3a, . . ., ba que sa˜o
divisı´veis por b e´ d.
MA553/Plínio soluções cap.4.pdf
Capítulo 4 (Exercícios) 
 
1. Avaliar (n), (n) e (n) para os seguintes valores de n: a) 10 b) 35 c) 20 d) 512 e) 10000 f) 1234. 
Lembremos as definições: 
(n): Número de divisores positivos de n. 
(n): Soma dos divisores positivos de n. 
(n): Número de elementos menores e relativamente primos com n. 
 Sabemos que: (p) = p  p
  1 e que, se mdc(m, n) = 1, então (m  n) = (m)  (n). 
 
Dessa forma, temos: 
a) Os divisores positivos de 10 são os elementos do conjunto D10 = {1, 2, 5, 10}. 
Os números menores do que 10 relativamente primos com este são os elementos de N, com N = {1, 3, 7, 9}. 
Então: 
 (10) = n(D10) = 4. 
  ∑ 
 
 
 (n) = n(N) = 4. 
 Vejamos que 10 = 2
1
  5
1
, e mdc(2, 5) = 1. Então, 
 (10) = (2
1
  5
1
) = (2
1
)  (5
1
) = (2
1
  2
0
)  (5
1
  5
0
) = 4. 
 
 Os outros itens são análogos. 
 Lembrando que, se N = 
  
  ...  
 
 , o número de divisores positivos é (1 + 1)  (1 + 2)  ...  (1 + k). 
 
2. Para quais valores de m, (m) é ímpar? 
Seja m = 
  
  ...  
 
 . 
Então (m) = ( 
 )  ( 
 )  ...  ( 
 
 ) = ( 
  
  )  ...  ( 
 
  
 
  ) = 
  ...  
 
  (  
 
 
)  ...  (  
 
 
). 
Mas m = 
  
  ...  
 
 . Então, (m) = m  (  
 
 
)  ...  (  
 
 
). 
Vejamos que, com exceção de m = 2, (m) é par se m é par. 
Se m é ímpar, então qualquer pi (da decomposição de m em fatores primos) deve ser ímpar. 
Neste caso,  
 
 
 = 
  
 
 = (pi  1)  
 
 
 é par, uma vez que pi  1 é par. 
Ou seja, (m) é ímpar apenas para m = 1 e m = 2. 
 
3. Para quais valores de m, (m) divide m? 
 
4. Mostrar que se m e n são inteiros positivos tais que m | n, então (m) | (n). 
Sejam m = 
 
  
 
  ...  
 
 e n = 
 
  
 
  ...  
 
 . Se m | n, é claro que i  i, para todo i. 
Dessa forma, todos os fatores primos 
 
 ’s de m d v dem a , ou seja, todos os fatores (  
 
 
)’s de (m) estarão, também, 
em (n). Dessa forma, (n) = n  ∏(  
 
 
) e m | n, então m  ∏(  
 
 
) = (m) | (n). 
∎ 
 
5. Refazer a demonstração do Teorema 4.3 para m = 5 e n = 9. 
Primeiramente, lembremos: 
Teorema 4.3: A função  de Euler é multiplicativa, isto é, (m  n) = (m)  (n), para mdc(m, n) = 1. 
 
Inicialmente, notemos que (5) = 4 e (9) = 6. 
Queremos mostrar que (45) = 24. 
Ora, mas (45) é o número de inteiros positivos que são relativamente primos com 45. 
Sendo que 45 = 3
2
  5, temos que 45 não será relativamente primo com nenhum múltiplo de 3 e com nenhum múltiplo de 5. 
Dessa forma, sendo N o conjunto em questão, temos: 
N = {1, 2, 4, 7, 8, 11, 13, 14, 16, 17, 19, 22, 23, 26, 28, 29, 31, 32, 34, 37, 38, 41, 43, 44}. 
Assim, (45) = |N| = 24, como queríamos provar. 
∎ 
 
 
6. Mostrar que (m) é par se m > 2. 
Demonstração feita no exercício 2. 
 
8. Mostrar que se f é multiplicativa, então f(1) = 1. 
Se f é multiplicativa, então f é não nula. Em vista de que mdc(1, 1) = 1, temos que f(1  1) = f(1) ⇒ [f(1)]2 = f(1), o que implica 
em f(1) = 0 ou f(1) = 1. 
Se f(1) = 0, então, como mdc(1, n) = 1, f(n) = f(n  1) = f(n)  f(1) = 0. Absurdo, pois f é multiplicativa. 
Dessa forma, f(1) = 1. 
∎ 
 
 
10. Mostrar que um inteiro p é um primo se, e somente se, (p) = p + 1. 
(⇒) 
Se p é primo, então os únicos divisores positivos de p são p e 1. Dessa forma, (p) = p + 1. 
(⇐) 
Suponhamos que p seja composto. Isto é, além de 1 e p, p possui outros divisores. Seja S a soma destes divisores. 
Com efeito, (p) = 1 + p + S. 
Porém, por hipótese, temos que (p) = p + 1, ou seja, p + 1 = p + 1 + S, o que implica em S = 0. 
Mas S é a soma dos divisores positivos de p, ou seja, S > 0, o que gera um absurdo. 
Logo, p é primo. 
∎ 
 
 
11. Mostramos que as funções (n) e (n) são multiplicativas. Mostrar que nenhuma delas é completa-
mente multiplicativa. 
Notemos que (n) é o número de divisores positivos de n. 
Tomemos, como exemplo, n = 4 e m = 2. É claro que mdc(m, n)  1. 
Temos, porém, que (2) = 2, (4) = 3 e (8) = 4. 
Com isso, notamos que (8)  (2)  (4), ou seja, que (2  4)  (2)  (4), fazendo com que (n) não seja completamente 
multiplicativa. 
O mesmo exemplo é válido para a função . 
Como (n) é a soma dos divisores positivos de n, temos que: (2) = 3, (4) = 7 e (8) = 15. 
Teremos, então, que (8)  (2)  (4), isto é, (2  4)  (2)  (4), o que mostra que esta também não é completamente 
multiplicativa. 
 
 
 
12. Mostrar que para um inteiro fixo r, a função h(n) = nr é completamente multiplicativa. 
Notemos que, para os inteiros m e n, temos que h(n)  h(m) = n
r
  m
r
 = (n  m)
r
 = h(m  n). h é, portanto, completamente mul-
tiplicativa. 
∎ 
 
 
13. Mostrar que as funções F(n) = f(n)  g(n) e G(n) = f(n)/g(n) são multiplicativas sendo f(n) e g(n) multi-
plicativas com g(n)  0. 
Sejam m e n inteiros. Teremos que: 
F(m  n) = f(m  n)  g(m  n) = [f(n)  f(m)]  [g(n)  g(m)] = [f(m)  g(m)]  [f(n)  g(n)] = F(m)  F(n). 
Logo, F é multiplicativa. 
G(m  n) = f(m  n)/g(m  n) = f(m)  f(n) / g(m)  g(n) = [f(m)/g(m)]  [f(n)/g(n)] = G(m)  G(n). 
Logo, G é multiplicativa. 
∎ 
 
 
14. Mostrar, através de um exemplo, que a função F(n) = ∑ nem sempre é completamente mul-
tiplicativa caso f(d) seja. 
É claro que f(d) = d é multiplicativa. Tomando F(n) = ∑ dd , teremos que F(n) = (n). Porém, já foi mostrado no exercício 
11 que a função (n) não é completamente multiplicativa, o que completa nosso exemplo. 
 
15. Mostrar que para qualquer inteiro positivo n > 1 existem infinitos inteiros m tais que (m) = n. 
Tomemos, como base, o fato de que os primos são infinitos. 
Sendo p primo, tomemos m = p
n  1. Da existência de infinitos primos, temos a existência de f tos m’s dessa forma. 
Sabemos, porém, que (m) = (p
n  1) = (n  1) + 1 = n. 
Dessa forma, existem infinitos valores de m para os quais (m)
= n. 
∎ 
 
 
16. Encontrar o menor inteiro positivo m para o qual (m) = 6. 
Tomemos m = p, com p primo. Caso seja possível encontrar m dessa forma, garantimos que m  m1 = p
  q , com p e q 
primos. A fim de encontrarmos o menor valor de m, essa suposição é plausível. 
Então, (m) = (p) = 
   
  
 = 
   

 
  
 = p + p
  1
 + ... + p + 1. 
Afim de que (m) = 6, deveremos ter p + p
  1 + ... + p + 1 = 6, isto é, p + p
  1
 + ... + p = 5, ou seja, p  (p
  1 + ... + 1) = 5. 
Para tanto, deveremos ter p = 5 e p
  1
 + ... + p + 1 = 1, ou seja,  = 1. Temos, portanto, que m = p
 = 5. 
 
A verificação podia, porém, ter sido feita por testes. 
Temos: (1) = 1, (2) = 3, (3) = 4, (4) = 7 e (5) = 6. 
 
17. Encontrar o menor inteiro positivo m para o qual (m) = 6. 
Analogamente ao exercício anterior, podemos supor m = p, com p primo. Dessa forma, (m) = p  p
  1. 
A fim de que (m) = 6, deveremos ter p  p
  1 = p
  1  (p  1) = 6. Para tanto, teremos: 
 
 
 
 
MA553/Plínio soluções cap.2.pdf
 
 Teoria dos Números  Capítulo 2 (Exercícios) 
 
1. Mostrar que 47 | 223  1. 
Para mostrar que 47 | 2
23
  1, devemos mostrar que 2
23
 ≡ 1 (mod 47). 
Notemos que 2
10
 = 1024 = 37 + 47  21. Ou seja, 2
10
 ≡ 37 (mod 47) ⇒ 210 ≡ 10 (mod 47). 
Então, [2
10
]
2 
≡ (10)
2
 (mod 47) ⇒ 220 ≡ 100 (mod 47) ⇒ 220 ≡ 6 (mod 47) (I) 
Vejamos, agora, que 2
3
 = 8 = 47  39, ou seja, 2
3
 ≡ 39 (mod 47) (II). 
De (I) e (II), (2
20
  2
3
) ≡ 6  (39) (mod 47) ⇒ 223 ≡ 234 (mod 47). 
Mas, 234 = 1  47  5, então 2
23
 ≡ 1 (mod 47). 
 ∎ 
 
2. Encontrar o resto da divisão de 734 por 51 e o resto da divisão de 563 por 29. 
i) Vejamos que 7
2
 ≡ 2 (mod 51). Então, (7
2
)
17
 ≡ (2)
17
 (mod 51) ⇒ 734 ≡ 217 (mod 51). (I) 
Porém, 
 ≡ 
 ≡ 
 } ⇒ 210  27 ≡ 4  26 (mod 51) ⇒ 217 ≡ 104 (mod 51) ⇒ 217 ≡ 2 (mod 51). 
Dessa forma, 2
17
 ≡ 2 (mod 51) ⇒ 217 ≡ 49 (mod 51). (II) 
De (I) e (II), temos que 7
34
 ≡ 49 (mod 51), o que indica que o resto da divisão de 7
34
 por 51 é 49. 
 
ii) Notemos que 5
3
 ≡ 9 (mod 29), o que nos dá: 5
63
 ≡ 9
21
 (mod 29). Como 9 = 3
2
, 5
63
 ≡ 3
42
 (mod 29) (I) 
Mas, 3
3
 ≡ 2 (mod 29) ⇒ 342 ≡ (2)16 (mod 29) ⇒ 342 ≡ 216 (mod 29) (II) 
No entanto, 2
8
 ≡ 13 (mod 29) ⇒ (28)2 ≡ 132 (mod 29) ⇒ 216 ≡ 169 (mod 29) ⇒ 216 ≡ 24 (mod 29) (III). 
De (I), (II) e (III), temos que 5
63
 ≡ 24 (mod 29), ou seja, o resto da divisão de 5
63
 por 29 é 24. 
 
3. Mostrar que se p é um ímpar e a2 + 2b2 = 2p, então “a” é par e “b” é ímpar. 
Teremos 4 casos: 
1º Caso: “a” par e “b” par 
Dessa forma, teremos: a = 2x e b = 2y (x e y inteiros). 
Então, a
2
 + 2b
2
 = 4x
2
 + 8y
2
 = 4(x
2
 + 2y
2
). 
Já que a
2
 + 2b
2
 = 2p, temos que 4(x
2
 + 2y
2
) = 2p ⇒ p = 2(x2 + 2y2), o que é um absurdo, pois p é ímpar. 
2º Caso: “a” ímpar e “b” par 
Dessa forma, teremos: a = 2x + 1 e b = 2y (x e y inteiros). 
Então, a
2
 + 2b
2
 = (2x + 1)
2
 + 2(2y)
2
 = 4(x
2
 + 4x + y
2
) + 1, o que é absurdo, pois a
2
 + 2b
2
 = 2p. 
3º Caso: “a” ímpar e “b” ímpar 
Dessa forma, teremos a = 2x + 1 e b = 2y + 1 (x e y inteiros) 
Então, a
2
 + 2b
2
 = (2x + 1)
2
 + 2(2y + 1)
2
 = 2(2x
2
 + 2x + 4y
2
 + 4y + 1) + 1, o que é absurdo, analogamente ao caso 2. 
4º Caso: “a” par e “b” ímpar 
Dessa forma, teremos a = 2x e b = 2y + 1 (x e y inteiros). 
Então, a
2
 + 2b
2
 = (2x)
2
 + 2(2y + 1)
2
 = 2(2x
2
 + 4y
2
 + 4y + 1). 
Dessa forma, teríamos que p = 2x
2
 + 4y
2
 + 4y + 1, verificando o fato de p ser ímpar. 
 
D s cas s , , 3 e , tere s que, para “p” í par, a
2
 + 2b
2
 = 2p somente para “a” par e “b” í par. 
 ∎ 
4. Provar que para p primo (p  1)! ≡ p  1 (mod 1 + 2 + ... + (p  1)). 
Notemos que: 
(p  1) ≡  1 (mod p) e (p  1)! ≡ 1 (mod p) (Teorema de Wilson). 
Pela transitividade, teremos que: (p  1)! ≡ p  1 (mod p). 
Isso nos mostra que p | (p  1)!  (p  1). 
Temos, também, que (p  1)!  (p  1) = (p  1)  [(p  2)!  1], ou seja, p  1 | (p  1)!  (p  1). 
Disso, segue que 
 p  
 
 | (p  1)!  (p  1). 
Como p e 
 p  
 
 são primos entre si, temos que p  
 p  
 
 | (p  1)!  (p  1), ou seja, (p  1)! ≡ p  1 ( p 
 p  
 
). 
Notando, porém, que 1 + 2 + ... + (p  1) = p  
 p  
 
, tem-se provado o resultado. 
∎ 
 
5. Encontrar o máximo divisor comum de (p  1)!  1 e p! (primo). 
Se p = 2, teremos que (p  1)!  1 = 0 e p! = 2, ou seja, mdc((p  1)!  1, p!) = mdc(0, 2) = 2. 
Se p = 3, teremos que (p  1)!  1 = 1, ou seja, mdc((p 1)!  1) = 1. Suponhamos, então, p  2. 
Seja d um divisor comum de (p  1)!  1 e de p!. 
Notemos que, se d = p, então d  (p  1)!  1. Consideremos, portanto, d  p. 
Como d | p! = p  (p  1)! e d  p, então d | (p  1)!. 
Mas d | (p  1)!  1, por hipótese. Se d | (p  1)! e d | (p  1)!  1, então d | 1, logo d = 1. 
Então, mdc((p  1)!  1, p!) = 1, se |p|  2 e mdc((p  1)!  1, p!) = 2, se |p| = 2. 
 
Nota: Do Teorema de Wilson, p | (p  1)! + 1. Dessa forma, se p | (p  1)!  1 = (p  1)! + 1  2, então p divide a 2, ou seja, 
p = 2. 
 
6. Mostrar que para n  4 o resto da divisão por 12 de 1! + 2! + ... + n! é 9. 
Queremos provar que, para n  4, o resto da divisão de 1! + 2! + ... + n! por 12 é 9. Ou seja, se N = 1! + 2! + ... + n!, 
queremos mostrar que N ≡ 9 (mod 12). 
Notemos que 1! + 2! + 3! = 9, e que 4! = 24. 
Então, 1! + 2! + 3! + 4! + ... + n! = 9 + (4! + 5! + ... + n!) = 9 + 4!(1 + 5 + 6  5 + ... + n  (n  1)  ...  6  5). 
Então, para n  4, teremos que 1! + 2! + 3! + ... + n! = 9 + 4! . k. Porém, 4! = 24 = 12  2. Então, 12 | 4!  k (k inteiro). 
Sendo assim, podemos escrever: 1! + 2! + 3! + ... + n! = 9 + 12  m (m ∈ ℤ), para n  4. 
Logo, se N = 1! + 2! + 3! + ... + n! = 9 + 12  m, então N ≡ 9 (mod 12), tendo provado o resultado. 
∎ 
 
7. Mostrar que para n inteiro 3n2  1 nunca é um quadrado. 
Notemos que 3n
2
  1 = 3n
2
  3 + 2 = 3(n  1)(n + 1) + 2 = 3k + 2. 
Basta mostrarmos que nenhum quadrado é da forma 3k + 2. 
Um número t, qualquer, pode ser das formas: t = 3k, t = 3k + 1 ou t = 3k + 2. Então, 
(I) t = 3k ⇒ t2 = 9k2 = 3  (3k2) = 3k1 
(II) t = 3k + 1⇒ t2 = (3k + 1)2 = 9k2 + 6k + 1 = 3k2 + 1 
(III) t = 3k + 2 ⇒ t2 = (3k + 2)2 = 9k2 + 12k + 4 = 3k2 + 1. 
Dessa forma, temos provado que um quadrado nunca é da forma 3k + 2 e, consequentemente, que 3n
2
  1 nunca é um 
quadrado. 
8. Resolver as seguintes congruências. 
(a) 5x ≡ 3 (mod 24) 
Vejamos que, existe y inteiro tal que: 5x = 3 + 24y, ou seja, 5x  24y = 3. 
Procuramos, portanto, soluções para essa Equação Diofantina. 
Vejamos que: 5  5  24 = 1 ⇒ (3  5)  5  3  24 = 3 ⇒ x = 15 e y = 3 é uma solução particular. 
Dessa forma, 5  (x  15)  24  (y  3) = 0 ⇒ x = 15 + 
   3 
 
 ⇒ y = 3 + 5  k ⇒ x = 15 + 24  k ⇒ x ≡ 15 (mod 24) 
Vejamos, porém, que, dada a equação ax + by = c, com d = mdc(a, b), se d | c, então para uma solução particular x = x0, 
teremos que: x = x0 + (
 b 
 
)  k (k ∈ ℤ). 
Para a nossa
equação 5x  24y = 3, teremos que d = mdc(5, 24) = 1. Para x0 = 15, teremos: x = 15 + (
  
 
)  k = 15  24  k. 
Isso nos dá a solução x ≡ 15 (mod 24). 
 
(b) 3x ≡ 1 (mod 10) 
Queremos encontrar a solução da equação 3x  10y = 1. Notemos que mdc(3, 10) = 1 | 1. 
Vejamos que x = 3 e y = 1 é uma solução particular. Dessa forma, 
3  (x + 3)  10  (y + 1) = 1 ⇒ x = 3 + 
  
3
 ⇒ x = 3 + 10  k (k inteiro) ⇒ x ≡ 3 (mod 10) ⇒ x ≡ 7 (mod 10). 
 
(c) 23x ≡ 7 (mod 19) 
Queremos encontrar a solução da equação 23x  19y = 7. Vejamos que mdc(23, 19) = 1 | 7. Isso garante a existência da 
solução. 
Notemos que, 23 = 19 + 4, que 19 = 3  4 + 7, então, multiplicando a primeira igualdade por 3, teremos: 
3  23 = 3  19 + 3  4 = 3  19 + (19  7) ⇒ 3  23 + 4  19 = 7, dessa forma x = 3 e y = 4 é uma solução particular. 
Teremos, então, que 23(x + 3)  19(y + 4) = 0, o que nos dá: x =  3 + 
  
 3
 ⇒ x = 3 + 19  k (k inteiro). 
O que nos dá, como solução, a classe de congruências: x ≡ 3 (mod 19), ou seja, x ≡ 16 (mod 19). 
 
(d) 7x ≡ 5 (mod 18) 
Vejamos que mdc(7, 18) = 1 | 5, então existe solução. Dessa forma, queremos a solução da equação 7x  18y = 5. 
Temos que: 18  2  7 = 4, ou seja, 3  18  6  7 = 3  4 = 12 = (7 + 5). Então, 3  18  7  7 = 5. Assim, uma solução particular 
para a equação é x = 7 e y = 3. 
Então, 7  (x + 7)  18  (y + 3) = 0, ou seja, x = 7 + 18  k (k inteiro). 
As soluções são tais que x ≡ 7 (mod 18) ≡ 11 (mod 18) ⇒ x ≡ 11 (mod 18). 
 
(e) 25x ≡ 15 (mod 120) 
Vejamos que mdc(25, 18) = 5 | 15. Dessa forma, existem 5 soluções. 
Notemos que 25x  120y = 15 é tal que 5x  24y = 3 e, do item (a), temos que x = 15 (e y = 3) é uma solução particular. 
Dessa forma, x = 15 + 
 
 
  k, para k inteiro. Serão, então, mais 4 soluções. Ou seja, 
x1 = 15 + 
 
 
  1 = 39, x2 = 15 + 
 
 
  2 = 63, x3 = 15 + 
 
 
  3 = 87 e x4 = 15 + 
 
 
  4 = 111. 
Dessa forma, teremos as soluções: 
x ≡ 15 (mod 120), x ≡ 39 (mod 120), x ≡ 63 (mod 120), x ≡ 87 (mod 120) e x ≡ 111 (mod 120). 
 
9. Mostrar que 5n3 + 7n5 ≡ 0 (mod 12) para todo inteiro n. 
Notemos, inicialmente, que: 5 ≡ 7 (mod 12) e 7 ≡ 5 (mod 12). Teremos, então: 
(I) Se n ≡ 0 (mod 12) ⇒ { 
 3 ≡ 
 ≡ 
 ⇒ { 
 3 ≡ 
 ≡ 
 ⇒ 5n3 + 7n5 ≡ 0 (mod 12) 
(II) Se n ≡ 1 (mod 12) ⇒ { 
 3 ≡ 
 ≡ 
 ⇒ { 
 3 ≡  
 ≡  
 ⇒ 5n3 + 7n5 ≡ 12 (mod 12) ⇒ 5n3 + 7n5 ≡ 0 (mod 12) 
(III) Se n ≡ 2 (mod 12) ⇒ { 
 3 ≡ 
 ≡ 3 ≡ 
 ⇒ { 
 3≡  ≡ 
 ≡  ≡ 
 ⇒ 5n3 + 7n5 ≡ 0 (mod 12) 
(IV) Se n ≡ 3 (mod 12) ⇒ { 
 3 ≡ ≡ 3 
 ≡ 3 ≡ 3 
 ⇒ { 
 3≡  ≡ 3 
 ≡  ≡ 3 
 ⇒ 5n3 + 7n5 ≡ 0 (mod 12) 
(V) Se n ≡ 4 (mod 12) ⇒ { 
 3 ≡ ≡ 
 ≡ ≡ 
 ⇒ { 
 3≡  ≡ 
 ≡  ≡ 
 ⇒ 5n3 + 7n5 ≡ 0 (mod 12) 
(VI) Se n ≡ 5 (mod 12) ⇒ { 
 3 ≡ ≡ 
 ≡ 3 ≡ 
 ⇒ { 
 3≡ 3 ≡ 
 ≡  ≡ 
 
(Basta continuar a verificação para n ≡ 6 (mod 12), n ≡ 7 (mod 12), n ≡ 8 (mod 12), n ≡ 9 (mod 12), n ≡ 10 (mod 12) e 
n ≡ 11 (mod 12)) 
∎ 
Uma outra forma de pensar, é notar que 5 = 12  7. Ou seja, 5n
3
 + 7n
5
 = (12  7)n
3
 + 7n
5
 = 12n
3
 + 7  (n
5
  n
3
). 
Dessa forma, como 7 é primo, devemos mostrar que n
5
  n
3
 é divisível por 12. 
Para tanto, basta mostrarmos que n
5
  n
3
 é divisível por 3 e por 4. 
Se 3 | n, nada temos a provar. Suponhamos, então, que 3  n. Então n ≡ 1 (mod 3) ou n ≡ 2 (mod 3). 
Se n ≡ 1 (mod 3), então n
5
 ≡ 1 (mod 3) e n
3
 ≡ 1 (mod 3). Dessa forma, n
5
  n
3
 ≡ 0 (mod 3), ou seja, 3 | n
5
  n
3
. 
Se n ≡ 2 (mod 3), então n
5
 ≡ 2 (mod 3) e n
3
 ≡ 2 (mod 3). Dessa forma, n
5
  n
3
 ≡ 0 (mod 3). 
Provemos agora que 4 | n
5
  n
3
. Ora, n
5
  n
3
 = n
2
  (n
3
  n). Ou seja, se n é par, 4 | n
2
 e, portanto, 4 | n
5
  n
3
. 
Suponhamos, então, n ímpar. Então, n ≡ 1 (mod 4) ou n ≡ 3 (mod 4). 
Se n ≡ 1 (mod 4), então n
5
  n
3
 ≡ 0 (mod 4). 
Se n ≡ 3 (mod 4), então n
5
 ≡ 243 (mod 4) ≡ 3 (mod 4) e n
3
 ≡ 27 (mod 4) ≡ 3 (mod 4). Então n
5
  n
3
 ≡ 0 (mod 4). 
Dessa forma, n
5
  n
3
 é divisível por 4. 
Se 3 | n
5
  n
3
 e 4 | n
5
  n
3
, então 12 | n
5
  n
3
, logo 12 | 5n
3
 + 7n
5
 e, portanto, 5n
3
 + 7n
5
 ≡ 0 (mod 12). 
∎ 
 
10. Seja f(x) = a0 + a1x + ... + anx
n um polinômio com coeficientes inteiros onde an > 0 e n  1. Mostrar 
que f(x) é composto para infinitos valores da variável x. 
 
11. Mostrar que se p1 e p2 são primos tais que p2 = p1 + 2 e p1 > 3, então p1 + p2 ≡ 0 (mod 12). 
Vejamos que, dividindo um número por, obtemos números da forma 6k, 6k + 1, 6k + 2, 6k + 3, 6k + 4 e 6k + 5. Notemos, 
também, que 6k, 6k + 2, 6k + 3 e 6k + 4 não são primos. Dessa forma, os números primos são da forma 6k + 1 ou 6k + 5. 
Como p1 > 3, então p1  5, ou seja, p2  7. Então: 
Se p1 = 6k + 5, então p2 = 6k + 7, ou seja, p1 + p2 = 12k + 12 = 12(k + 1). Então, p1 + p2 ≡ 0 (mod 12). 
Se p2 = 6k + 1, então p1 = 6k  1, ou seja, p1 + p2 = 12k. Então, p1 + p2 ≡ 0 (mod 12). 
∎ 
 
Observação: Notemos que: 
Se p1 = 6k + 1, então p2 = 6k + 3 (Absurdo, pois p2 é primo). 
Se p2 = 6k + 5, então p1 = 6k + 3 (Absurdo, pois p1 é primo). 
 
12. Mostrar que para a e b inteiros temos que 3 | (a2 + b2) ⇒ 3 | a e 3 | b. 
Suponhamos que 3 não divida a pelo menos um entre a e b (suponhamos que 3  a, sem perda de generalidade). Teremos, 
assim, 6 casos para analisar: 
(I) a ≡ 1 (mod 3) e b ≡ 0 (mod 3). 
Dessa forma, { 
a ≡ 3 
b ≡ 3 
 ⇒ a2 + b2 ≡ 0 (mod 3) ⇒ 3  a2 + b2 (Absurdo!). 
(II) a ≡ 1 (mod 3) e b ≡ 1 (mod 3). 
Dessa forma, { 
a ≡ 3 
b ≡ 3 
 ⇒ a2 + b2 ≡ 2 (mod 3) ⇒ 3  a2 + b2 (Absurdo!). 
(III) a ≡ 1 (mod 3) e b ≡ 2 (mod 3). 
Dessa forma, { 
a ≡ 3 
b ≡ 3 ≡ 3 
 ⇒ a2 + b2 ≡ 2 (mod 3) ⇒ 3  a2 + b2 (Absurdo!). 
(IV) a ≡ 2 (mod 3) e b ≡ 0 (mod 3). 
Dessa forma, { 
a ≡ 3 ≡ 3 
b ≡ 3 
 ⇒ a2 + b2 ≡ 1 (mod 3) ⇒ 3  a2 + b2 (Absurdo!). 
(V) a ≡ 2 (mod 3) e b ≡ 1 (mod 3). 
Dessa forma, { 
a ≡ 3 ≡ 3 
b ≡ 3 
 ⇒ a2 + b2 ≡ 2 (mod 3) ⇒ 3  a2 + b2 (Absurdo!). 
 
 
(VI) a ≡ 2 (mod 3) e b ≡ 2 (mod 3). 
Dessa forma, { 
a ≡ 3 ≡ 3 
b ≡ 3 ≡ 3 
 ⇒ a2 + b2 ≡ 2 (mod 3) ⇒ 3  a2 + b2 (Absurdo!). 
 
É, então, absurdo supor que 3  a ou 3  b, então 3 | a e 3 | b. 
∎ 
 
13. Sejam p1, p2 e p3 primos tais que p = (p1)
2 + (p2)
2 + (p3)
2 é primo. Mostrar que algum dos pi’s é igual a 
3. 
Suponhamos que nenhum dos pi’s seja igual a 3. Ist é, pi ≡ 1 (mod 3) ou pi ≡ 2 (mod 3). 
Notemos que, se x ≡ 1 (mod 3), então x
2
 ≡ 1 (mod 3). Se x ≡ 2 (mod 3), então x
2
 ≡ 4 (mod 3) ≡ 1 (mod 3). 
Dessa forma, (pi)
2
 ≡ 1 (mod 3). 
Então, (p1)
2
 + (p2)
2
 + (p3)
2
 = 1 + 1 + 1 (mod 3) ⇒ p ≡ 3 (mod 3) ⇒
p ≡ 0 (mod 3). 
Vejamos que pi  2, então p  6. Sendo p primo, temos que p ≡ 0 (mod 3) implica em p = 3, o que é absurdo, pois p  6. 
Dessa forma, ao menos um dos pi’s eve ser congruente a 0 módulo 3. Sendo que os pi’s sã pri s, e tã a e s u 
deles deve ser igual a 3. 
∎ 
 
14. Mostrar que 3x2 + 4x2 ≡ 3 (mod 5) é equivalente a 3x2  x2 + 2 ≡ 0 (mod 5). 
Vejamos que: { 
 ≡  
3 ≡  
 
Dessa forma, 3x
2
 + 4x
2
 ≡ 3 (mod 5) é equivalente a 3x
2
  x
2
 ≡ 2 (mod 5), ou melhor, 3x
2
  x
2
 + 2 ≡ 0 (mod 5). 
 
 
15. Mostrar que p | (
p 
 
) , onde 0 < k < p . 
Notemos que, (
p 
 
) = 
 p 
  p  
 = 
 p  p
 
 
  p  
 = p  
 p
 
  p
 
  p
 
 3 p
 
 
 
 = p  m (m ∈ ℤ). 
Então, claramente p | p  m = p  p 
  1  m, dessa forma, p | (
p 
 
). 
∎ 
 
18. Mostrar que 310 ≡ 1 (mod 112). 
Vejamos que 3
5
 ≡ 1 (mod 242), isto é, 3
5
 ≡ 1 (mod 11
2
). Dessa forma, tem-se imediatamente, que 3
10
 ≡ 1 (mod 11
2
). 
∎ 
 
19. Resolver os seguintes sistemas. 
a) {
 ≡ 1 mo 2 
 ≡ 2 mo 3 
 ≡ 5 mo 
 
 
Inicialmente, notemos que m = 2  3  7 = 42 
(I) Temos que: y1 = 
 
 
 = 21 
Além disso, ̅ é solução particular de y1  x ≡ 1 (mod 2), ou seja, 21x ≡ 1 (mod 2), ou seja, ̅ = 1. 
(II) Temos que: y2 = 
 
3
 = 14 
Além disso, ̅ é solução particular de y2  x ≡ 1 (mod 3), ou seja, 14x ≡ 1 (mod 3), ou seja, ̅ = 2. 
(III) Temos que: y3 = 
 
 
 = 6 
Além disso, 3̅ é solução particular de y3  x ≡ 1 (mod 7), ou seja, 6x ≡ 1 (mod 7), ou seja, 3̅ = 6. 
 ssa s lu ã é, p rta t , ≡ ∑ bi i i̅ 
3
i 
 
 Então, x ≡ 257 (mod 42), ou seja, x ≡ 5 (mod 42). 
 
Os outros sistemas são análogos. Lembrar que, por exemplo, a congruência 2x ≡ 1 (mod 5) equivale a x ≡ 3 (mod 5). 
 
21. Mostrar que a7 ≡ a (mod 21) para todo inteiro a. 
Basta mostrarmos que a
7
  a é divisível por 7 e por 3. 
Mostremos, inicialmente, que 7 | a
7
  a. 
Notemos que a
7
  a = a  (a
6
  1). Se 7 | a, nada temos a provar. Suponhamos, então, que 7  a. Dessa forma, do Pequeno 
Teorema de Fermat, temos que a
7  1 ≡ 1 (mod 7), ou seja, 7 | a
6
  1, o que prova que 7 | a
7
  a. 
Vejamos, também, que a
7
  a = a  (a
6
  1) = a  (a
3 
 1)  (a
3
 + 1) = (a  1)  a  (a + 1)  (a
2
  a + 1)  (a
2
 + a + 1). É claro que um 
dos fatores (a  1), a ou (a + 1) é divisível por 3, dessa forma, a
7
  a é divisível por 3. 
Conclui-se, então, que 7 | a
7
  a e 3 | a
7
  a, ou seja, 21 | a
7
  a, e, portanto, a
7
 ≡ a (mod 21). 
∎ 
 
 
 
22. Mostrar que para a e b inteiros, com mdc(a, b) = 1 temos: 
a(b) + b(a) ≡ 1 (mod ab). 
 
Vejamos que, como mdc(a, b) = 1, temos, do Teorema de Euler, que a
(b)
 ≡ 1 (mod b) e b
(a)
 ≡ 1 (mod a). 
Ou seja, temos que b | a
(b)
  1 e a | b
(a)
  1. 
Assim, ab | (a
(b)
  1)  (b
(a)
  1) = a
(b)
  b
(a)
  a
(b)
  b
(a)
 + 1. 
Porém, ab | a
(b)
  b
(a)
. Dessa forma, deveremos que ter que ab |  a
(b)
  b
(a)
 + 1 ou melhor, ab | a
(b)
 + b
(a)
  1. 
Isso implica que a
(b)
 + b
(a)
 ≡ 1 (mod ab). 
∎ 
 
23. Provar ou dar um contra exemplo: “Se a e m são inteiros, mdc(a, m) = 1, então 
m | (1 + a + a2 + ... + a(m)  1) “ 
Como mdc(a, m) = 1, o Teorema de Euler nos garante que a
(m) 
 ≡ 1 (mod m). Ou seja, m | a
(m)
  1. 
Mas, a
(m)
  1 = (a  1)  (a
(m)  1 + ... + a
2
 + a + 1). 
Ou seja, mdc(a, m) = 1 ⇒ m | (a  1)  (1 + a + a2 + ... + a(m)  1). 
Assim, se m | a  1, não podemos afirmar que m | (1 + a
2
 + ... + a
(m)  1). 
Para um contra exemplo, é necessário tomarmos a e m tais que a ≡ 1 (mod m). Tomemos, por exemplo, a = 3 e m = 2. 
Dessa forma, (2) = 1, ou seja, teremos que 2  3(2)  1) = 1, contrariando a afirmação inicial. 
 
24. Mostrar que se p e q são primos, p  q  5, então p2  q2 ≡ 0 (mod 24). 
Devemos verificar que 3 | p
2
  q
2
 e 8 | p
2
  q
2
. 
Como p e q são maiores que ou iguais a 5, então ambos são ímpares. Vejamos que, se p = 2k + 1, então p
2
 = 4k
2
 + 4k + 1, ou 
melhor, p
2
 = 4k  (k + 1) + 1. Porém, k  (k + 1) = 2k1, ou seja, p
2
 = 8k1 + 1. O que nos leva a atribuir q
2
 = 8k2 + 1. 
Então, p
2
  q
2
 = 8  (k1  k2), ou seja, 8 | p
2
  q
2
. 
Basta verificarmos, agora, que 3 | p
2
  q
2
. Ora, nas condições dadas, temos que p e q não são múltiplos de 3. Então, temos, 
por exemplo, p ≡ 1 (mod 3) ou p ≡ 2 (mod 3). 
Já verificamos anteriormente, que se x ≡ 1 (mod 3), então x
2
 ≡ 1 (mod 3) e que se x ≡ 2 (mod 3), então x
2
 ≡ 1 (mod 3). 
Dessa forma, teremos que p
2
 ≡ 1 (mod 3) e, consequentemente, q
2
 ≡ 1 (mod 3). 
Assim, p
2
  q
2
 ≡ 0 (mod 3), ou seja, 3 | p
2
  q
2
. Isso implica, portanto, que 24 | p
2
  q
2
, ou melhor, p
2
  q
2
 ≡ 0 (mod 24). 
∎ 
 
 
Capitulo 1: Mostrar que 2n + 1 nunca é um cubo. 
 
Para tanto, suponhamos 2
n
 + 1 = k
3
. 
Dessa forma, 2
n
 = k
3
  1 = (k  1)(k
2
 + k + 1). 
Vejamos que k
2
 + k + 1 = k  (k + 1) + 1 
Necessariamente, k  (k + 1) é par, o que faz com que k  (k + 1) + 1 seja ímpar. 
Isso é um absurdo, pois 2
n
 = (k  1)  (k
2
 + k + 1), ou seja, k
2
 + k + 1 é um dos fatores de 2
n
 e 2
n
 (por ser uma potência de 2) 
apresenta apenas fatores iguais a 2. 
Então, 2
n
 + 1  k
3
, para todo inteiro k, isto é, 2
n
 + 1 não pode ser um cubo. 
∎