Buscar

Problemas em Teoria dos Números (Resolvidos e Propostos) do prof Diego Marques

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 132 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 132 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 132 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

:,· 
JOSÉ PLÍNIO DE OLIVEIRA SANTOS 
DIEGO MARQUES 
PROBLEMAS EM , 
TEORIA DOS NU MEROS 
_, (RESOLVI DOS E PROPOSTOS) 
i: ..... ··. 
t~·-· -~ .· .. 
t .. ,... ,-,. 
L~~ ... --:~ ,-·_ . 
....... -· 
Este livro destina-se a · 
alunos de graduação em 
Matemática (bacharelado 
e licencia~ra) e também 
aos que se preparam para 
olimpíadas de 
Matemática. 
I 
I 
J 
l 
·l 
JOSÉ PLÍNIO DE OLIVEIRA SANTOS 
DIEGO MARQUES 
PROBLEMAS EM , 
TEORIA DOS NU MEROS 
(RESOLVIDOS E PROPOSTOS) 
c================================------ --- ---
JOSÉ PLÍNIO DE OLIVEIRA SANTOS 
DIEGO MARQUES 
PROBLEMAS EM , 
TEORIA DOS NUM EROS 
(RESOLVIDOS E PROPOSTOS) 
" .. EDITORA 
\itYJ CIÊNCIA MODERNA 
Problemas em Teoria dos Números (Resolvidos e Propostos) 
Copyright@J Editora Ciência Moderna Ltda., 2017 
Todos os direitos para a língua portuguesa reservados pela EDITORA CI~NCIA MODERNA L TDA. 
De acordo com a Lei 9.61 O, de 19/2/1998, nenhuma parte deste livro poderá ser reproduzida, transmitida e 
gravada, por qualquer meio eletrônico, mecânico, por fotocópia e outros, sem a prévia autorização, por 
escrito, da Editora. 
Editor: Paulo André P. Marques 
Produção Editorial: Dilene Sandes Pessanha 
Capa: Daniel Jara 
Copidesque: Equipe Ciência Moderna 
Várias Marcas Registradas aparecem no decorrer deste livro. Mais do que simplesmente listar esses 
nomes e informar quem possui seus direitos de exploração, ou ainda imprimir os logotipos das mesmas, o 
editor declara estar utilizando tais nomes apenas para fins editoriais, em beií.éfído exclusivo do dono da 
Marca Registrada, sem intenção de infringir as regras de sua utilização .. Qualquer semelhança em nomes 
próprios e acontecimentos será mera coincidência. 
FICHA CATALOGRAFICA 
SANTOS, José Plínio de Oliveira; FERREIRA; Ofego Marques. 
Problemas em Teoria dos Números (Resolvidos e Propostos) 
Rio de Janeiro: Editora Ciência Moderna Ltda., 2017. 
1. Matemática 2. Álgebra 
1- Título 
ISBN: 978-85-399-0894-3 
Editora Ciência Moderna Ltda. 
R. Alice Figueiredo, 46 - Riachuelo 
Rio de Janeiro, RJ - Brasil CEP: 20.950-150 
Tel: (21) 2201-6662/ Fax: (21) 2201-6896 
E-MAJL: LCM@LCM.COM.BR 
WWW.LCM.COM.BR 
CDD 510 
512 
04/17 
Prefácio 
O primeiro autor, do presente livro, publicou, na coleção Matemática Universitária do IMPA, o 
livro Introdução à Teoria dos Números onde, além de vários problemas resolvidos são propostos 
muitos outros. 
Nossa proposta inicial, para o presente livro, era apenas a de fornecer as soluções para todos aqueles 
problemas propostos no livro acima mencionado. Dado o grande interesse que estes tópicos despertam 
nos estudantes e a procura por soluções, decidimos pela inclusão de vários outros problemas resolvidos 
e uma pequena coleção de exercícios propostos. 
Desta forma o livro ficou dividido em três capítulos, cada um, por sua vez, dividido em nove seções 
correspondentes a cada um dos nove capítulos em que o livro original está dividido. 
No primeiro capítulo estão as soluções para todos os problemas do referido livro. No segundo estão 
problemas correspondentes aos conteúdos dos nove capítulos. com as correspondentes soluções e no 
terceiro, colocamos nove pequenaS listas de exercícios propostos mas sem soluções. 
No total são 312 problemas resolvidos e 137 problemas propostos. 
Esperamos, desta forma, que o presente texto possa contribuir, um pouco mais, nesta área tão 
importante da matemática ao trazer este material em língua portuguesa. 
Sumário 
1 Problemas resolvidos 
1.1 Divisibilidade 
Problemas resolvidos do Capítulo ·1 
1.2 Congruência 
Problemas resolvidos do Capítulo 2 
1.3 Teoria combinatória dos números 
Problemas resolvidos do Capítulo 3 
1.4 Funções Aritméticas 
Problemas resolvidos do Capítulo 4 
1.5 Resíduos Quadráticos 
Problemas resolvidos do Capítulo 5 
1.6 Raízes Primitivas 
Problemas resolvidos do Capítulo 6 
o •• o •••• o o ••• o o • o •• o o 
1. 7 Representação de inteiros como soma de quadrados 
Problemas resolvidos do Capítulo 7 . . . . . 
1.8 Frações Contínuas 
Problemas resolvidos do Capítulo 8 
1.9 Partições 
o • o o •••••• o •• o • o ••• o o • o •• 
Problemas resolvidos do Capítulo 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . 
2 Problemas suplementares 
2.1 Divisibilidade 
Problemas suplementares referentes ao Capítulo 1 
2.1.1 Solução dos Problemas Suplementares ..... 
2.2 Congruência 
Problemas suplementares referentes ao Capítulo 2 
2.2.1 Solução dos Problemas Suplementares ..... 
2.3 Teoria combinatória dos números 
Problemas suplementares referentes ao Capítulo 3 
2.3.1 Solução dos Problemas Suplementares ..... 
2.4 Funções Aritméticas 
Problemas suplementares referentes ao Capítulo 4 
2.4.1 Solução dos Problemas Suplementares ..... 
2.5 Resíduos Quadráticos 
Problemas suplementares referentes ao Capítulo 5 
2.5.1 Solução dos Problemas Suplementares ..... 
1 
1 
21 
29 
32 
39 
44 
46 
48 
50 
55 
55 
58 
69 
70 
75 
76 
78 
79 
83 
85 
viii Problemas em Teoria dos Números (Resolvidos e Propostos) 
2.6 Raízes Primitivas 
Problemas suplementares referentes ao Capítulo 6 
2.6.1 Solução dos Problemas Suplementares ..... 
2. 7 Representação de inteiros como soma de quadrados 
Problemas suplementares referentes ao Capítulo 7 
2. 7.1 Solução dos Problemas Suplementares . . . . . 
2.8 Frações Contínuas 
Problemas suplementares referentes ao Capítulo 8 
2.8.1 Solução dos Problemas Suplementares ..... 
2.9 Partições 
Problemas suplementares referentes ao Capítulo 9 
2.9.1 Solução dos Problemas Suplementares ..... 
3 Problemas propostos 
3.1 Divisibilidade 
Problemas propostos referentes ao Capítulo 1 
3.2 Congruência 
3.3 
3.4 
3.5 
3.6 
3.7 
3.8 
3.9 
Problemas propostos referentes ao Capítulo 2 
Teoria combinatória dos números 
Problemas propostos referentes ao Capítulo 3 
Funções Aritméticas 
Problemas propostos referentes ao Capítulo 4 
Resíduos Quadráticos 
Problemas propostos referentes ao Capítuio 5 
Raízes Primitivas 
Problemas propostos referentes ao Capítulo 6 
Representação de inteiros como soma de quadrados 
Problemas propostos referentes ao Capítulo 7 
Frações Contínuas 
Problemas propostos referentes ao Capítulo 8 
Partições 
Problemas propostos referentes ao Capítulo 9 
88 
89 
91 
92 
94 
95 
98 
99 
105 
105 
108 
109 
110 
111 
111 
112 
113 
113 
Capítulo 1 
Problemas resolvidos 
1.1 Divisibilidade 
Problemas resolvidos do Capítulo 1 
1. Encontrar, usando o algoritmo de Euclides, o máximo divisor comum dos seguintes pares de 
números: 
(a) 542 e 234 
(b) 9652 e 252 
(c) 24573 e 1387 
( d) 4276 e 1234 
(e) 48762 e 176 
(f) 42516 e 97421 
(g) 8374 e 24517 
(h) 35262 e 12753 
Solução: 
(a) Temos, 
logo (542, 234) = 2. 
(b) Temos, 
logo (9652, 252) = 4. 
542 = 2 . 234 + 7 4 
234 = 3 . 7 4 + 12 
74=6·12+2 
12 = 6. 2 
9652 = 38 . 252 + 76 
252 = 3 . 76 + 24 
76 = 3. 24+ 4 
24=6·4 
2 Problemas em Teoria dos Números (Resolvidos e Propostos) 
(c) Temos, 
logo (24573, 1387) = 1. 
(d) Temos, 
logo (4276, 1234) = 2. 
(e) Temos, 
logo ( 48762, 176) = 2. 
(f) Temos, 
logo (42516, 97421) = 1. 
24573 . 17 ·1387 + 994 
1387 = 1 . 994 + 393 
994 = 2 . 393 + 208 
393 = 1 . 208 + 185 
208 = 1. 185 + 23 
185 = 8. 23 + 1 
23 = 1· 23 
4276 = 3. 1234 + 574 
1234 = 2 . 57 4 + 86 
57 4 = 6 . 86 + 58 
86 = 1. 58+ 28 
58= 2. 28 + 2 
28 = 14.2 
48762 = 277 ·176 + 10 
176 = 17 . 10 + 6 
10=1·6+4 
6=1·4+2 
4 = 2· 2 
97421 = 2. 42516 + 12389 
42516 = 3 . 12389 + 5349 
12389 = 2 . 5349 + 1691 
5349 = 3. 1691 + 276 
1691 = 6. 276 + 35 
276 = 7. 35 + 31 
35 = 1· 31 + 4 
31 = 7. 4 + 3 
4=1·3+1 
3 = 3 ·1 
Capítulo 1. Problemas resolvidos 3 
(g) Temos, 
logo (8374, 24517) = 1. 
(h) Temos, 
logo (35262, 12753) = 9. 
24517 = 2. 8374 + 7769 
8374 = 1. 7769 + 605 
7769 = 12 . 605 + 509 
605 = 1 . 509 + 96 
509 = 5 . 96 + 29 
96 = 3. 29 + 9 
29 = 3. 9 + 2 
9=4·2+1 
4 = 2. 2 
35262 = 2 . 12753 + 9756 
12753 = 1 . 9756 + 2997 
9756 = 3 .2997 + 765 
2997 = 3 . 765 + 702 
765 = 1 . 702 + 63 
702 = 11 . 63 + 9 
63 = 7. 9 
2. Achar o mínimo múltiplo comum dos seguintes pares de números: 
(a) 44 e 32 
(b) 234 e 12 
(c) 35 e 24 
(d) 142 e 742 
(e) 17 e 141 
(f) 42 e 52 
(g) 501 e 2141 
(h) 144 e 64 
Para resolver os itens, do Problema 2, usaremos que se 
t t 
a= I1Pi 0 i e b = Ilp/i 
i=l j=l 
Solução: 
o 
4 Problemas em Teoria dos Números (Resolvidos e Propostos) 
(a) Temos que 44 = 22 ·11 e 32 = 25 . Assim, [44,32] = 25 ·11 = 352. 
(b) Temos que 234 = 2 · 32 · 13 e 12 = 22 · 3. Assim, [234, 12] = 22 . 32 . 13 = 468. 
(c) Temos que 35 = 5 · 7 e 24 = 23 · 3. Assim, [35,24] = 23 · 3 · 5 · 7 = 840. 
(d) Temos que 142 = 2 · 71 e 742 = 2 · 7 ·53. Assim, [142, 742] = 2 · 7 ·53· 71 = 52682. 
(e) Temos que 17 é primo e 141 = 3 · 47. Assim, [17, 141] = 3 · 17 · 47 = 2397. 
(f) Temos que 42 = 2 · 3 · 7 e 52 = 22 · 13. Assim, [42, 52] = 22 . 3 . 7 · 13 = 1092. 
(g) Temos que 501 = 3 · 167 e 2141 é primo. Assim, [501, 2141] = 3 · 167 · 2141 = 1072641. 
(h) Temos que 144 = 24 · 32 e 64 = 26 . Assim, [144, 64] = 26 · 32 = 576. 
3. Encontrar uma sequência de pelo menos 30 inteiros consecutivos e compostos. 
o 
Solução: Na demonstração do Teorema 1.13, vimos que para todo inteiro positivo k, os números 
(k + 1)! + 2, (k + 1)! + 3, (k + 1)! + 4, ... (k + 1)! + (k + 1) 
são compostos. Para esse problema tome k = 30. Ou seja, a sequência 
(31)! + 2, (31)! + 3, (31)! + 4, ... (31)! + (31) 
conterá somente números compostos. Como curiosidade o número 31! é dado por 
8222838654177922817725562880000000. 
4. Mostrar por indução, que 
(a) 12 + 22 + 32 + ... + n2 = n(n+1~(2n+l) 
(b) 1 + 3 + 5 + · · · + (2n- 1) = n2 
(c) 1 · 2 + 2 · 3 + 3 · 4 + · · · + n(n + 1) = n(n+lJ(n+2) 
(d) n! > 2n, Vn ~ 4 
(e) n2 > 2n + 1, Vn ~ 3 
(f) 91 (lon+I- 9n- 10), Vn ~ 1 
Para facilitar as demonstrações, denotamos: 
Solução: 
{ 
BI : Base de Indução 
HI : Hipótese de Indução 
TI: Tese de Indução. 
o 
(a) Temos que, 
Como 
temos pela HI que 
Portanto, 
Capítulo 1. Problemas resolvidos 5 
H I : 12 + ... + k2 = k(k+1~(2k+l) 
{
BI: 12 = 1·(1+1)~(2·1+1) 
TI : 12 + ... + (k + 1)2 = (k+1)(k~2)(2k+3). 
12 (k 1)2 k(k + 1)(2k + 1) (k )2 +···+ + = 6 + +1 . 
12 + ... + (k + 1)2 = k(k + 1)(2k + 1) + (k + 1)2 = 
6 
(k + 1)(2k2 + 7k + 6) 
-
6 
Mas 2k2 + 7k + 6 = (k + 2)(2k + 3) e isso conclui a prova. 
(b) Temos que, 
{
BI:2·1-1=12 
HI: 1 + · · · + (2k -1) = k2 
TI: 1 + · · · + (2k + 1) = (k + 1)2. 
Como 
1 + ... + (2k + 1) = 1 + ... + (2k- 1) + (2k + 1), 
temos pela HI que 
1 + ... + (2k + 1) = k2 + (2k + 1). 
Portanto, 
1 + ... + (2k + 1) = (k + 1)2. 
(c) Temos que, 
{
BI: 1 · 2 = 1·(1+11(1+2) = 2 . 
HI: 1 · 2 + · · · + k(k + 1) = k(k+1J(k+2) 
TI: 1. 2 + ... + (k + 1)(k + 2) = (k+1)(k;-2)(k+3). 
Como 
1. 2 + ... + (k + 1)(k + 2) = 1. 2 + ... + k(k + 1) + (k + 1)(k + 2), 
temos pela HI que 
1. 2 + ... + (k + 1)(k + 2) = k(k + 11(k + 2) + (k + 1)(k + 2). 
Assim, 
k(k + l)(k + 2) (k )(k ) = k(k + 1)(k + 2) + 3(k + 1)(k + 2) 
3 + +1 +2 3 
e daí segue que 
k(k + 1)(k + 2) + 3(k + 1)(k + 2) (k + 1)(k + 2)(k + 3) 
-
3 3 
6 Problemas em Teoria dos Números (Resolvidos e Propostos) 
( d) Temos que, 
Como 
temos pela HI que 
{ 
BI : 4! = 24 > 16 = 24 
HI: k! > 2k 
TI : ( k + 1)! > 2k+1. 
(k + 1)! = (k + 1)k!, 
(k + 1)k! > (k + 1)2k. 
Mas k + 1 > 2, logo multiplicando essa última desigualdade por 2k temos 
(k + 1)2k > 2k+l. 
Assim, 
(e) Temos que, 
Como 
e pela HI 
temos que, 
Mas como 2k + 1 ~ 3, temos 
( k + 1)! > ( k + 1) 2k > 2k+l. 
{
BI: 32 = 9 > 7 = 2 · 3 + 1 
HI: k 2 > 2k + 1 
TI: (k + 1)2 > 2(k + 1) + 1. 
k 2 > 2k + 1, 
(k + 1)2 > 2k + 1 + 2k + 1. 
(k + 1)2 > 2k + 1 + 3 > 2k + 3 = 2(k + 1) + 1. 
OBS: Uma solução mais direta seria: como n ~ 3 > v'2 + 1, então n- 1 > J2. Logo 
(n- 1)2 > 2 e assim n 2 - 2n + 1 > 2. Daí segue n 2 > 2n + 1. 
(f) Perceba que 9 I (lon+I- 9n- 10) se, e somente se, 9 I (lon+l- 1). De fato, como 
10n+l- 9n- 10 = 10n+l- 1- 9(n + 1), 
segue que 91 (lon+l- 9n- 10) ~ 91 (lon+I- 1). Assim, temos que 
{
BI: 9 I (101+1 - 1) = 99 
H I : 9 1 ( 1 ok+ 1 - 1) 
TI: 91 (10k+2 - 1). 
Como 10k+2 - 1 = 10k+2 - 10k+1 + 10k+1 - 1 = 9 · 10k+l + 10k+1 - 1, temos pela HI que 
9 I (1ok+I - 1). Logo segue que 9 I (lok+2 - 1). 
n+l 
' ,_...,.,.._ 
OBS: Uma solução direta é notar que 10n+l - 1 = 9 ... 9 que é múltiplo de 9 (soma dos 
algarismos é múltiplo de 9 ). 
----------
Capítulo 1. Problemas resolvidos 7 
o 
5. Provar que o produto de 3 inteiros consecutivos é divisível por 6. 
Solução: Queremos mostrar que 6 I n(n + 1)(n + 2), para todo n E .Z. Para tanto, usaremos 
indução sobre n. Quando n E {0, - 1, - 2} O resultado é obviamente verdadeiro, e além disso, 
quando n < -3, então 
n(n + 1)(n + 2) = -( -n)( -n + 1)( -n + 2). 
Portanto, é suficiente mostrar que 6 I n(n + 1)(n + 2), somente para n ~ 1. 
{
BI: 6 11 · (1 + 1) · (1 + 2) = 6 
HI: 61 k(k + 1)(k + 2) 
TI: 61 (k + 1)(k + 2)(k + 3). 
Como (k + 1)(k + 2)(k + 3) = k(k + 1)(k + 2) + 3(k + 1)(k + 2), então pela HI, basta mostrar 
que 6 I 3(k + 1)(k + 2), ou equivalentemente, que 2 I (k + 1)(k + 2) o que é verdadeiro uma vez 
que um dos números k + 1 ou k + 2 é par. O 
6. Provar que para todo n E N, 32n+l +2n+2 é um múltiplo de 7 e que 32n+2 + 26n+l é um múltiplo 
de 11. 
Solução: (i) Vamos provar, por indução, que 7l32n+l +2n+2. Defina Mn = 32n+l +2n+2. Então 
{ 
B I : 7 I Ml = 33 + 23 = 35 
HI: 71 Mk 
TI: 71 Mk+l· 
Note que Mk+l- Mk = 32k+3 + 2k+3 - 32k+l- 2k+2 = 8 · 32k+l + 2k+2 = 7 · 32k+l + Mk. Logo 
Mk+l = 7 · 32k+l + 2Mk. Como 71 7 · 32k+l e pela HI 7 I 2Mk temos que 71 Mk+l· 
(ii) Vamos provar, por indução, que 11 I 32n+2 + 26n+l. Defina Sn = 32n+2 + 26n+l, então 
{
BI: 111 81 = 34 + 27 = 209 = 11· 19 
HI: 111 Sk 
TI: 111 Sk+l· 
Note que Sk+l- Sk = 32k+4 + 26k+7- 32k+2- 26k+l = 8. 32k+2 + 63. 26k+l = 8(32k+2 + 26k+l) + 
55. 26k+l = 8Sk +55. 26k+l. Logo 11 I sk+l = 9Sk +55. 26k+l' pois 11 I 9Sk e 11 I 55. 26k+l. o 
7. Encontrar inteiros x e y tais que 
(a) 93x + 81y = 3 
(b) 43x + 128y = 1 
Solução: 
8 Problemas em Teoria dos Números (Resolvidos e Propostos) 
(a) Primeiramente temos pelo algoritmo de Euclides 
93 = 81 + 12 
81 = 6 ·12 + 9 
12 = 1· 9 + 3 
9= 3·3. 
Isto é (93, 81) = 3. Isso mostra que existem inteiros x e y satisfazendo 
93x + 81y = 3. 
Logo, 
6 . 93 = 6 . 81 + 6 . 12 = 
6 . 81 + (81 - 9) = 7. 81 - (12 - 3) = 
7. 81- (93- 81) + 3 = 
8. 81-93 + 3. 
Assim, 93 · 7 + 81 · ( -8) = 3 e (x, y) = (7, - 8) é solução. 
(b) Como 128 = 3 · 43- 1, então (x, y) = (3, - 1) é solução de 43x + 128y = 1. 
8. Mostrar que se a e b são inteiros positivos com (a, b) = [a, b], então a= b. 
o 
Solução: Sejam a = fn=l Pia, e b = f1~=l Pi.B' com ai, /3i 2: O. De acordo com o Teorema 1.11 
e a Proposição 1.5, basta-nos mostrar que se max{ ai, f3i} = min{ ai, /3i}, então ai = /3i, o que é 
trivialmente verdadeiro. Portanto, segue que a = b. O 
9. Mostrar que n 5 - n é divisível por 30 para todo inteiro n. 
Solução: Como 30 = 6 · 5 e (6,5) = 1, segue que 30 I n 5 - n -<==:::} 5 I n 5 - n e 6 I n 5 - n. 
Fatorando n 5 - n temos que, 
n 5 - n = (n- 1)n(n + 1)(n2 + 1). 
Assim, resta mostrar que 5 I n5 - n, uma vez que foi mostrado no Problema 5 que 
6 I (n- 1)n(n + 1) e portanto 6 I n5 - n. Como todo número natural n é da forma 5k + j, onde 
j E {0,1,2,3,4}, temos 
n = 5k =? 5 I (n- 1)(5k)(n + 1)(n2 + 1) = n5 - n 
n = 5k + 1 =? 5 I (5k)n(n + 1)(n2 + 1) = n5 - n 
n = 5k + 2 =? 5 I (n- 1)n(n + 1)(25k2 + 20k + 5) = n 5 - n 
n = 5k + 3 =? 5 I (n- 1)n(n + 1)(25k2 + 30k + 10) = n 5 - n 
n = 5k + 4 =? 5 I (n- 1)n(5k + 5)(n2 + 1) = n 5 - n. 
Portando, podemos concluir que 30 I n 5 - n, para todo inteiro n. o 
Capítulo 1. Problemas resolvidos 9 
10. Mostrar que a equação x3 + 7x + 17 =O não possui nenhuma solução inteira. 
Solução: Suponha, por absurdo, que m E Z é uma solução. Então, 
m 3 + 7m + 17 =O <==> m(m2 + 7) = -17. 
Como 17 é primo e m2 + 7 > O, a igualdade acima implica que m I -17 e logo m = -1 ou 
m= -17. Então 
{
m = -1 =? ( -1) · (( -1)2 + 7) = -8 =I -17 
m = -17 =? (-17) · ((-17) 2 + 7) = -5032 #-17. 
Log;o não existe m E Z ~ai que m3 + 7m -f- 17 = O. o 
11. Mostrar que para nenhum n E N, 2n + 1 é um cubo. 
Sol~·ção: Suponha,. por absurdo que, 2n + 1 = x3 , para algum x E N. Logo 2n = x 3 - 1 = 
(x -1)(x2 +x+ i). Como 2n + 1 'f= 13 e 2n + 1 #23, então podemos supor x > 2. Logo x -1 > 1 
divide 2n e, portanto, deve ser par. Assim x é ímpar e logo x2 + x + 1 é ímpar maior do que 1 
dividindo 2n. Esse absurdo completa nossa demonstração. O 
12. Pode o número A= 111 ... 1, formado por trezentos 1's, ser um quadrado? 
Solução: Para resolvermos esse problema usaremos o seguinte fato. Se p é primo e p I a2 , elltão 
p2 I ÇJ-2 . De fato, se .P I a2 = a · a então p I a e portanto pk I ak para todo k 2:: 1. Em particular 
para k = 2. Suponha, por absurdo, que A= a2 para algum a E N. Como a soma dos dígitos de 
A é 300, ·então 3 I A = a2 e pelo fato acima 32 I a2 = A. Portanto 9 divide A, mas isso implica 
que 9 I 300 o que é um absurdo. Logo A não é um quadrado perfeito. o 
13. Sejam F1 = 1, · F2 = 1 ·e Fn = Fn-1 + Fn-2, n 2:: 3 (Fn é chamado o n-ésimo número de 
• Fibonacci) .. Mostrar que 
(a) F1 + F3 + Fs + · · · +F2n-1 = F2n 
(b) F2 + F4 + F6 + · · · + F2n = F2n+l - 1 
(c) F1 + F2 + F3 + · · · + Fn = Fn+2- 1 
. 2 
(d) F1F2 + F2F3 + +F3F4 + · · · + F2nF2n+1 = F2n+1 -1 
SoluÇão: Mostraremos cada Uiíl dos casos por indução. 
(a) Temos que 
Como 
{
BI: n = 1, F1 __:_ F2.1-1 = 1 
H I : F1 + F3 · · · + F2k-1 = F2k 
TI: F1 + F3 · · · + F2k+1 = F2k+2· 
10 Problemas em Teoria dos Números (Resolvidos e Propostos) 
temos pela HI que 
e, portanto, 
(b) Temos que 
Como 
temos pela HI que 
e, portanto, 
(c) Temos que 
Como 
temos pela HI que 
e, portanto, 
( d) Temos que 
{
BI: n = 1, F2 = F2-1+1- 1 = 1 
H I : F2 + F4 + · · · + F2k = F2k+1 - 1 
TI : F2 + F4 + · · · + F2k+2 = F2k+3 - 1. 
{
BI:n=1, F1=F1+2-1=1 
H I : F1 + F2 + · · · + Fk = Fk+2 - 1 
TI : F1 + F2 + · · · + Fk+l = Fk+3 - 1. 
{
BI: F1F2 + F2F3 = 1·1 + 1· 2 = 3 = 22 -1 = F2-1+1 2 -1 
HI: HF2 + · · · + F2kF2k+1 = F2k+1 2 - 1 
TI: HF2 + · · · + F2k+2F2k+3 = F2k+3 2 -1. 
Como 
temos pela HI que 
F1F2 + · · · + F2k+2F2k+3 = F2k+1 2 - 1 + F2k+1F2k+2 + F2k+2F2k+3· 
Assim, vale que 
Capítulo 1. Problemas resolvidos 11 
Logo 
e, portanto, 
Daí, 
14. Mostrar que os números de Fibonacci, definidos no problema anterior, satisfazem 
(a) (Fn, Fn+l) = 1 
(b) (Fn, Fn+3) = 1 OU 2. 
Solução: 
(a) Apresentamos duas soluções para este problema. 
(i) 
{
BI: (F1, F2) = 1 
HI: (Fk, Fk+1) = 1 
TI: (Fk+l, Fk+2) = 1. 
o 
Como (Fk+1, Fk+2 ) = (Fk+l, Fk+l + Fk) e como pelo Teorema 1.5 temos que (a, b) = 
(a, b + ax) para todos inteiros a, b e x, então, temos, (Fk+l, Fk+2) = (Fk+l, Fk)· Logo, 
como pela HI (Fk+b Fk) = 1 então (Fk+1, Fk+2) = 1. 
(i i) Pelo algoritmo de Euclides, 
logo (Fn+l, Fn) = F1 = 1. 
Fn+1 = Fn + Fn-1 
Fn = Fn-1 + Fn-2 
(b) Como (Fn, Fn+3) = (Fn, Fn+l +Fn+2) = (Fn, 2Fn+l +Fn) = (Fn, 2Fn+l)· Então, (Fn, Fn+3) I 
Fn e (Fn, Fn+3) I 2Fn+l· Portanto (Fn, Fn+3) I 2Fn e (Fn, Fn+3) I 2Fn+1· Assim, (Fn, Fn+3) I 
(2Fn, 2Fn+1) = 2(Fn, Fn+1)· Mas pelo item anterior vimos que (Fn, Fn+l) = 1, logo 
(Fn, Fn+3) I 2(Fn, Fn+l) = 2 ~ (Fn, Fn+3) = 1 OU (Fn, Fn+3) = 2. 
o 
12 Problemas em Teoria dos Números (Resolvidos e Propostos) 
15. Mostrar que além de 2 = 13 + 1, nenhum número da forma n 3 + 1 é primo. 
Solução: Devemos mostrar que n 3 + 1 é composto, para todo n > 1. De fato, como 
n 3 + 1 = (n + 1)(n2 - n + 1) 
segue diretamente que n3 + 1 é composto pois n + 1 > 2 e se n 2 - n + 1 = 1 então n = O ou 
n=l. O 
16. Utilizando a sequência Rn = n! + 1, n ~ 1, fornecer uma outra demonstração para a infinitude 
dos primos. 
Solução: Mostraremos que dado n E N, existe p primo com p > n. De fato, para todo n E N, 
podemos escrever n! + 1 = Rn = pm, com m ~ 1. Logo p I n! + 1. Se p ~ n, então p dividiria n! 
e logo p dividiria 1. Portanto p > n. O 
17. Mostrar que todo inteiro maior do que 11 é a soma de dois inteiros compostos. 
Solução: Apresentamos duas soluções para este problema. 
(i) Temos, primeiramente, que todo inteiro n admite as formas n = 2k ou n = 2k + 1. Assim, 
podemos escrever n como segue 
n = 2k = 2(k- 2) + 4 n = 2(k- 4) + 9. 
Como n > 11 temos que k > 5, portando, 2(k- 2) e 2(k- 4) são números compostos e daí segue 
que todo inteiro n > 11 é a soma de dois compostos. 
(i i) Vamos à segunda solução. Suponha que n é da forma 2k, com k > 5, então, 
(1) k composto=? n = k + k 
(2) k primo=? k ímpar, assim n = (k -1) + (k + 1), (k -1) e (k + 1) são números pares maiores 
do que 2 e, portanto, ( k - 1) e ( k + 1) são números compostos. 
Suponha, agora, que n é da forma 2k + 1. Logo, n = 2k + 1 = k + (k + 1) com k > 5. Se k 
e k + 1 são compostos, então está terminado. Suponha então, sem perda de generalidade, que 
k é primo. Logo k- 1 é composto e n = (k- 1) + (k + 2). Assim, k + 2 composto implica no 
resultado. Portanto, suponha, que, k+2 é primo. Então k+3 é composto e n = (k- 2) + (k+3). 
Afirmamos que k - 2 é composto e o problema está resolvido. De fato, se k - 2 é primo, então, 
pelo Problema 18, temos que k - 2, k e k + 2 são primos implica k - 2 = 3. Logo k = 5 o que é 
absurdo, pois k > 5. O 
18. Mostrar que 3 é o único primo p tal que p, p + 2 e p + 4 são todos primos. 
Solução: Claramente se p = 3, então p, p + 2 e p + 4 são primos. Suponha p > 3 primo. Então p 
admite as seguintes formas 3k + 1 ou 3k + 2. Em qualquer um dos casos temos: se p = 3k + 1, 
então 3 I p + 2 e logo p+ 2 é composto. Se p = 3k + 2, então 31 p+4 e logo p+4 é composto. O 
19. Achar a soma de todos os números formados pelas permutações dos dígitos 1, 2, 3, 4 e 5, isto é: 
12345 + ... + 54321. 
Capítulo 1. Problemas resolvidos 13 
Solução: Vamos estabelecer duas soluções para esse problema. 
(i) SejaS= 12345 + · · · + 54321. Vamos somar da maneira convendonal. Note que o dígito das 
unidades de Sé igual ao resto da divisão de 24(1 + 2 + 3 + 4 + 5) = 360 por 10, Logo o último 
dígito de Sé O. Como a soma de cada coluna abaixo é igual a 360 
12345 
12354 
54312 
54321 
então o dígito das dezenas de Sé o resto da divisão de 360 + 36 por 10, isto é, 6. Pelo mesmo 
argumento, o dígito da centena e milhar é 9. Pois 9 é o resto da divisão de 360 + 39 por 10. Mas, 
claramente, seus 3 primeiros dígitos são 360 + 39 = 399. Logo, S = 3.999.960. 
(i i) Usaremos a conhecida ideia de Gauss para somar os números d~ 1 a 100, isto é, somar termos 
recíprocos. Seja 
s = 12345 + 12354 + ... + 54312 + 54321. 
Note que a primeira parcela somada com a última resulta em 12345 + 54321 = 66.666 o mesmo 
acontece com a segunda somada com a penúltima 12354 + 54312 = 66.666 e assim por diante. 
Como existem 5! = 120 parcelas na soma, temos que S = 66.666 + · · · + 66.666 = 60 · 66.666 = 
60 vezes 
3.999.960. o 
20. Provar que não existe n E N tal que 71 (4n2 - 3). 
Solução: Suponha, por absurdo, que 7l4n2 - 3. Como 717, então 71 (4n2 - 3) + 7 = 4(n2 + 1). 
Mas (7, 4) = 1 e, portanto, 7 I (n2 + 1), ou seja, n 2 deixa resto 6 na divisão por 7. Por outro 
lado, n é da forma 7k + j, com j E {0, ... ,6} e, portanto, os possíveis restos na divisão de n 2 
por 7 são O, 1, 2 e 4. Assim 7 não pode dividi~ n 2 + 1 e, consequentemente, 7 não pode dividir 
4n2 - 3. O 
21. Sabendo que o resto da divisão de um inteiro b por 7 é 5, calcular o resto da divisão por 7 dos 
seguintes números: 
(a) -b 
(b) 2b 
(c) 3b+.7 
(d) 10b+1 
(e) b2 + b + 1 
Solução: Como b é da forma 7k + 5 então 
14 Problemas em Teoria dos Números (Resolvidos e Propostos) 
(a) -b = -7k- 5 = 7( -k- 1) + 2 =>resto é 2. 
(b) 2b = 14k + 10 = 7(2k + 1) + 3 =>resto é 3. 
(c) 3b + 7 = 21k + 22 = 7(3k + 3) + 1 =>resto é 1. 
(d) lOb + 1 = 70k +51= 7(10k + 7) + 2 =>resto é 2. 
(e) b2 + b + 1 = 49k2 + 77k + 31 = 7(7k2 + 11k + 4) + 3 =>resto é 3. 
22. Seja Un = 111 ... 1 um número formado por n l's. Provar que Un primo implica n primo. 
o 
Solução: Mostraremosque n composto implica Un composto. De fato, se n = rs, com r, s > 1, 
então 
lOn - 1 lOrs - 1 (lOr)s - 1 
Un = 111 ... 1 = 
9 9 
-
9 
= ( lOr 9- 1) (lor(s-1) + ... + 1) 
que é composto, já que cada expressão entre parênteses é maior que 1. Note que 10~ - 1 2: 10~-1 = 
11. o 
23. Mostrar que, se para algum n, m I (35n + 26), m I (7n + 3) em> 1, então m = 11. 
Solução: Como m I (35n + 26) em I (7n + 3) então m divide 
1(35n + 26) + ( -5)(7n + 3) = 11. 
Logo m = 1 ou m = 11, mas por hipótese, m > 1. Assim, m = 11. o 
24. Sendo ~ + i um inteiro, onde a e b são inteiros positivos, mostrar a = b. Mostrar também que 
a= 1 ou 2. 
Solução: Apresentamos três soluções para esse problema. 
(i) Suponha que ~+i = c E Z. Então a+ b = abc e podemos concluir que a I b pois b = a(bc- 1) 
e b I a pois a= b(ac- 1). Logo a= b, pois a e b são positivos.· Daí ~ = c e logo a I 2. Sendo 
assim, segue que a = 1 ou a = 2. 
(ii) Se ~+i =c, então a+ b = abc e, portanto, b = acC:..1. Como ac- 1 é maior do que a para 
c > 3; segue que c = 1 ou c = 2. Logo b = a~1 ou b = 2aC:..1. Assim a - 1 I a e daí a = 2 (e, 
portanto, b = 2). No outro caso (2a- 1) I a e daí 1 = ( -1, a) = (2a- 1, a) = 2a- 1 =>a= 1 (e, 
portanto, b = 1). 
(iii) Se min{a,b} > 2, então 
1 1 1 1 
0<-+-<-+-=1. 
a b 2 2 
Logo ~ + i não pode ser inteiro, pois está entre O e 1. Logo min{ a, b} ~ 2. Daí, se a = 1 então 
g E N ===> b = 1. Se a = 2 então ! + i E N => g E N => b = 1 ou b = 2. Mas ~ + 1 fi N então 
b=2. 0 
Capítulo 1. Problemas resolVidos 15 
25. Mostrar que, se (a, b) = 1, então (2a + b, a+ 2b) = 1 ou 3. 
Solução: (i) Solução 1. Se d = (2a + b, a+ 2b). Temos que, 
dI (( -1)(2a + b) + 2(a + 2b)) = 3b 
e também, 
dI (2(2a + b) + ( -1)(a + 2b)) = 3a. 
Se (3,d) = 1 então dI a e dI b. Logo d = 1 pois (a,b) = 1. 
Se (3,d) = 3 então d = 3k. Como dI 3a e dI 3b então k I a e k I b. Mas (a,b) = 1 e portanto 
k = 1. Assim, d = 3. 
(ii) Solução 2. Usaremos o Teorema 1.7 e a Proposição 1.3. De fato, 
mas, 
d= (2a+b,a+2b) = (2(a+2b)- 3b,a+2b) = 
= (3b,a+2b) = (3b,a-b+3b) = (3b,a-b) 
(3b, a- b) I (3b, 3(a- b)) = (3b, 3a- 3b) = (3b, 3a) = 3(b, a)= 3. 
Logo, d I 3 e portanto d = 1 ou d = 3. o 
26. Mostrar que sendo num inteiro, o número n(n + 1)(n + 2)(n + 3) + 1 é um quadrado perfeito. 
Solução: Defina a= n 2 + 3n. Logo n(n +1)(n + 2)(n + 3) + 1 = (n(n+ 3))((n + 1)(n + 2)) + 1 = 
(n2 + 3n)(n2 + 3n + 2) + 1 = a(a + 2) + 1 = a2 + 2a + 1 =(a+ 1)2 = (n2 + 3n + 1)2 . O 
27. Determinar todos os números de 3 algarismos divisíveis por 8, 11 e 12. 
Solução: Primeiramente calculamos o menor inteiro que tem 8, 11 e 12 como fatores comuns. 
Este é o mínimo múltiplo comum que é dado por [8, 11, 12] = 264. Daí os números que são, 
simultaneamente, divisíveis por 8, 11 e 12 são os múltiplos de 264. Logo com 3 dígitos temos: 
{264, 2. 264,3. 264} = {264, 528, 792}. 
o 
28. Encontrar todos os inteiros positivos n para os quais (n + 1) I (n2 + 1). 
Solução: Suponha que ( n + 1) I ( n2 + 1), então nt.tl = n 2;;t2 = n- 1 + n!l E Z. Logo n + 1 I 2 
e portanto, n + 1 = 1 ou n + 1 = 2. Daí n = O ou n = 1. Assim, n = 1 é o único inteiro positivo 
tal que (n+ 1) I (n2 + 1). O 
29. Dados a e b inteiros com b #O, mostrar que existem inteiros q e r satisfazendo a= qb ±r, O~ 
r~~· 
Solução: Pelo algoritmo da divisão de Euclides temos que a= bq +r, com O~ r< b. Se r~ ~' 
o resultado está provado. Se r > ~ então a = b(q + 1) - (b- r), onde b- r < b- ~ = ~ e o 
resultado está completo. D 
16 Problemas em Teoria dos Números (Resolvidos e Propostos) 
30. Mostrar que se a e b são inteiros, (a, 3) = (b, 3) = 1, então a2 + b2 não é um quadrado perfeito. 
Solução: Como por hipótese (a, 3) == 1 então a= 3k + 1 ou a= 3k + 2. Logo temos, que, quando 
a= 3k + 1, a 2 = 3k + 1 com k = 3k2 + 2k e quando a= 3k + 2 temos que a 2 = 3.k' + 1 com 
k' = 3k2 + 4k + 1. Como (b, 3) = 1 temos que b = 3q + 1 ou b = 3q + 2 e, analogamente, teremos 
que b2 é da forma 3Q + 1. Assim, se x 2 = a 2 + b2 temos que x 2 = a 2 + b2 = 3s + 2. Mas como 
todo quadrado deixa resto O ou 1 na divisão por 3 
x2 = a2 + b2 
não é um quadrado perfeito. D 
31. Mostrar que para n > 1 os números n4 + 4 e n4 + n 2 + 1 são ambos números compostos. 
Solução: (i) De fato, temos que, 
n4 + 4 = n4 + (2n) 2 + 4...:. (2n)2 ·= (n2 + 2) 2 - (2n)2 = (n2 + 2 + 2n)(n2 + 2- 2n). 
Como n 2::2 temos que n 2 +2+2ri = n(n+2)+2 > 2 e n 2 +2-2n = n(n-2)+2 2::2. Portanto, 
segue que n 4 + 4 é composto. 
(i i) De fato, temos que, 
n4 + n2 + 1 = n4 + 2n2 + 1- n2 = (n2 + 1)2 - n2 = (n2 + 1 + n)(n2 + 1...:.. n}; · 
Como n 2:: 2 temos que n2 + 1 + n > 1 e n2 + 1-:- n = n(n- 1) + 1 > 1. Portanto, se~e que 
n4 + n 2 + 1 é composto. [J 
32. Mostrar os itens (a), (b) e (c) do Problema 13sem f~er uso de indução. 
Solução: (a) Observe que 
F1 =F2 
F3 = F4- F2 
Fs = F6- F4 
F2n-3 = F2n-2- F2n-4 
F2n-l = F2n- F2n-2• 
Somando as igualdades acima, obtemos F1 + F3 + · · · + F2n-i = F2n· 
(b) Com efeito, temos: 
F2 = F3- F1 
F4 = Fs- F3 
F6 = F1- Fs 
F2n-2 = F2n-l- F2n-3 
F2n = F2n+l- F2n-l· 
Capítulo 1. Problemas resolvidos 17 
Somando as igualdades acima, obtemos F2 + F4 + · · · + F2n = F2n+l- F1 = F2n+1- 1. 
(c) Note que, 
F1 = Fa- F2 
F2 = F4- Fa 
Fa = Fs- F4 
Fn-1 = Fn+l - Fn 
Fn = Fn+2 - Fn+l· 
Somando as igualdades acima, obtemos .H + F2 + · · · + Fn = Fn+2 - F2 = Fn+2 - 1. 
33. Mostrar que (a, bc) = 1 se, e somente se, (a, b) = (a, c) = 1. 
o 
Solução: Usaremos o fato que, (a, b) = 1 se, e somente se, existem x,y E Z tais que ax + by = 1. 
De fato, se (a, bc) = 1 então existem xo, Yo E Z tais que axo + (bc)yo = 1. Logo, 
axo + (yoc)b = 1 =? (a, b) = 1 
axo + (yob)c = 1 =? (a, c) = 1. 
Se (a, b) = (a, c) = 1, então existem r, s, t, u E Z tais que, ar+ bs = 1 = at +cu. Logo, 
1 = (ar+ bs)(at +cu)= rta2 + rauc + sbta + sbuc = (rta +rue+ sbt)a + (su)(bc) =? (a,bc) = 1. 
o 
34. Mostrar que se b I c então (a+ c, b) = (a, b). 
Solução: Usaremos o Teorema 1.7. Se a, b E Z, então (qb +r, b) = (r, b). Como b I c então c= qb 
para algum q E Z. Daí pelo Teorema 1.7 segue que (a+ c, b) = (a+ qb, b) =(a, b). O 
35. Mostrar que se (a, c)= 1 então (a, bc) = (a, b). 
Solução: Como (a, b) I a, e (a, b) I b I bc segue que (a, b) é um divisor comum de (a, bc) portanto 
(a, b) ~ (a, bc). Por outro lado, a e c são primos entre si, logo, existem xo, yo E Z tais que 
axo+cyo = 1 =? (ab)xO+(bc)yo = b. Como (a, bc) I a e (a, bc) I bc, então (a, bc) I (a(bxo)+bcyo) = 
b =? (a, bc) ~ (a, b). Daí vale a igualdade, isto é, (a, bc) = (a, b). O 
36. Mostrar que (a, b, c)= ((a, b), c). 
Solução: De modo análogo a prova do Teorema 1.11, podemos mostrar que se a = IlPi0 ', 
b = IlPi'8• e c= f1pi'"Y• então (a,b,c) = IlPimin{a,,,B,m}. Por outro lado, pelo Teorema 
1.11, ((a, b), c) = (ITPimin{a,,,B,}, c) = IJPimin{rnin{a,,,B,}m}. Portanto, resta-nos mostrar que 
min { min {ai, .Bi}, {i} = min {ai, .Bi, li}. Mas essa igualdade é fácil de ser provada dividindo os 
casos em que ai, f3i e {i são mínimos, respectivamente. O 
18 Problemas em Teoria dos Números (Resolvidos e Propostos) 
37. Dizer qual é o maior inteiro que pode ser somado ao dividendo sem alterar o quociente quando 
se divide 431 por 37. 
Solução: Temos que 431 = 37 · 11 + 24. Logo, somando t ao dividendo e ao resto, temos 
431 + t = 37 · 11 + (24 + t). Queremos o maior t, tal que o quociente da divisão de 431 + t por 
37 seja ainda 11. Logo, queremos o maior t tal que 24 + t < 37 (pois caso contrário, o quociente 
será pelo menos 12). Daí t < 13 e portanto t = 12 é o valor desejado. O 
38. Para cada par de inteiros a e b dado abaixo, encontrar o quociente q e o resto r satisfazendo o 
algoritmo da divisão de Euclides 
(a) a= 59; b = 6 
(b) a = -71; b = 5 
(c) a= -48; b = -7 
(d) a= 67; b = -13 
Solução: 
(a) 59= 9 · 6 + 5 => q = 9 e r= 5. 
(b) -71 = 5 · ( -15) + 4 => q = -15 e r= 4. 
(c) -48 = ( -7) · 7 + 1 => q = 7 e r = 1. 
(d) 67 = ( -13) · ( -5) + 2 => q = -5 e r= 2. 
39. Mostrar que se nem são inteiros ímpares, então 8 I (n4 + m 4 - 2). 
Solução:Escrevendo n = 2k + 1 em= 2t + 1, temos, 
o que claramente é um múltiplo de 8. 
OBS.: Usamos que (a+ 1)4 = a4 + 4a3 + 6a2 + 4a + 1. 
40. Encontrar o menor inteiro positivo da forma 36x + 54y onde x e y são inteiros. 
o 
o 
Solução: Usaremos a observação do Teorema 1.3, que diz que o menor inteiro positivo da forma 
ax + by, com x, y E Z, é exatamente (a, b), ou seja, (a, b) = min (N n {ma+ nb I m, n E Z} ). Daí 
basta calcular (36, 54). Portanto (36, 54) = (22 • 32 ,2 · 33) = 2 · 32 = 18. O 
41. Utilizando o processo descrito no Teorema 1.17 expressar o número 274 nas bases 2,5,7 e 9. 
Capítulo 1. Problemas resolvidos 19 
Solução: Na demonstração do Teorema 1.17, vimos que se 
n = bqo + ao, O ~ ao < b 
qo = bq1 + a1, O ~ a1 < b 
Ql = bq2 + a2, O ~ a2 < b 
então n = (akak-l ... a1ao)b. Daí 274 pode ser expresso na, 
(i) Base 2, 
então 274 = (100010010)2. 
(ii) Base 5, 
então 274 = (2044)s. 
(iii)Base 7, 
então 274 = (541)7. 
(iv) Base 9, 
então 274 = (334)g. 
.· .. ·274 = 2. 137 +o, 
137 = 2 . 68 + 1, 
. 68 = 2 . 34 + o, 
34 = 2. 17 +o, 
17 = 2. 8 + 1, 
8 = 2. 4 +o, 
4 = 2. 2 +o, 
2 = 2 ·1 +o, 
1 = 2. o+ 1, 
274 = 5. 54+ 4, 
54= 5 ·10 + 4, 
10 = 5. 2 +o, 
2 = 5. o+ 2, 
{
274 = 7. 39 + 1, 
39 = 7. 5 + 4, 
5 = 7. o+ 5, 
{ 
27 4 = 9 . 30 + 4, 
30 = 9. 3 + 3, 
3 = 9. o+ 3, 
o 
20 Problemas em Teoria dos Números (Resolvidos e Propostos) 
42. Transformar para a base 10 os seguintes números 
(a) (2351)7 
(b) (1001110)2 
(c) (7706)s 
(d) (11122)4 
Solução: 
(a) (2351)7 = 1 · 'fl + 5 · 71 + 3 · 72 + 2 · 73 = 1 + 35 + 147 + 686 = 869. 
(b) (1001110)2 =o. 2° + 1. 21 + 1. 22 + 1. 23 +o. 24 +o. 25 + 1. 26 = 2 + 4 + 8 + 64 = 78. 
(c) (7706)s = 6 · 8° +O· 81 + 7 · 82 + 7 · 83 = 6 + 448 + 3584 = 4038, 
(d) (11122)4 = 2. 4° + 2. 41 + 1. 42 + 1. 43 + 1. 44 = 2 + 8 + 16 + 64 + 256 = 346. 
43. Mostrar que se 2n + 1 é um primo ímpar, então n é uma potência de 2. 
o 
Solução: Suponha que n não é potência de 2, isto é, n = 2am, com m > 1 ímpar e a~ O. Usando 
que se t é ímpar, então 
at + 1 =(a+ 1)(at-1 - at-2 + · · · + 1), 
obtemos, 2n + 1 = (22a)m + 1 = (22a + 1)(22a(m-1) - 22a(m-2) + · · · + 1), que é um número 
composto. O 
44. Provar que se d = (a, b), então d é o número de inteiros na sequência a, 2a, 3a, ... , ba que são 
divisíveis por b. 
Solução: (i) Solução 1. Suponha que ja é divisível por b, para algum 1 ~ j ~ b. Então b I ja e 
a I ja, portanto [a, b]l ja (isso porque ja seria um múltiplo comum de a e b). Daí ja = k[a, b], 
para algum k E Z. Para saber a quantidade de possíveis j, é suficiente encontrar a quantidade 
de possíveis k. Como ja ~ ab, então k é o maior inteiro tal que 
ab 
k[a, b] ~ ab ==? k ~ [a, b] =(a, b), 
onde usamos o Teorema 1.16. Logo, existem (a, b) possíveis k o que implica na existência de 
(a, b) possíveis j E {1, ... , b} tais que b I ja. 
(i i) Solução 2. O número de múltiplos de b no conjunto {a, 2a, ... , ba} é o mesmo número de 
múltiplos de ~ no conjunto {a, 2a, ... , ba}· Como (a,~) = 1, então é o número de múltiplos de 
~ no conjunto {1, 2, ... , b} que é igual a l l J = d, onde usamos o seguinte fato: 
O número de múltiplos de k no conjunto { 1, ... , n} é lI J . 
D 
Capítulo 1. Problemas resolvidos 21 
1. 2 Congruência 
Problemas resolvidos do Capítulo 2 
1. Mostrar que 47 J (223 - 1) 
Solução: Temos que 26 = 64 = 17 (mod 47). Elevando ao cubo, obtemos 
Finalmente, multiplicando por 25 obtemos, 
223 = 25 · 32 = 800 = 1 (mod 47). 
Portanto 47J 223 - 1. O 
2. Encontrar o resto da divisão de 734 por 51 e o resto da,-divisão de 563 por 29. 
Solução: Para resolver este problema usaremos o Teorema 2.3, que diz: 
Se ac = bc (mod m) e (c, m) = 1, então a- b (mod m). 
(i) Note que 72 = -2 (mod 51) e daí 734 = (72 ) 17 = ( -2)17 = -217 (mod 51). Por outro 
lado, 26 = 13 (mod 51) e então 212 = (26 ) 2 = 132 = 169 = 16 = 24 (mod 51). Aplicando o 
Teorema citado com a= 28 , b = 1, c= 24 em= 51, obtemos a congruência 28 = 1 (mod 51) 
e logo -217 = -2·(28) 2 = -2 (mod 51). Assim, 734 = -2 = 49 (mod 51). Portanto, o resto é 49. 
(ii) Como 29 é primo, então pelo Pequeno Teorema de Fermat, temos que 528 = 1 (mod 29) e, 
portanto, 
563 = 52-28+7 = (528)2. 57= 57 (mod 29). 
Mas 52 = -4 (mod 29) e daí, 
57 = 52·3+1 = (52) 3 • 5 = ( -4)3 • 5 = 23 · 5 = 28 (mod 29). 
Portanto, temos que 563 = 28 (mod 29) e o resto em questão é 28. o 
3. Mostrar que se pé um ímpar e a2 + 2b2 = 2p, então a é par e b é ímpar. 
Solução: Note que a é par, pois a2 = 2(p- b2). Suponha, por absurdo, que b é par. Então a= 2k 
e b = 2t. Daí 
2p = a 2 + 2b2 = 4k2 + 8t2 
e logo p = 4(k2 + 2t2) é par, contradizendo o fato de p ser ímpar. o 
4. Provar que para p primo (p- 1)! = p- 1 (mod 1 + 2 + 3 + · · · + (p- 1)). 
Solução: Queremos mostrar que (p-1)! ::=p-1 (mod 1+2+· · ·+(p-1)), ou seja, (p-1)! =p-1 
22 Problemas em Teoria dos Números (Resolvidos e Propostos) 
(mod (p-;)·P). Se p = 2, então 1! = 1 (mod 1). Se p > 2, então P21 é inteiro e assim basta-nos 
mostrar que (p- 1)! = p- 1 (mod p) e (p- 1)! = p- 1 (mod P21 ) pois (p, P21 ) = 1. 
Pelo Teorema de Wilson, temos (p- 1)! = -1 = p- 1 (mod p). Como P21 I (p- 1), então 
P21 I (p -1)!- (p- 1) e, portanto, (p -1)! = p -1 (mod P21 ) o que conclui a demonstração. O 
5. Encontrar o máximo divisor comum de (p- 1)!- 1 e p! (p primo). 
Solução: Suponha que d = ((p- 1)!- 1,p!), então dI ((p- 1)!- 1) e dI p!. Daí 
d I p( (p - 1)! - 1) - p! = -p e, portanto, d = 1 ou d = p. Mas pelo Teorema de Wilson, 
(p- 1)! = -1 (mod p). Assim, se d = p teríamos 1 = -1 (mod p) ::::} p = 2 logo se p = 2, 
((p- 1)!- 1,p!) = 2. Se p > 2, então 1 = d = ((p- 1)!- 1,p!). O 
6. Mostrar que para n ~ 4 o resto da divisão por 12 de 1! + 2! + 3! + · · · + n! é 9. 
Solução: Se n > 4, então n! =O (mod 12). Daí 1! + 2! + · · · + n! = 1! + 2! + 3! = 1 + 2 + 6 = 9 
(mod 12). O 
7. Mostrar que para n inteiro 3n2 - 1 nunca é um quadrado. 
Solução: Para solucionar esse problema usaremos o seguinte fato: 
Se x E .Z, então x 2 =O (mod 3) ou x 2 = 1 (mod 3). 
Na verdade, sabemos que dado x E .Z temos que x = 3.k + j com j E {0, 1, 2}. Assim, x 2 = 
(3k + j) 2 = 3(3k2 + 2kj) + j 2 . Mas 02 = O (mod 3), 12 = 1 (mod 3) e 22 = 4 = 1 (mod 3). 
Suponha, por absurdo, que 3n2 - 1 = m 2 . Claramente 3 não divide m (caso contrário 3 dividiria 
1). Logo m2 = 1 (mod 3) e, portanto, 1 = m 2 = 3n2 - 1 =O- 1 = -1 (mod 3) ::::} 3 I 2 o que é 
um absurdo. O 
8. Resolver as seguintes congruências. 
(a) 5x = 3 (mod 24) 
(b) 3x = 1 (mod 10) 
(c) 23x = 7 (mod 19) 
(d) 7x = 5 (mod 18) 
(e) 25x = 15 (mod 120) 
Solução: 
(a) x = 5 ( 5x) · 5 · 3 = 15 ( mod 24) 
(b) x = 7(3x) = 7 · 1 = 7 (mod 10) 
(c) Como 23x = 4x (mod 19), então queremos resolver 4x = 7 (mod 19). Daí x = 5(4x) = 
5 · 7 = 35 = 16 (mod 19). 
(d) -x = 5(7x) = 5 · 5 = 25 (mod 18) e daí x = -25 = 11 (mod 18) 
Capítulo 1. Problemas resolvidos 23 
(e) 5(5x) = 5 · 3 (mod 120), então pelo Teorema 2.3 implica que 5x = 3 (mod 24) e daí x = 
5(5x) = 5 · 3 = 15 (mod 24). 
o 
9. Mostrar que 5n3 + 7n5 = O (mod 12) para todo inteiro n. 
Solução: Temos que 5n3 + 7n5 = n 3 (5 + 7n2). Logo basta-nos mostrar que 3 I n 3 (5 + 7n2) e 
41 n 3 (5 + 7n2). Para isso usaremos que 
(i) se 3 não divide x, então x2 = 1 (mod 3); 
(ii) se 2 não divide x, então x2 = 1 (mod 4). 
Note que, se 3 I n, então 3 I n 3 (5 + 7n2) e se 3 não divide n, então n 2 = 1 (mod 3). Portanto, 
5 + 7n2 = 5 + 7 · 1 = 12 =O (mod 3). Se 2 I n, então 4 I n3 e, logo, 4 I n 3 (5 + 7n2). Por outro 
lado, se 2 não divide n, então n 2 = 1 (mod 4) e, portanto, 5 + 7n2 = 5 + 7 ·1 = 12 =O (mod 4). 
o 
10. Seja f(x) =ao+ a1x + · · · + anxn um polinômio com coeficientes inteiros onde an >O e n 2: 1. 
Mostrar que f(x) é composto para infinitos valores da variável x. 
Solução: Apresentamos duas soluções para esse problema. 
Solução 1. Primeiramente, observamos que como an > O, temos 
lim f(x) = +oo 
x~oo 
o que implica a existência de k E Z tal que f(y) > f(x) >O para todo y > x > k. Desta forma, 
se f(x) não assume nenhum valor primopara x > k então nada temos a provar. Por outro lado, 
se existir x0 > k e p primo tal que f(xo) = p, então tome Xn = xo + np, onde n E N. Então, 
Nesta soma, observamos que cada termo sendo somado é divisível por p, exceto, possivelmente, 
quando k = j. Portanto, existe N E N tal que, 
f(xn) = pN + tai (~)xoi(np) 0 = pN + f(xo). 
j=O J 
Isto mostra que p I f(xn) para todo n E N. Como k < xo < X! < x2 < . . . e p = f(xo) < 
f(xi) < j(x2) < ... a sequência crescente (f(xn))nEN contém infinitos múltiplos de p. 
Solução 2. Se f(x) é composto, para todo x E Z, o problema está terminado. Portanto, suponha 
que existe x0 E Z tal que f(xo) = p com p primo. Defina o seguinte polinômio na variável t: 
24 Problemas em Teoria dos Números (Resolvidos e Propostos) 
onde f(x) =ao+ a1x + · · · + anxn. Claramente, existe to> O tal que g(t) f/. {0, -1}, para todo 
t ~ to (caso contrário, um dos polinômios g(t) + 1 e g(t) teria infinitas raízes). Logo, para todo 
t ~ to, temos, 
Assim, 
f(xo + tp) = f(xo) + pg(t) = p + pg(t) = p(1 + g(t)). 
Mas setE Z, então 
f(xo + tp) = p(1 + g(t)) 
com p primo e (1 + g(t)) f/. {0, 1} pois t ~ to. Logo f(xo + tp) é composto para todo inteiro 
t ~to. O . 
11. Mostrar que se Pl e P2 são primos tais que P2 = Pl + 2 e Pl > 3 então Pl + P2 =O (mod 12). 
Solução: Basta-nos mostrar que 4 I (p1 +p2) e 3 I (p1 +P2)· Como Pl é ímpar e P2 = Pl +2, então 
Pl + P2 = 2pl + 2 = 2(pl + 1) que é múltiplo de 4 pois Pl + 1 é par. Para mostrar a divisibilidade 
por 3 note que p1 = 2 (mod 3). De fato, caso contrário, Pl = 1 (mod 3) (pois Pl > 3) e daí 
P2 = Pl + 2 = 1 + 2 = O (mod 3) o que não pode acontecer, portanto Pl = 2 (mod 3) e logo 
Pl + 1 =O (mod 3). Daí segue que 3 I 2(pl + 1) = Pl + P2· O 
12. Mostrar que para a e b inteiros temos que 3 I (a2 + b2 ) =} 3 I a e 3 I b. 
Solução: Supondo que 3 I (a2 + b2 ) então se 3 I a, então 3 I b. Suponha, por absurdo, que 3 não 
divida a então 3 não divide b e daí a2 = b2 = 1 (mod 3). Logo, 2 = 1 + 1 = a2 + b2 =O (mod 3) 
o que é um absurdo. 
o 
13. Sejam Pl, P2 e P3 primos tais que p = pf + p~ + P5 é primo. Mostrar que algum dos Pi 's é igual 
a 3. 
Solução: Note que p = pf + p~ + P5 > 3 e daí, se nenhum Pi é igual a 3, então p; = 1 (mod 3), 
para i E {1, 2, 3} e assim, p = pf + p~ + P5 = 1 + 1 + 1 =O (mod 3). O que implica 3 I p e logo 
p = 3 (pois pé primo). Portanto, pelo menos um dos Pi's é igual a 3. O 
14. Mostrar que 3x2 + 4x2 = 3 (mod 5) é equivalente a 3x2 - x2 + 2 =O (mod 5). 
Solução: Basta observar que 4 = -1 (mod 5) e que 2 = -3 (mod 5). o 
15. Mostrar que p I (P;) onde O < k < per. 
Solução: Note que (P;) = lf(P;~}). Se k I per, então lf é um inteiro múltiplo de p (pois k <per). 
Daí p divide (P;). Suponha que k não divida per, então (k,p) = 1. Logo a identidade anterior 
implica que p I k (Pk"), assim (p, k) = 1 nos dá p I (Pk"). O 
·, ... Capítulo 1. Problema.'; resolvidos 25 
16;· Seja p primo ~ M umeonjunto de p inteiros consecutivos. É possível encontrar M1 e M2 sub-
conjtmtos de M tais que M1 U M2 = M, M1 n M2 = 0, Mi f 0 de forma que . 
.· .· .. · ·: .· .. ·· rri=rrj? 
iEM1 jEM2 
Solução: Usaremos o seguinte fato: 
Paratodo n E N, somente um dos números n+1, n+2, ... , n+p é um múltiplo dep. De fato, caso 
contrário p dividiria n + ie n + j para 1 ~ i < j ~ p e daí, p I ( ( n + j) - ( n +i)) = j -i ~ p- 1, o 
que é um absurdo. LOgo em M existe apenas um múltiplo de p. Se M1 U M2 = M e M1 n M2 = 0, 
esse múltiplo de p, digamos tp, estaria em M1 ou M2. Sem perda de generalidade, suponha que 
· · tp E M1 e que M2 == { a1, ... , a"}. Daí, se, por absurdo, . 
rri= rrj 
iEM1 jEM2 
.· entâc:> tp I njEM2I~ aia2 ~ .. as. Logo i> dividiria um dos aj'S o que não pode acontecer, pois o . 
· único múltiplo de p, está em M1. O 
17. Seja f(x)um polinômio com coeficienteS inteiros. Mostrar que se /(-1), /(0) e /(1) não são 
divisíveis por 3, então f(n) f o para todo inteiro n. 
Solução~· Usaremos o seguinte fato: 
·Se f(x) E Z[x] e f(a) . O, então f(x) = (x- a)g(x) para algum g(x) E Z[x]. 
·Suponha que f(n) =O, para algum n E Z, então existe g(x) E Z[x] tal que f(x) = (x- n)g(x) 
e, ·portanto, f( ..:...1) = -(n + 1)g( -1), /(0) = -ng(O) e /(1) = -(n- 1)g(1). Como g( -1), g(O) 
e. g(1) são inteiros e 3 I (n- 1)(n)(n + 1), então 3 I /( -l)/(0)/(1). Portanto, 3 divide um dos 
.númer~ /(_.:_1), J(O) e /(1). Provamos~ resultado pela contrapositiva, O 
18. Mostrar qu~ 3Üi = 1 (mod 1i2). 
. . . . . . . . ·. 
SoluÇão: Observe que 310 ~ 1 = (35 -1)(35 + 1) = 242 · 244, mas 242 = 2 · 121 = 2 · 112 . Logo 
310 ~ l =O (inod 112 ) => 310 = 1 (mod 112). O 
19. Resolveros seguintes sistemas: 
(a) 
. (h) 
(mod 2) 
(mod 3) 
(mod 7) 
(1) 
(2) 
(3). 
{ 
2x = 1 (mod 5) (1) · 
3x = 2 {mod 7) (2) 
5x = 7 (mod 11) (3). 
26 Problemas em Teoria dos Números (Resolvidos e Propostos) 
(c) 
{ 
x = 7 (mod 11) (1) 
3x = 5 (mod 13) (2) 
1x = 4 (mod 5) (3). 
Solução: 
(a) x = 1 (mod 2) ::::} x = 2y + 1. Substituindo em (2), temos 2y = 1 (mod 3) ::::} y = 2 
(mod 3) portanto y = 3z + 2 e daí x = 2(3z + 2) + 1 = 6z + 5. Substituindo em (3), 
6z + 5 = 5 (mod 7) ::::} 7 I z::::} z = 1t. Daí x = 42t + 5::::} x = 5 (mod 42) e essa é a família 
de soluções. 
(b) 2x = 1 (mod 5) ::::} 4x = 2 (mod 5) ::::} x = 3 (mod 5) ::::} x = 5y + 3. Substituindo em 
(2), 3(5y + 3) = 2 (mod 7), ou seja 15y = -7 (mod 7) e daí 7 I y ::::} y = 1z. Portanto 
x = 5(7z) + 3 = 35z + 3 e substituindo em (3), ganhamos 5(35z + 3) = 7 (mod 11) ::::} 
175z = -8 (mod 11). Mas 175z = -8 (mod 11) ::::} z = 8 (mod 11) ::::} z = 11t + 8. Logo 
x = 35(11t + 8) + 3 = 385t + 283 ou seja x = 283 (mod 385). 
(c) De (1) temos que x = 11y+7. Substituindo em (2), 3(11y+7) = 5 (mod 13)::::} 33y = -16 
(mod 13) ::::} -6y = -16 (mod 13). Como ( -2, 13) = 1, então 3y - 8 (mod 13) ::::} 12y = 
32 = -7 (mod 13). Mas 12y = -y (mod 13) e daí y = 7 (mod 13) ::::} y = 13z + 7. 
Assim, x = 11(13z + 7) + 7 = 143z + 84. Substituindo em (3), temos 7(143z + 84) = 4 
(mod 5) ::::} 1001z = -584 (mod 5) ::::} z = 1 (mod 5) ::::} z = 5t + 1. Portanto x = 
143(5t + 1) + 84 = 715t + 227::::} x- 227 (mod 715). 
20. Encontrar todas as soluções de cada uma das seguintes congruências lineares. 
(a) 5x = 3 (mod 7) 
(b) 13x = 14 (mod 29) 
(c) 15x = 9 (mod 25) 
(d) 37x = 16 (mod 19) 
(e) 5x = 20 (mod 15) 
Solução: 
(a) 5x = 3 (mod 7) ::::} 15x = 9 = 2 (mod 7) =* x = 2 (mod 7) pois 15x = x (mod 7). 
D 
(b) 13x = 14 (mod 29) ::::} 26x = 28 (mod 29) ::::} -3x = 28 (mod 29) ::::} 3x = -28 = 1 
(mod 29) ::::} 30x- 10 (mod 29) ::::} x = 10 (mod 29). 
(c) Observe que (15, 25) = 5 e 5 não divide 9. Daí 15x = 9 (mod 25) não admite solução. 
(d) 37x = 16 (mod 19)::::} -x = 16 (mod 19) ::::} x = -16 = 3 (mod 19). 
(e) 5x = 20 (mod 15) ::::} 5x = 5 · 4 (mod 5 · 3)::::} x = 4 (mod 3) ::::} x = 1 (mod 3) .. 
o 
Capítulo 1. Problemas resolvidos 27 
21. Mostrar que a7 =a (mod 21) para todo inteiro a. 
Solução: Pelo Corolário 2.1, temos que 
a3 =a (mod3) e a7 =:a (mod7). 
Mas a3 = a (mod 3) implica em a7 = a2 ·3+1 = (a3 ) 2a = a2a = a (mod 3). Logo 3 1 a7 - a e 
7 I a7 - a. Como (3, 7) = 1, então 21 = 3 · 7 I a7 - a=> a7 =a (mod 21). D 
22. Mostrar que para a e b inteiros com (a, b) = 1 temos: 
ai/:J(b) + brfJ(a) = 1 (mod ab) 
Solução: Como (a, b) = 1, então pelo Teorema (Euler) 2.13, temos que 
arP(b) = 1 (mod b) e bi/:J(a) = 1 (moda) 
mas, 
brfJ(a) =O (mod b) e ai/:J(b) =O (moda). 
Daí 
ai/:J(b) + brfJ(a) = 1 (mod b) 
e, 
arP(b) + brfJ(a) = 1 (mod a). 
ou seja, 
a I ai/:J(b) + brfJ(a)- 1 e b I ai/:J(b) + brfJ(a)- 1. Mas (a, b) = 1 portanto 
ab I ai/:J(b) + brfJ(a) - 1 => arP(b) + brfJ(a) - 1 (mod ab) 
23. Provar ou dar contraexemplo: Se a em são inteiros (a, m) = 1, então 
m I (1 +a+ a2 + · · · + ai/J(m)-1 ). 
D 
Solução: Afirmamos que essa divisibilidade é falsa sempre que a = 1 e m > 1. De fato, nesse 
caso m 11 + 1 + 12 + 13 + · · · + 11/J(m)-1 = cp(m). Logo m I cp(m) que é um absurdo sem> 1, 
pois cp(m) < m param> 1. D 
24. Mostrar que se p e q são primos, p ~ q ~ 5, então p 2 - q2=O (mod 24). 
Solução: Devemos mostrar que 24 I p2 - q2 , ou seja, que 3 I p2 - q2 e 8 I r - q2 . Como p e q são 
primos maiores do que 3, então temos 2 casos. 
Caso 1. p =i (mod 3) e q = j (mod 3) com i=/: j e i,j E {1, 2}. Nesse caso, p+q = i+j = 3 =O 
(mod 3). 
28 Problemas em Teoria dos Números (Resolvidos e Propostos) 
Caso 2. p = q =i (mod 3) para algum i E {1, 2}. Nesse caso, p- q =i- i= O (mod 3). Logo, 
em qualquer caso temos p2 - q2 = (p- q)(p + q) =O (mod 3). 
Para provar que 8 I (p- q)(p + q), mostraremos primeiro que 4 I p- q ou 4 I p + q. A prova é 
análoga a demonstração acima. De fato, 
Caso 1. p =f= q (mod 4). Nesse caso, p + q = 1 + 3 =O (mod 4), pois p =i (mod 4), com q = j 
(mod 4), com i =f:j com i,j E {1,3}. 
Caso 2. p = q (mod 4). Nesse caso 4 I p- q. Logo 4 divide p- q ou p + q. Mas p- q e p + q são 
pares (subtração e soma de ímpares). Assim em qualquer caso 8 = 4 · 2 I (p - q) (p + q) = p2 - q2 . 
o 
25. Encontrar um sistema completo de resíduos módulo 11 formado somente por múltiplos de 6. 
Solução: Sabemos que {r1, r2,r3, ... , ru} = {0,1,2, ... , 10} é um sistema completo de resíduos 
módulo 11. Usando o Teorema 2.5, basta tomar, a= 6 e b = O. Logo {0, 6, 12, ... , 60} é um 
sistema completo de resíduos módulo 11. O 
26. Encontrar um sistema completo de resíduos módulo 7 onde todos os elementos são números 
primos. 
Solução: Basta encontrar 7 primos incongruentes módulo 7 (dois a dois). Note que os primeiros 
· 6 primos são incongruentes módulo 7: 2, 3, 5, 7, 11 e 13. Mas 17- 3 (mod 7), 19 = 5 (mod 7) 
e 23 = 2 (mod 7). No entanto afirmamos que 29 é incongruente a 2, 3, 5, 7, 11 e 13 módulo 7. 
De fato, 
29-2 = 27 = 6 
29-3 = 26 = 5 
29-5 = 24 = 3 
29-7 = 22 = 1 
29-11 = 18 = 4 
29-13 = 16 = 2 
(mod 7) 
(mod 7) 
(mod 7) 
(mod 7) 
(mod 7) 
(mod 7). 
Portanto, {2, 3, 5, 7, 11, 13, 29} é um sistema completo de resíduos módulo 7 formado só por 
primos. O 
27. Dado um primo pé sempre possível encontrar um sistema completo de resíduos módulo p formado 
só por primos? Justificar. 
Solução: Sim, é sempre possível! Um fato muito importante em Teoria analítica dos números é o 
Teorema das Progressões Aritméticas de Dirichlet que diz que se (a, b) = 1, então existem infinitos 
primos como solução da congruência x = a (mod b). Para encontrar um sistema completo de 
resíduos módulo p formado só por primos, basta encontrar p primos incongruentes módulo p. 
Pelo Teorema de Dirichlet, existem q~, q2, ... , qp-1 primos soluções de x = 1 (mod p), x = 2 
(mod p), ... , x = p- 1 (mod p), respectivamente. Logo esses primos são incongruentes, dois a 
dois módulo p e; portanto, {p, q1, ... , qp-1} é um sistema completo de resíduos módulo p. O 
28. Provar que, para todo número composto n, n =f: 4, a congruência (n- 1)! _O (mod n) é verda-
deira. 
Capítulo 1. Problemas resolvidos 29 
Solução: Se n é composto então n = ab, com 1 < a, b < n. Dividimos a prova em dois casos: 
Caso 1: Se a =I= b podemos supor, sem perda de generalidade, que a < b, então (n- 1)! -
( n - 1) ... b .. . a ... 1 = O ( mod n). 
Caso 2: Se a = b, então (a2 - 1)! = (a2 - 1) ... (2a) ... a .. . 1 = O (mod n), pois n = a2 e se 
a> 2 (pois n =I= 4), então a2 - 1 > 2a. O 
1.3 Teoria combinatória dos números 
Problemas resolvidos do Capítulo 3 
1. Quantos estudantes uma turma precisa conter, no mínimo, para que pelo menos dois estudantes 
tirem notas iguais no exame final, dado que as notas variam de O a 10 e apenas uma casa decimal 
é utilizada quando necessário? 
Solução: Existem 101 possíveis notas, a saber, 
o, 0.1, 0.2, ... 1, 1.1, 1.2, ... 2, ... '9.1, 9.2, ... 10. 
10 notas 10 notas 10 notas 
Logo para dois estudantes ter a mesma nota, precisamos de 102 alunos no mínimo. o 
2. Suponha agora que as notas possíveis são conceitos A, B, C, D e F. Qual o número mínimo de 
estudantes para que pelo menos 5 tenham conceitos iguais? 
Solução: Podemos ter 20 alunos divididos em 5 grupos em que cada grupo tem 4 alunos com o 
mesmo conceito. Logo 21 alunos é suficiente para garantir que pelo menos 5 tenham o mesmo 
conceito. O 
3. Existem 25 milhões de linhas telefônicas em um determinado Estado, identificadas por uma 
sequência de 10 dígitos da forma N X X - N X X - X X X X, onde N é um dígito entre 2 e 9, 
inclusive, X é um dígito qualquer e os primeiros 3 dígitos constituem o código de DDD. Quantos 
códigos distintos de D D D o Estado deve admitir para que a cada linha telefônica, corresponda 
uma sequência de 10 dígitos distinta das demais? 
Solução: Sem o DDD, podemos formar 8 · 10 · 10 · 10 · 10 · 10 · 10, isto é, 8 milhões de linhas 
telefônicas. Logo, com 4 possíveis DDD's podemos ter 32 milhões de linhas distintas e isso 
garante a possibilidade de termos 25 milhões de sequências de 10 dígitos distintas das demais. 
Veja que com apenas 3 isto não seria possível. 
o 
4. Existem 83 casas em uma rua. As casas são numeradas com números entre 100 e 262, inclusive. 
Mostre que pelo menos 2 casas têm números consecutivos. 
Solução: Observe que para não haver números consecutivos, o conjunto 
{100, ... '262} 
30 Problemas em Teoria dos Números (Resolvidos e Propostos) 
poderia ser particionado em dois subconjuntos, a saber, {100, 102, ... , 262} com 82 elementos 
e {101, 103, ... , 261} com 81 elementos. Logo 82 casas poderiam ser numeradas com números 
não consecutivos, mas 83 casas terão 82 números pares e 1 ímpar (logo pelo menos 2 pares de 
números consecutivos) ou 81 números ímpares e dois pares (logo pelo menos 4 pares de números 
consecutivos). D 
5. Quantas pessoas, no mínimo, devemos ter em um grupo para que possamos garantir a existência 
de pelo menos duas tendo nomes que começam com a mesma letra? (Considere um alfabeto com 
26 letras.) 
Solução: Como existem 26 letras no alfabeto, então precisaríamos de 27 pessoas no grupo. O 
6. Supondo que os números de RG sejam constituídos de 7 dígitos, quantas pessoas, no mínimo, 
devemos ter em uma cidade para que se tenha certeza da existência de pelo menos duas com os 
primeiros dois dígitos (da esquerda) iguais? (Admita que um RG possa ter O como dígito inicial.) 
Solução: Existem 10 possibilidades para cada um dos dois primeiros dígitos. Logo, 100 = 10 · 10 
possibilidades para o bloco formado pelos primeiros 2 dígitos. Assim, 101 pessoas garantem a 
existência desejada. D 
7. Uma escola possui 46 classes com uma média de 38 alunos por classe. O que se pode dizer a 
respeito do número de alunos na maior? 
Solução: Seja Ci o número de estudantes da i-ésima classe com i E {1, ... , 46} e C1 ~ C2 < 
... ~ c46 (sem perda de generalidade). 
c1 + c2 + · · · + c46 c46 + c46 + · · · + c46 
38 = 
46 
~ 
46 
= c46· 
Portanto, a maior sala tem pelo menos 38 alunos. D 
8. Um restaurante possui 62 mesas com um total de 314 cadeiras. É possível garantir a existência 
de pelo menos uma mesa com pelo menos 6 cadeiras? 
Solução: Suponha que cada mesa tem número de cadeiras menor do que 6. Daí existiriam no 
máximo 5 · 62 = 310 cadeiras, mas, por hipótese, existem 314. Portanto, pelo menos uma mesa 
tem mais do que 5 cadeiras. O 
9. Dados 12 livros de português, 14 de história, 9 de química e 7 de física, quantos livros devemos 
retirar (sem olhar) para que estejamos certos de termos retirado 6 de uma mesma disciplina? 
Solução: Podemos retirar 5 livros de português, de história, de química e de física. Logo 20 
livros. Assim, ao retirarmos 21 livros garantimos que pelo menos 6 são da mesma disciplina. O 
10. Mostrar que em um grupo de apenas 5 pessoas o resultado do Exemplo 3.17 não é necessariamente 
verdadeiro. (Sugestão: construir uma figura com os 5 pontos ligados por Cg = 10 segmentos de 
reta, onde não exista nenhum triângulo tendo todos os lados da mesma cor.) 
Capítulo 1. Problemas resolvidos 31 
Solução: Basta considerar a figura: 
A 
c D 
o 
11. Encontrar a maior subsequência crescente e a maior subsequência decrescente para cada uma das 
sequências abaixo: 
(a) 6,4,5,3,2; 
(b) 8,7,9,2,3,6,10,12,15,5; 
(c) 5,10,2,8,3,12,14,17,9,7;verificando se elas estão em concordância com o Teorema 3.3 (As respostas não são únicas.) 
Solução: 
(a) Crescente: 4, 5 
Decrescente: 6, 4, 3, 2; 6, 5, 3, 2. 
(b) Crescente: 2, 3, 6, 10, 12, 15 
Decrescente: 8, 7, 6, 5. 
(c) Crescente: 2,3,12,14,17; 5,10,12,14,17; 5,8,12,14,17 
Decrescente: 10, 8, 7; 12, 9, 7; 14, 9, 7; 17, 9, 7. 
12. Mostrar que 11 divide infinitos números da forma 363636 ... 36. 
Solução: Consideremos primeiro os 12 números abaixo, 
D 
32 Problemas em Teoria dos Números (R~olvidos e Propostos) 
36 
3636 
363636 
36363636 
3636363636 
363636363636 
36363636363636 
.3636363636363636 
363636363636363636 
36363636363636363636 
3636363636363636363636 
363636363636363636363636 
· .. ·: ,: 
. '·. 
. . .. 
. . . . . .. . . . 
Como temos mais de 11 números, pelo menos dois deles têm o mesmo res.to, quando dividido por 
11. Logo a diferença é divisível por 11. Mas esta diferença é da forma 3636 .. .' 360 ... 0000 = 
3636 ... 36 · 102k. Como (11, 102k) = 1, então 11 divide 3636, .. 36. A obtençãO de~ conjunto 
-infinito pode ser obtida pela repetição do que. foi feito, utilizand~se sequênci~ slifi~ientEmiente 
grandes para evitar repetições. · · O 
1.4 Funções Aritméticas 
Problemas resolvidos do Capítulo 4 
1. Avaliar r(n), O'(n) e <P(n) para os seguintes valores de n: 
(a) 10 .. 
·.· .. 
(b) 35 
(c) 200 
(d) 512 
(e) 10000 
(f) 1234 
Solução: Usaremos que se n = P1 121 ]J2 12~ •• ·Pkak, então, 
rrk (Piai+l - 1) . u(n) = 1 , i=l Pi-
e 
r(n) = (a1 + 1)(a2 + 1) ... (ak + 1). 
Então, 
Capítulo 1. Problemas resolvidos 33 
(a) Temos que 10 = 2 · 5, logo, o-(10) = ( 2;_=:l) · ( 5;_=-11) = 3 · 6 = 18, 
f/>(10) = 21- 1 . 51- 1 . (2- 1) . (5- 1) = 4 e 7(10) = (1 + 1) . (1 + 1) = 4. 
(b) Temos que 35 = 5 · 7, logo, o-(35) = ( 5;.=-l) · ( 7;_=-11) = 6 · 8 = 48, 
f/>(35) = 51- 1 . 71- 1 . (5- 1) . (7- 1) = 24 e 7(35) = (1 + 1) . (1 + 1) = 4. 
(c) Temos que 200 = 23 ·52, logo, o-(200) = (2;.=-l) · (5;.=-l) = 15 · 31 = 465, f/>(200) = 
23- 1 . 52- 1 . (2- 1) . (5-1) = 80 e 7(200) = (3 + 1) · (2 + 1) = 12. 
(d) Temos que 512 = 29 , logo, o-(512) = e;~J: 1 ) = 1023, f/>(512) = 29- 1 · (2- 1) = 28 = 256 e 
7(512) = (9 + 1) = 10. 
(e) Temos que 10000 = 24 ·54 , logo, o-(10000) = ( 2;.=-l) · ( 5;.=-l) = 31· 781 = 24.211, f/>(10000) = 
24- 1 .54- 1 . (2- 1). (5-1)= 4000 e 7(10000) = (4 + 1) · (4 + 1) = 25. 
(f) Temos que 1234 = 2 · 617, logo, o-(1234) = ( 22
2_=-l) · ( 6l17;.=-l) = 3 · 618 = 1854, f/>(1234) = 
· 21- 1 .6171- 1 . (2 -1). (617 -1) = 616 e 7(1234) = (1 + 1) · (1 + 1) = 4. 
o 
2. Para quais valores de m, f/>(m) é ímpar? 
Solução: f/>(m) é ímpar somente param= 1 em= 2. A solução será apresentada em conjunto 
com a do Problema 6, que pede para mostrar que f/>(m) é par, para todo m > 2. O 
3. Para quais valores de m, f/>(m) dividem? 
Solução: Dividiremos nossa análise em 2 casos: 
Sejam= P1a1P2a2 •• ·Pkak com P1 < P2 < · · · < Pk· 
(i) Caso 1. Se k = 1. Nesse caso f/>(p1a 1 ) = P1a1 - 1(p1- 1) e logo, </>~) - P1a/\~1 _1 ) -
= P~~ 1 E Z se, e somente se, P1 = 2. Logo, m = 2a tem a propriedade desejada para todo a~ O. 
(ii) Caso 2. Se k ~ 2, então P1 = k = 2. 
De fato, como 
f/>( m) = m ( 1 - :
1 
) ... ( 1 - :k) , 
então, 
m _ P1P2 · · · Pk E z 
f/>(m) (p1 - 1)(p2 - 1) ... (pk- 1) · 
Logo se P1 > 2 então P1 - 1 é par e divide P1P2 ... Pk que é ímpar. Logo P1 = 2 e, portanto, 
4>( m) I m se, e somente se, 
2P2 .. ·Pk 
(P2 - 1) ... (pk - 1) 
é inteiro. 
Se k > 2, então (P2- 1)(p3- 1) _ O (mod 4) e logo 2p2 .. ·Pk = O (mod 4) o que é absurdo, 
desde que P2 .. ·Pk é ímpar. Daí, k = 2 e assim m = 2a1 P2a2 . Mas f/>(m) I m implica P2 -1I2P2. 
34 Problemas em Teoria dos Números (Resolvidos e Propostos) 
Como ÚY.!- l,P2) = 1, então P2- 1 I 2 => P2 - 1 = 1 ou P2- 1 = 2. Como P2 é ímpar, então 
P2 - 1 = 2 => P2 = 3. Logo, m da forma 2a3b tem a propriedade desejada, para todos a, b 2: O. O 
4. Mostrar que se m e n são inteiros positivos tais que m I n, entào 4;( m) I 4;( n). 
Solução: Sejam= P1°1P2°2 •• • p8°". Como, por hipótese, m In devemos ter que 
com /3i 2: ai. Como 
temos que 
.+.( ) _ f31 {38 "Yl "Yr ( 1 ) ( 1 ) ( . 1 ) ( 1 ) _ 'P n - Pl ••• Ps Ql ••• Qr 1 - Pl . . • 1 - Ps 1 - Ql • • • 1 - Qr -
1'1 /'r Ih -al fJ. -a. a1 a. (1 1 ) (1 1 ) (1 1 ) (1 1 ) Ql .. · Qr Pl " • P• Pl " • P• - ~ " ' - Ps - Ql " ' - Qr = 
<P( 171) 
= Ql"Yl .• • qr"YrPlf31-al .. ·Psf3.-a•rp(m) (1- q~) ... (1- :r) 
e isso conclui a demonstração, pois 
"Yl "Yr ( 1) ( 1) Ql ••• Qr 1 - Ql • • • 1 - Qr E Z. 
5. Refazer a demonstração do Teorema 4.3 param= 5 e n = 9. 
Solução: Considere a lista, 
1 6 11 16 21 26 31 36 41 
2 7 12 17 22 27 32 37 42 
3 8 13 18 23 28 33 38 43 
4 9 14 19 24 29 34 39 44 
5 10 15 20 25 30 35 40 45 
o 
Note que se (5 · 9,j5 +r)= 1, com O~ j ~ 8 e 1 ~r~ 4 então (5,j5 +r)= 1 e (9,j5 +r)= 1. 
Daí (5, r)= (9,j5 +r)= 1 =>r= 1, 2, 3, 4. Para essas linhas, (5, r)= 1, então 
r, 5 + r, 2 · 5 + r, ... , 8 · 5 + r 
forma um sistema completo de resíduos módulo 9. Então em cada linha temos 4;(9) = 4>(32) = 
3 · (3 - 1) = 6 primos entre si com 9. Ou seja, 
Logo, 4;(5 · 9) = 4;(45) = 24 = 4 · 6 = 4;(5)4;(9). o 
Capítulo 1. Problemas resolvidos 35 
1 11 16 26 31 41 
2 7 17 22 32 37 
8 13 23 28 38 43 
4 14 19 29 34 44 
6. Mostrar que if>(m) é par sem> 2. · 
Solução: Para esse problema apresentaremos duas soluções. 
(i) Solução 1. Como, param= P1°1P2°2 .. ·Pk0 k com P1 < P2 < · · · < Pk temos, 
A..( ) _ 01-1 02-1 Ok-1(p 1)(p 1) (p 1) 
'f' m - P1 P2 · · · Pk 1 - 2 - · · · k - , 
então se k ~ 2 teremos que P2 -1 é par e logo if>(m) é par. Quando k = 1, m = p1°1 temos, 
Se Pl > 2, então P1 - 1 é par e o resultado segue. Para P1 = 2 temos 
que é par sempre que a 1 - 1 ~ 1, ou seja para todo m > 2. 
(i i) Solução 2. Essa solução é mais de interpretação da função if>. Sua definição é 
if>(n) = #{k E {1, ... ,n} I (k,n) = 1}. 
Note que se n > 1, (n, n) > 1. Daí, para n > 1, if>(n) pode ser definida como 
if>(n) = #{k E {1, ... ,n -1} I (k,n) = 1}. 
Caso 1. Quando n é ímpar, então podemos particionar 
{1, ... , n -1} = { 1, ... , n ~ 1 } U { n; 1 , ... , -1n} =A U B. 
Como (k, n) = (n- k, n) para todo 1 :::; k:::; n- 1, então sempre que x E A é tal que (x, n) = 1, 
então (n- x, n) = 1 e n- x E B. Logo os números relativamente primos com n aparecem em 
pares e, portanto, #{k E {1, ... , n- 1} I (k, n) = 1} é par. 
Caso 2. Se n é par e maior do que 2 a prova é a mesma do caso 1, observando que a partição 
agora é 
{1, ... , n- 1} = { 1, ... , ~ - 1} U { ~} U { ~ + 1, ... , n- 1}. 
e (n, ~) = ~ > 1, se n > 2. o 
7. Mostrar que existem infinitos inteiros m para os quais if>(m) é um quadrado perfeito. 
Solução: Basta tomar m = 22k+l para todo k 2: O. De fato, nesse caso 
o 
36 Problemas em Teoria dos Números (Resolvidos e Propostos) 
8. Mostrar que se f é multiplicativa, então f(1) = 1. 
Solução: Temos que f(1) = f(1 · 1) = f(1)f(1) = f(1) 2 • Logo, f(1) E {0,1}. Se f(1) =O, então 
para todo n E N temos 
f(n) = f(1 · n) = f(1)f(n) =O 
e f seria nula c'ontradizendo a Definição 4.3. Portanto, f(1) = 1. 
9. Mostrar que para qualquer inteiro positivo n 
3 rr JL( n + i) = o. 
i=O 
o 
Solução: Para todo n E N, 4 divide um dos números n, n + 1, n + 2, n + 3. Em particular 
JL(n + j) =O, para algum j E {0, 1, 2, 3}. Daí, 
3 rr JJ.(n +i) = JL(n)JL(n + 1)~t(n + 2)~t(n + 3) _=o. 
i=O 
o 
10. Mostrar que um inteiro pé um primo se, e somente se, a(p) = p + 1. 
Solução: Se pé primo, seus únicos divisores positivos são 1 e p. Daí a(p) = p+ 1. Por outro lado, 
supondo p composto, isto é p = ab, com 1 < a, b < p temos que 1, a e p são divisores distintos 
de p e, portanto, a(p) ~ 1 +a+ p =/: 1 + p. Logo a(p) =/: p + 1. O 
11. Mostramos que as funções r(n) e a(n) são multiplicativas. Mostrar que nenhuma delas é com-
pletamente multiplicativa. 
Solução: Tome a= 22 e b = 2. Então, r(ab) = r(23) = 4. Por outro lado, r(a)r(b) = r(22)r(2) = 
(2 + 1) · (1 + 1) = 6. Tome agora a = 6 e b = 3. Então a(ab) = a(2. 32) = ( 2;~l) . ( 3;~l) = 
3 ·13 = 39. Poroutro lado, a(a)a(b) = a(6)a(3) = a(2)a(3)2 = (2 + 1) · (3 + 1)2 = 3 ·16 = 48. O 
12. Mostrar que para um inteiro fixo r, a função h(n) = nr é completamente multiplicativa. 
Solução: Dado r E Z, temos 
h(mn) = (mnr = mrnr = h(m)h(n) 
para todos m,n E N. o 
13. Mostrar que as funções F(n) = f(n)g(n) e G(n) = ~f:~ são multiplicativas sendo f(n) e g(n) 
multiplicativas com g(n) =/:O. 
Solução: Se (m, n) = 1, então 
G(mn) = f(mn) = f(m)f(n) = f(m) f(n) = G(m)G(n) 
g(mn) g(m)g(n) g(m) g(n) · 
Capítulo 1. Problemas resolvidos 37 
Também, 
F(mn) = f(mn)g(mn) = (f(m)f(n))(g(m)g(n)). 
Logo 
F(mn) = (f(m)g(m))(f(n)g(n)) = F(m)F(n). 
o 
14. Mostrar, através de um exemplo, que a função F(n) = 'Edln f(d) nem sempre é completamente 
multiplicativa caso f(d) seja. 
Solução: Basta tomar f(n) = n que é completamente multiplicativa (vide Problema 12 com 
r= 1), mas 
F(n) = Lf(d) = Ld = a(n) 
dln dln 
não é completamente multiplicativa (vide Problema 11). o 
15. Mostrar que para qualquer inteiro positivo n > 1 existem infinitos inteiros m tais que r(m) = n. 
Solução: Dado n E N, a imagem de pn-1 pela função r é n para todo primo p. De fato, 
r(pn-1) = ((n- 1) + 1) = n. 
A infinitude é devido a existência de infinitos primos. o 
16. Encontre o menor inteiro positivo m para o qual a(m) = 6. 
Solução: Como 5 é primo, então a(5) = 5 + 1 = 6 e a(1) = 1, a(2) = 3, a(3) = 4 e a(4) = 7. 
Daí n = 5 é o menor inteiro positivo tal que a(n) = 6. O 
17. Encontre o menor inteiro positivo m para o qual </>(m) = 6. 
Solução: Como 7 é primo, então if>(7) = 7- 1 = 6 e c/>(1) = c/>(2) = 1, </>(3) = c/>(4) = if>(6) = 2 e 
c/>(5) = 4. Logo 7 é o número procurado. O 
!..(!!2 
18. Mostrar que Tidln d = n 2 • 
Solução: Usaremos o seguinte fato, 
{d: dI n} ={~:dI n} =? IT d = IT ~· 
dln dln 
Logo, 
(rr d) 
2 
- (rr d) (rr d) - (rr d) (rr ~) -
dln dln dln dln dln 
38 Problemas em Teoria dos Números (Resolvidos e Propostos) 
~ 
Daí Tidln d = n 2 . 
= (rr d· ~) 
dln 
= rr n = nr(n)_ 
dln 
19. Mostrar que se f é multiplicativa, mIne (m, ~) = 1, então f(~)= Jg;!)" 
Solução: Como f é multiplicativa e (m, ~) = 1, então 
f(n) =f ( m :) = f(m)f (:) => ;(:) =f(:) . 
D 
o 
20. Seja h(n) o número de fatores primos distintos de n. Por exemplo, h(15) = h(21) = 2 e h(30) = 3. 
Seja q(n) = ah(n) onde a está fixado. Mostrar que q(n) é multiplicativa mas não é completamente 
multiplicativa. 
Solução: Afirmamos que se (m, n) = 1, então 
h(mn) = h(m) + h(n) 
De fato, se ( m, n) = 1, então, m = Pl a:1 P2 a:2 • • • Pk a:k e n = r1 fh r2!32 • • • r 8 /3., onde os p~s e r~s são 
primos distintos. Daí, 
h(mn) = k + s = h(m) + h(n). 
Portanto, se ( m, n) = 1, então 
q(mn) = ah(mn) = ah(m)+h(n) = ah(m)ah(n) = q(m)q(n). 
Na verdade, q( n) é completamente multiplicativa somente quando a = 1. De fato, se a =I= 1 (e 
zero), então param= 6 e n = 15 
Por outro lado, 
Logo q(6 · 15) =I= q(6)q(15), se a =I= 1 (e zero). o 
21. Mostrar que existem infinitos inteiros m para os quais 10 I cjJ(m). (Sugestão: cjJ(11) = 10). 
Solução: Como c/J(ll) = 10, então se pé primo diferente de 11, temos (11,p) = 1 e daí 
cjJ(11p) = cjJ(11)cjJ(p) = 10(p- 1) e cjJ(112 ) = 11·10. 
Daí 10 I c/J(llp), para todo primo p. o 
Capítulo 1. Problemas resolvidos 39 
22. Mostrar que se n é um inteiro, então 
~(2n) = {~(n), se n é ímpar 
2~(n), se n é par 
Solução: Se n é ímpar, então (n, 2) = 1. Daí, 
~(2n) = ~(2)~(n) = 1~(n) = ~(n). 
Se n é par, então n = 2km com m ímpar e k 2: 1. Daí, 
~(2n) = ~(2 · 2km) = ~(2k+lm) = ~(2k+l)~(m) = 2k~(m) = 
= 2(2k-l~(m)) = 2(~(2k)~(m)) = 2~(2km) = 2~(n). 
o 
23. Mostrar que todo inteiro positivo pode ser escrito como soma de números de Fibonacci distintos 
e não consecutivos. 
Solução: Esse resultado é conhecido como Teorema de Zeckendõrff. A prova será feita por 
indução. 
Caso base: n = 1 = F1 que é a soma trivial. 
Hipótese de indução: n = Fm1 + Fm2 + · · · + Fmk' com mi+l- mi 2: 2, para i E {1, ... , k- 1}. 
Daí, 
n + 1 = 1 + Fm1 + Fm2 + · · · + Fmk. 
Se m1 2: 3, o resultado está provado pois 1 = F1 e logo n + 1 = 1 + Fm1 + Fm2 + · · · + Fmk e 
ffil- 1 2: 2. 
Se m1 = 2 (o caso m 1 = 1 é análogo e na verdade podemos supor, sem perda de generalidade 
que m1 = 2, pois F1 = F2 = 1), então, n + 1 = F1 + F2 +Fm2 + · · · + Fmk e daí n + 1 = ......__.., 
F3 
Fa + Fm2 + · · · + Fmk· Novamente, se m2 2: 5 o resultado está provado. Se m2 = 4, então 
n + 1 = F a + F4 + Fm3 + · · · + Fmk e logo n + 1 = Fs + Fm3 + · · · + Fmk · ......__.., 
Fs 
Note que esse processo continua até termos somente um número de Fibonacci ou a soma de 
números de Fibonacci com índices não consecutivos. O 
1.5 Resíduos Quadráticos 
Problemas resolvidos do Capítulo 5 
1. Calcular (~), (~~~) e (~~V-
Solução: (i) Como 48 = 24 · 3 (mod 3) e 97 = 1 (mod 3) então, 
(:~)=(2:;3)=(~;)(~)=(~)= 
40 Problemas em Teoria dos Números (Resolvidos e Propostos) 
(3-1)(97-1) (97) 48 (1) = ( -1) -2 -2- 3 = ( -1) . 3 = 1 
onde usamos a lei da reciprocidade quadrática. 
(ii) Como 235 = 5 · 47, então 
( 
235) ( 5 . 4 7) ( 5 ) ( 4 7 ) 
991 = 991 = 991 991 = 
= ( -1)(521 )(99~-1) (9:1) ( -1)(4721 )(99~-1) (9::) = 
=- (9:1) (9:;) =- (~) (4~) =- (~
2
) (~~) = -1. 
(iii) Como 138 = 2 · 3 · 23, então: 
( ~!~) = ( 8~3) ( 8!3) ( 82833) · 
Mas, ( 8~3 ) = -1, já que 883 = 3 (mod 8) (veja Teorema 5.10). 
(
8
!
3
) = (-1)(3;1)(88;-1) (8~3) = _ (~) = _1 
já que 883 = 1 (mod 3). 
( E_)= (-1)(23;1)(88;-1) (883) =- (~) = (-3
2
) = 1 
883 23 23 23 
(corolârio 5.2). O 
2. Encontrar os resíduos quadráticos e não quadráticos de 19 e 23. 
Solução: (i) p = 19. Basta olhar os restos da divisão de x 2 por 19 quando x E {1, ... , 18}. Ou 
seja, 
12 = 1 
22 = 4 
32 = 9 
42 = 16 
52 = 6 
62 = 17 
72 = 11 
82 = 7 
92 = 5 
(mod 19) 
(mod 19) 
(mod 19) 
(mod 19) 
(mod 19) 
(mod 19) 
(mod 19) 
(mod 19) 
(mod 19). 
Pelo Teorema 5.5, basta encontrarmos os primeiros 9 = 1921 resíduos quadráticos módulo 19 que 
são: {1,4,5,6,7,9,11,16,17}. 
(ii) p = 23. De modo análogo ao caso p = 19, temos que 
{1,2,3,4,6,8,9,12,13,16,18} 
são os 11 = 23; 1 resíduos quadráticos módulo 23. o 
Capítulo 1. Problemas resolvidos 41 
3. Mo8trar que nãO existe n tal que 71 (41i2 ~ 3). 
Soluçao·: Suponha ·qu~ 7.1 4n2 - 3, então 7 1 [(4n2 - 3) + 7] = 4(n2+ 1). Como (7, 4) = 1, então 
7 I n2 + 1,·ou seja, ....::.1 é resíduo quadrâtico módulo 7. Por outro lado, o Teorema 5.9 implica em, . '. . . . 
(-1) (7-1). . 3 . 7 :._ ( -1) 2"" =( -1) = -1. 
Es8e al)~urdo confirma o resultado. 
.·. · .. :;··· 
4. ·Mo~tta~ que se·p e q são primas ímpares com P = q + 4a, então· 
(a) (~) = (~)" 
(h)(~) (~) 
. Soi~ção: Suponha que p. = q + 4a, com p e q. primos . 
. · (~) Com~p ~ q + 4a_:= 4a (mod q) e(~)= e:)= 1, então, 
. (b) · P~lo item . (a) e a lei da r~ciprocidade quadrâtica temos, 
. (~) = (~) = (-1)(9)(~) (~) = (-1)(9)(~) (p ~ 4a). 
Como p- 4a = -4a (mod p), ( -;,1 ) = ( -1)(?) e (~) = 1, então: 
. . 
(~) .· (~1)(?)(~) (-:~) = (-1)(?)(?) (~1 ) (~) (~) = 
. = (-1)(9)(~) (~) . 
o 
. . Note que p = q (mod 4a), então p- 1 = (q + 1) - 2 (mod 4a) e daí P21 = 9~ 1 - 1 
(mod 2a)._ O~ seja, P21 e 9~ 1 tem paridades diferentes. Em particular, ( P21 ) ( 9~1 ) é par 
.. · . (!!::.!) ( tt!) .. e.daí ( -1) 2 2 = 1. Portanto, 
. (~) = (~). 
o 
5. Y~do o Teorema 5.12 mostrar que se pé um primo ímpar, então 
(~·) '== { 1, se p = ±1 (mod 12) . p -1, se p = ±5 (mod 12) 
42 Problemas em Teoria dos Números (Resolvidos e Propostos) 
Solução: O Teorema 5.12 garante que (~) = ( -1)(~) (~). 
Se p = 1 (mod 12), então P21 ê par, p = 1 (mod 3) e daí 
(~) = (~) = 1. 
Se p = -1 (mod 12), então, 
(~) = ( -1)(~) (~) = ( -1)(~) ( ~1 ) = ( -1)(~) ( -1)(321 ) = ( -1)(p+l)/2 = 1, 
pois (p + 1)/2 =O (mod 6). 
Se p = 5 (mod 12), então, p = 2 (mod 3) e daí 
(3) (2.=.!.) (2) (2.=.!.) (E±!) p = ( -1) 2 3 = ( -1) 2 ( -1) = ( -1) 2 
pois (~) = -1. Mas ptl = 3 (mod 6) e daí ptl ê ímpar. Assim, (~) = -1. 
Se p = -5 (mod 12), então, p = 1 (mod 3) e daí 
Mas P21 = -3 (mod 6), implicando P21 ímpar. Ou seja O)= -1. 
Resumindo, 
(~) = {1, se p = ±1 (mod 12) P -1, se p = ±5 (mod 12) 
D 
6. Fornecer uma congruência descrevendo todos os primos para os quais 5 ê um resíduo quadrático. 
Solução: Queremos que (~) = 1. Pela lei da reciprocidade quadrática, (~) = (~). Ou seja, 
queremos os primos p que são resíduos quadráticos módulo 5. Sabemos que existem 5; 1 = 2 
classes congruentes módulo 5. Como, 
Se p = 1 (mod 5), então (;) = (~) = (~) = 1. 
Se p = -1 (mod 5), então(~)=(~)= (51)= (-1)CS2 1 ) = 1. 
Daí, temos que p = ±1 (mod 5). 
7. Mostrar que 17 ê um resíduo quadrático módulo 19 utilizando o Lema de Gauss. 
D 
Capítulo 1. Problemas resolvidos 43 
Solução: O Lema de Gauss nos diz que se {t1, t2, ... ,tE=!} são os restos de {a, 2a, ... , P;1a} 
2 
módulo p, então(~)= (-lY onde r= #{j E {1, ... , P;1 } I ti> H· 
Seja a = 17 e p = 19, então ~ = 9,5 e P;1 = 9. Assim, 
p-1 
{a, 2a, ... , -
2
-a} = {17, 34, 51, 68, 85,102,119,136, 153} 
e logo, 
{ti. t2, ... ,t9} = {17, 15, 13, 11, 9, 7, 5, 3, 1}, 
portanto r= 4. Daí n~) = ( -lY = ( -1)4 = 1. 
8. Dizer se a congruência 3x2 - 12 (mod 13) possui, ou não, soluçãO. 
o 
Solução: Se 3x2 = 12 (mod 13) então 3x2 = 3 · 22 (mod 13). Como (3, 13) = 1, então x2 = 22 
(mod 13) ex= 2, por exemplo, é solução dessa congruência. O 
9 A:vali [327] [429] (181] · ar 635 • 563 e 991 · 
Solução: (i) Temos que 
[327] = (327) (327) =(~)(E_)= (-1)(~)(-1)(~)(~) (127) = 635 5 127 5 127 73 
=-(~;)=-(~!)=-(2;t)=-(~)(~)= 
= -(- 1)(*\-1)(~)(Y) (733) = _ (733) =_(~)=-L 
(i i) Como 563 é primo, temos: 
[429] = (429) = (-134) = (-1)(~) (134) =- (~) =- (_2_) (~) = 563 563 563 563 563 563 563 
= -( -1) -s- ( -1) -r -r- - -- - - - - -(563-1) (67-1)(563-1) (563)- (563)- (27) -67 67 67 
(33 ) ( 3) (3-1)(87-1) (67) (1) =- 67 =- 67 = -(-1) -r -r 3 = 3 = 1. 
(iii) Como 181 e 991 são primos, então: 
[181] = (181) = (- (~)(~) (991) = (991) = (~) = (~) = 991 991 1) 181 181 181 181 
( 2 ) ( 43) (~) (43-1)(181-1) (181) (181) = - - =(-1) (-1) -r -r- - =- - = 181 181 43 43 
= - ( :3) =- ( !: ) = -1. 
o 
44 Problemas em Teoria dos Números (Resolvidos e Propostos) 
10. Sendo p e q primos ímpares distintos com p = q - 3 (mod 4) mostrar que p é um resíduo 
quadrâtico módulo q se, e somente se, q não é resíduo quadrâtico módulo p. 
Solução: Pela Lei da reciprocidade quadrâtica de Gauss, 
(~) = (-1)(~)(~) (~). 
Como p = q = 3 (mod 4), então p;i e ª;1 são ímpares e logo ( ~) = - (!). Daí pé resíduo 
quadrâtico módulo q (isto é (~) = 1) se, e ~omente se, (!) = -1, ou seja, q não é resíduo 
quadrâtico módulo p. 
1.6 Raízes Primitivas 
Problemas resolvidos do Capítulo· 6 
1. Encontrar uma raiz primitiva módulo 
(a) 5 
(b) 6 
(c) 10 
(d) 11 
(e) 18 
(f) 19 
Solução: 
o 
(a) Temos que 4J(5) = 4 e D+(4) = {1,2,4}. Daí 2 é raiz primitiva módulo 5, pois 21 = 2 
(mod 5), 22 = 4 (mod 5) e 2c/l(S) = 1 (mod 5). 
(b) Temos 4J(6) = 2, logo 5 é raiz primitiva módulo 6, pois 51 = 5 (mod 6) e 5cP(6) = 1 (mod 6). 
(c) TeQlos 4J(10) = 4, logo 3 é raiz primitiva módulo 10, pois 3~ = 3 (mod 10), 32 = 9 (mod 10) 
e 3c/l(10) = 1 (mod 10). 
(d) Temos 4J(11) = 10 e n+(lO) = {1,2,5,10}. Assim, 2 é raiz primitiva módulo 11, pois 21 = 2 
(mod 11), 22 = 4 (mod 11), 25 = 10 (mod 11) e 2cf>(ll) = 1 (mod 11). 
(e) Como 4J(18) = 6 e D+(6) = {1,2,3,6}, então 5 é raiz primitiva módulo 18, pois 51 = 5 
(mod 18), 52 = 7 (mod 18), 53 = 17 (mod 18) e 5cP(18) = 1 (mod 18). 
(f) Observe que 4J(19) = 18 e n+(18) = {1,2,3,6,9,18}. Também 21 =: 2 (mod 19), 22 =: 4 
(mod 19), 23 = 8 (mod 19), 26 = 7 (mod 19), 29 = 18 (mod 19) e 2cP(19) = 1 (mod 19). 
Logo 2 é raiz primitiva módulo 19. 
o 
Capítulo 1. Problemas resolvidos 45 
2. Encontrar,o número de raízes primitivas dos seguintes primos (a) 5, (b) 17, (c) 11, (d) 23, (e) 13 
e (f) 31. 
Solução: Pelo Teorema 6.5, basta calcular if>(if>(p)), para p E {5, 11,13, 17, 23,31}. Portanto, 
if>(if>(5)) = 2, if>(if>(ll)) = 4, if>(if>(13)) = 4, if>(if>(17)) = 8, if>(if>(23)) = 10 e if>(if>(31)) = 8. O 
3. Mostrar que sem é um inteiro positivo e a um inteiro, (a, m) = 1, tal que ordma = m- 1, então 
m é primo. 
Solução: Temos que ordma I if>(m) (pelo Corolário 6.1), daí m- 1 I if>(m), mas param > 1, 
if>(m) :::; m- 1. Portanto, if>(m) = m- 1 vale se, e somente se, m é primo. D 
4. Mostrar que os divisores primos ímpares de um inteiro n 2 + 1 são da forma 4k + 1. 
Solução: Suponha que p I n 2 + 1 e p = 3 (mod 4). Então n 2 = -1 (mod p). Mas (n,p) = 1 
1 1 ~ e logo pelo Pequeno teorema de Fermat, nP- = 1 (mod p). Portanto, 1 = nP- = (n2 ) 2 = 
(-1)~ = -1 (mod p), o que é um absurdo. Aqui usamos que P21 é ímpar, já que p = 3 
(m~~- O 
5. Sendo p > 2, primo, e a > 1 um inteiro, mostrar que os divisores primos ímpares de aP + 1 são 
divisores de a + 1 ou são da forma 2np + 1. 
Solução: Seja q primo tal que q I (aP + 1) e a ~ -1 (mod q), então aP = -1 (mod q) o 
que implica a 2P = 1 (mod q). Como aq-1 = 1 (mod q), então aC2p,q-1) = 1 (mod q), mas 
(2p, q- 1) E {1, 2,p,2p }. 
Se a= 1 (mod q), então -1 = aP = 1 (mod q), absurdo. 
Se a2 = 1 (mod q), escreva p = 2t + 1, então -1 = aP = a 2H 1 =a (mod q) implicando q I a+ 1, 
absurdo. Claramente aP ~ 1 (mod q). Daí (2p, q- 1) = 2p ou seja, 2p I q- 1 => q- 1 = 2np => 
q = 2np + 1. O 
6. Mostrar que se a é uma raiz primitiva módulo p (primo) com p = 1 (mod 4) então -a também 
é raiz primitiva. 
Solução: Suponha que existe n < p- 1, tal que ( -a)n = 1 (mod p). Então a2n = 1 (mod p). 
Como ordpa = p- 1, então pelo Teorema 6.1, p- 1 I 2n e assim P21 In e como P21 é par (pois 
p = 1 (mod 4)), então n é par. De (-a)n = 1 (mod p) obtemos an = (-1)n = 1 (mod p) (pois 
n é par) absurdo pois ordpa = p - 1 > n. 
D 
7. Mostrar que se a é um resíduo quadrático módulo p primo ímpar, então a não é raiz primitiva 
módulo p. 
Solução: Se a é resíduo quadrático módulo p, então p não divide a. Seja xo E Z, tal que XQ 2 =a 
46 Problemas em Teoria dos Números (Resolvidos e Propostos) 
(mod p). Portanto, p não divide xo e daí, pelo Pequeno Teorema de Fermat, x 0P-1 = 1 (mod p). 
E.=! -1 
Assim, 1 = xoP-1 = (xo2 ) 2 = aT (mod p). Daí ordpa ~ P21 < p- 1 = <P(p) e então a não é 
raiz primitiva módulo p. O 
1. 7 Representação de inteiros como soma de quadrados 
Problemas resolvidos do Capítulo 7 
1. Dizer quais dentre os primos 11, 17, 19, 23, 29 e 31 possuem representação como soma de dois 
quadrados e fornecer a representação. 
Solução: Para encontrar os que são soma de dois quadrados, vamos procurar pelo resto da divisão 
por 4. Ou seja, 
11 = 3 (mod 4), 17 = 1 (mod 4), 19 = 3 (mod 4), 23 = 3 (mod 4), 29 = 1 (mod 4) e 31 - 3 
(mod 4). Logo, somente 17 e 19 são soma de dois quadrados e nesses casos 17 = 12 + 42 e 
29 = 22 +52. o 
2. Resolver, em inteiros, as seguintes equações, x2 + y2 = 146 e x2 + y2 = 625. 
Solução: (i) Como 146 = 2 · 73 e 73 = 1 (mod 4), então essa equação diofantina tem solução. 
Para resolvê-la, vamos supor x e y positivos, pois se (x, y) é solução então (±x, ± y) também o 
é. Note que a equação é simétrica, logo podemos supor x ~ y. Daí, 
e 
2x2 ~ x2 + y2 = 146 ~ 1 ~ x ~ .../72 < v'8i = 9. 
Logo, uma conta simples, mostra que a única solução no domínio acima é (x, y) - (5, 11). 
Portanto, todas as soluções são: 
(x,y) E {(5, 11), (11, 5), ( -5, 11), (11, - 5), (5, - 11), ( -11, 5), ( -5, - 11), ( -11,- 5)}. 
(ii) Usando o mesmo argumento do caso anterior, obtemos os limitantes. 
Ü ~ X ~ 17 1 ~ y ~ 25 
Logo (x,y) E {(7, 24), (15, 20), (0, 25)}. Daí todas as soluções são da forma: 
(7ei, 24e2), (15e3, 20e4) e (0, 25es) 
ondeei E {±1} para todo i. Também os pares com ordem trocada são soluções. 
o 
3. Dizer se existe um triângulo retângulo isósceles de lados inteiros. 
Solução: Suponha que existe, veja figura abaixo, 
Capítulo 1. Problemas resolvidos 47 
A 
B 
tal que A= B. Pelo Teorema de Pitágoras C2 = B 2 + B 2 = 2B2 => ~ = v'2. Absurdo pois ..j2 
é irracional. 
Obs: Note que a mesma prova acima implica na não existência de um triângulo retângulo isósceles 
com lados racionais. O 
4.

Outros materiais