391296166-Solucao-Abramo

Prévia do material em texto

I.
a
É
a
DIVãsÃ* Nüs ãtqrmïRüs
3.1 Divisibilidade
SoluçÃo.
a) Se b : 0, como blo., devemos ter o: 0, logo lol : g : lbl.
Suponhamosb 10, logo a+0, pois olb. Assim, da Proposição 3.6, temos que lol ( -: e
lbl ( lal, o que mostra que lal : lbl.
b) oclbc é equivaiente a bc : uoc para algum u e V.. Como c + 0, a igualdade anteú'lr É
equivalente a b : u6,o que equivale a olb.
3.2. A soma de todos os múltiplos positivos de 6
dois algarismos é:
(A) 612 (B) 64s (c) 756 (D) 810 (E) 864
que se escïevem (no sistema decimal) com
Soi-uçÃo.
Os múltiplos de 6 que se escrevem com dois algarismos no sistema decimal começam com I 2: 6-2
e terminam com 96 : 6 . 16. Logo estamos diante dos 15 primeiros termos de uma P.A. com
primeiro termo igual 12 e razã,o 6, cuja soma é
Srs : rt" t" : 8i 0.
A resposta é (D)
3.3. Com quantos zeros termina o número 1001?
SoluçÃo.
Cada zero à direita de 100! provém de um fator 2 e de um fator 5. Como há mais fatorEs 2 em.
n! do que fatores 5, basta contar o número de vezes que o número 5 aparece em I00!- \-amm à
contagem: De I até .l00 o número 5 vai aparecer como fator em
5:5.1, 10:5.2, 15:5.3, 20:5.4,, 25:5.5,..., .l00:5.20
^
^'A
42
Portanto, o fator 5 aparece 20 vezes,pais âS repedções que provêm dos fatores
5-5, 5-10. 5-15. 5'20'
que são em número de 4. Portanto, em '100! temos 24 fatores 5, logo ele termina com24 zelos'
g.4. a) N{ostre que o prgduto de i números naturais consecutivos é divísível po1 i1:
b) Mostre que 6ln(n + 1)(2n f 1), para todo n € N' ': ''
SoluçÃo.
a) Utilize o Lema 2.7.
b) Sefl: l, o resultado ê óbvio. Suponhamos Ír > 1,logo pelo item (a) temos que 6:31 divide
n(n*1)(2na1),pois
n(n* 1)(2n+ i) : (n- l)n(n+ 1)+n(n+ 1)(n+2)'
que é soma de duas parcelas, cada uma produto a: jl:: naturais'
uma outra solução obtém-se notandoq". ÚTtI é um número inteiro já que é igual
a 12 +22 +. ..+'rr2.
3.õ- \íostre, por in{11çã9 mg,tqmátical que, para todo n €
aì g;3h + 7 b) 9116" * 3.4n+z 1 5
di 9;n4*+1 
- {n f 1)4n,+:1 ' :,,,e}....16913h+3:-:' 26n:',27
N u {0},
cJ 2*132' 
- 
1
' 
..l
.:'::
' :,i,
SoruçÃo.
a) Para n:0 a asserção é verdadeira, pois 818. Suponha que 8132'+7 para algum n ç NUi0]'
Como 3h*2 a7 :9(32n +7) 
-B'7,lemos que 8132*+2 a7'
b) ParaÊ:0aasserçãoéverdadeira, pois 9154. Suponhaque, paraalgumrr € NU{0}, tenha-sé
9ll0* a3'4n+2 *5. Como
10.+r + 3 . 4n+3 * 5 : l0* + 3 . 4n+2+ 5 + g(,l0* + 4n+2),
temos que 9116n+1 a3' 4'+3 + 5.
c) Paran:0 a asserção é verdadeira, pois 112. Suponhaque 2nllz" -1, para algum rr € NU{O}'
Como
32**, _,1 :(32* _t)(32"+t)
Â.AA43
e (32" + .l ) é par, temos que 2*+1132'*ì 
- 
I .
d) Para n:0 a asserçãoéverdadeira, pois gl0. Suponha que, para algum n 
€ 
Nu{0}, tenha-se
9ln4n+t 
- 
(n* l)4* + .1. Como
(n* i )4n+z- (n+ 2)4n+t + I : 4(nQ"+t 
- 
(n+ l)4. + l) + 3(+.+t 
- 
lJ,
e 314"+t 
- 
Ì-, para todo n (que pode ser provado por indução), temos eue 9ln{n+lparatodon€N. -(n+l)4'+1.
e) Paran:0aasserçãoéverdadeira, pois 16910. Suponhaque, paraaigum n 
€ Nu{6}. tenËa-se
1 69132*+z 
- 
26n 
- 
27. Como
33n+6 
- 
26(n+1) 
-27 - 33n+3 -26n-27 +26q3zn+z 
- 
l),
temosque169l33n+6-26(nl1)-27,,pois13133n+3-l,paratodon€N,jáeue33n+:-l:2p=n-ì
e 26127-+1 
- 
1.
Note que o argumento acima utilizado mostra que 4 . l6g divid. 33n+3 
- 
26rr- 27, para tc,,ôail€NU{0}.
3.6. Mostfe que l3l2iQ + 3zo
Sor,uçÃo.
Note que 370 + 270 : g3s a 43s O resultado segue da Proposição J.g, já que 13 : g * 4.
,:r.li 
t,r.
Soi,uçÃo.
As Proposições 3.2,
a) 10-1110"-i;
d) 10 
-7110^ -7-;
3.8 e 3.9 fôrnecem-nos:
b) 9 
- 
.ll9* 
- 
1; c) 49 + 41492^ 
- 
4rn;
e) 9+ 4l|2n-4zn' f) 5+ 1152"+t + l2*+r;
h) l0 *7l\gzn+t +72"+1,g) 3+16l3zn+t ]-162n+1t
i) 9+Slgzr'+t a52n+1.
nãa 44
3.8. Sejam a.,b e V..
a) Se a I b, mostre que' païa todo n € N, n ) 2'
c*-b* : sn-l a a.-2b +...+ cb^-2 *b"-to-b
b) Se s * b + A, mostre que) para todo n € À['
O2n+1 152n+1 : ,,zn 
- 
&.n-1b + . ...- o62n-l a 62*.
...,t
_ o2n-1 _ o2n-26+ . . .+ o62n-2 62n-l ,
a*b
c) Se o * b + 0, mostre que Para todo n € N'
O2n 62n
o*b
Sor,uçÃo.
Essas identidades pïovam-se sem difi.culdade por indução sobre rr'
3.9.
r)
b)
c!
dï
Para quais valores de o € IS
c--21e3 + 4?
a*3loi-3?
s+Zlc-a +2?
s*2lo.ati'2o'+a2+l?
SouuçÃo.
*) óo-o s3 +4: 03- 8+12e o-2 divide c3-8, temos que o'-2 divide o3+4 se' e
somente se, o-2 divide 12, o que ocorre se, e Somente se, o € {1 ,3141516,8,14}'
b) Como o3-3: 03* 27 
-3l,temos que o*3 divide a3 -3 se, e somente se) o1L 3 divide 30'
o que ocorre se, e somente se' o e {2r3r7r12r27}'
c) como sa +2- ú 
-16+18, temos que 0*2 divide sa +2se, e somente se' o*2 divide 18'
o que ocorre se' e somente se, o € {1 ,4r7116}'
d) como oa +2o3 +ú+l : (oa -20)*2(o3 +23)+{s2-22)+5, temos que (I*2 divide
a4 +Zú + s2 +1 se, e somente se, o*2 divide 5, o que ocoffe se' e somente se' o:3'
45 ^àEã
3.10. N{ostre que, para todos e, m) n e V,,
m>n)0 -J 02'+llo.2''-.l.
Soi,uçÃo.
Note que s2 
-1 : (oz*;2m- 
- 
- 
I e utiÌize a Proposição 3.9.
3.11. N4ostre, para todo n 
€ 
N, que n2l(n + I )" 
- 
l.
("i ,)*'* (*i,)**,(ï)*-'+ +
: Í1n * (ï)*-'
SoluçÃo.
Pelo binômio de Newton,
(n+1)*:n'+
Portanto,
(n*l)'-l
que é divisível por n2.
+ + (_1 ,)*, *n,,
3.12. Mostre,
a) 2la2 - a; d) /lo, 
- 
o.
SoluçÃo.
a) Como o2 
- 
o.: o(o- l) é o pro.d.uto de dois-inteiros consecritivos, ele é divisível por 2.
b) Como c3 
- 
a: o(a- l)(o+ l) é o produto de três inteiros consecutivos, ele é divisível por
3!, logo divisÍvel por 3.
Sugestão para (c) e (d): Por indução sobre o, com a utilização do binômio de Newton.
para todo a 
€ 
Z, que
b) 3la3 
- 
o; c) 5los 
- 
a;
3.13. Mostre que existem infinitos valores de n em N para os quais
a) 8n2 +5 ê divisíve! por 7 e por 11.
b) 4n2 + 1 é divisível por 5 e por 13.
6D t'a 46
SoluçÃo.
a) O primeiro valor
rt:3 f r, logo
de n para o qral 8r-1--- 5 é riivisível por 7 e
8n2 + 5 : 8[3 +rjr 
- 
5 :77+r(6 + r).
Para que 8n2 + 5 seja múltiplo de 77, basta tomar r múItiplo de 77 '
'11 é n:3. Considererr:os
b)Asoluçãoéanáloga.
{}.)ò..4 Divisão Euclidiana
Sor,uçÃo.
a) q:5,r:2; b) q:5,r:3'
SolcçÃo.
Para dividir o por b nos inteiros com uma calculadora que trabalha com aigumas casas
decimais, procede-se como se segue. se o ( b, tem-se Q:0 e T: a' suponhamos que a'>b'
Primeiro passo: efetue a divisão o-;b e despreze a parte decimai apÓs a vírgula; o que se obtém
é o quociente q. Segundo passo: caicule bq. Terceilo passo: efetue a subtração o-bq' obtendo
o resto r.
No exemPlo numérico: Q : 198 e r : 11 526'
AÀA47
d) da potência de um número.
e) da soma de n números ímpares.
Sor,uçÃo.
a) e b) A soma e a diferença de dois números é par se, e somente se) os dois números possuem
a mesma paridade.
c) O produto de dois núrneros é par se) e somente se, pelo menos um deles é par.
cl) A potência de um número ê par Se, e Somente Se, esse número é par.
e) A soma de n números ímpares ê par se, e somente se, n é par'
Sor.uçÃo.
a) Peio problema anterior e indução mostra-se sem dificuldade que o é par se, e somente se,
a*êparparatodon€NI,bemcomooéímparse,esomentese,atéímparparatodon€NÍ-
b) Pelo item anterior, sabemos que o* e o* têm mesma paridade, logo dos itens (a) e (b) do
problema anterior segue-se que tanto a sua somâ quanto a sua diferença é par.
c) Temos que o. :2kf 1 para algum kçZ e b:2L+1para algum 1"eV'. Assim, a2+b2:
40e+12+k+L)+2,logo o2*b2 não é divisível por 4, pois, caso contrário,4 dividiria2, o que
é um absurdo.
3.LV . :,q.) Mostre'eue,xm.,núme1o'natural
ne1\.
b),Mostre que o*t'0* é semprePâr, quaisquer que sejaryr'nr'rn''€'${;-;"":."'' ''''r:' i" ' ' '
c) Mostre que, se o e b são Ímparàs, entãoa2 +b2 é divisível por 2 mas não divïsível por 4-
3.18. Quais são os números que, quando divididos por 5, deixam resto igual
a) à metade do quociente? b) ao quociente? 
,,; ., :: ,.:.: :
c)aodobrodoquociente?d)aotripiodoquociente?..
SoluçÃo.
Respostas:
a) 0, 1 1,22,33.,44;
c) 0,7,,14;
b) 0,6, 12,18,24;
d) 0,8.
rcã al 48
8.1g, Seja n um número natural. il{ostre qüe üm, e apenas um,'número de cada terno abaixo
é dlvisível por 3.
a) n,n *1rn1-2
c) n,n*-l0,n*23
b) r,fl+2rn*4
d)*,n*,l.,Zlu*1
SoluçÃo.
Um número n ê de uma das seguintes formas:
cada item a análise em cada caso.
n : 3k, n :3k* I ou n : 3kf 2. Faça em
3.20. Mostre que
a) se n é ímpar, então n2 
- 
1 ê múÌtiplo de 8;
b) se n não é múÌtïplo de 2 ou cle 3, então n2 
- 
1 é múltiplo de 24;
c) 4 [n? * 2, paia todo n e N.
Sor.uçÃo.
a) sendo nÍmpar, ele é daforma n:2kf 'l,logo"rt-l: (2k+1)2 -1 -4k(k+1) e
k{k+1)êpar.
b) Temos que rì"é deumadas seguintesformas: i) n:6k*1 ou ii) n:6k*5.
caso (i): n2 
-1 : (6k+ 1)2 - I - 3614 +12k: 12k(3k* 1). Como n é ímpar, 3k+ 1 é par,
loge 241n2 
- 
1.
Casoü): n2-1: (6k+5)2-1 
- 
Z6lê+60k:12k(3k*5). Comoné ímpar,3k+5 é par,
Irryto24lr,2 
-1.
c) Se n é ímpar, o resultado é óbvio. Se rr é par, então 'rt:/lç,Iogo n2 * 2 : 4k +2, que não é
divisÍvel por 4.
3.21. Quantos múltiplos de 7 existem entre
a) 123 e 2551? b) 343 e 2551?
Sor,uçÃo.
a) Resposta: 347. b) Resposta: 316.
A
^a49
g:,?ã.i.{ENÇ-!0.00}" I\{ostre que, se',üm'inteíro.ë, ,, smo telnpo, um crb.o'e.,ri ,qú
então ele é dá forma 5n, 5n * l, ou 5n * 4.
Sor,uçÃo.
Um número qualquer escreve-se numa das seguintes formas: 5k, 5k a 1, 5k + 2, 5k 
- 
3 ::
5k + 4. Elevando ao quadrado, vemos que um quadrado é de uma das seguintes form.as: 5;-*
5m*l ou 5m*4. Eievando ao cubo, vemos que um cubo é de umadas seguintesforma;: l-
5l+ l,5l+ 2,5L+ 3 ou 5lf 4.. Logo um número simuÌtaneamente um quadrado e um. cur": =
da forma 5n, 5n * I ou 5n* 4.
SoluçÃo.
a) Se a não é múltipio de 3, então é da forma 3k + I ou 3k + 2. Temos então que 02 :
3(3V +2k) 11 ou ú:3(3YJ +4k+ l)+ I, o que prova a afirmação.
b) Os números o2 são da forma o2 : 3k ou o2 : 3k * I e b2 : 3l ou b2 :31.* 1, logo sz +b2
só é clivisível por 3 se, e somente se, o2 :3k e b2 : 3L.
.3t?Í.r.(Ei\ç:2oqi) Seja N um número nq,tura!; p-rov.e que,:a divis,pO de
[esto.2,
Udd
rtJ
:J
rrl
UT
-d
EI
rrl
:J
11
IFdddI
çI
Ç
é
-€ (J
../
50
N2 oor 6 nunca deixa
'''::
SoluçÃo.
O número N é de uma das seguintes formas: N : 6k, N : 6k * I , N : 6k * 2, N : 6k + 3,
N :6kf 4 ou N:6k+5. Elevando ao quadrado, obtemos N2 :6(6*), N2: 6(6* *ZkJ*1.
N2 : 6(61C+4k)+4, N2 : 6$YJ+6k+l )+3, N2 : 6(6k2+8k+2)+4 ou N2 :6(61ê+l0k++.t--_'1.
o que prova o resultado.
3,25i 
-(EhlC=2002Ì''O,r.esto,,d.q, divipao,do.j.n!çiroNp 2Q Q Sr,Qual ç o rello, 'dil+sãs de N
por,5?
EãA
SoluçÃo.
Como N : 20q f B : 5(4q + l) + 
-?, a respcsta é 3'
3.26. 
,,&{ostJ-e,gue;!g,n é ímpa1, ,4Jãa a sotna de n termos con9ecutiu.9",,dÊ,,t-a PA,$g 4úm!To,.s.
inbeiros é sempre divisível por n.
SoluçÃo. n L
A soma dos termos consecutivos da PA é S : ttg=l#4. Como S é inteiro e n é ímpar'
temos que sm * o*+r,-t é par, logo S é múltiplo de n. '
3;ZT. Ache,o menor múltiplo de 5 que deiia restó,2 qúando dinidido p'or 3 e por 4.
SoluÇÃo.
Seja n o nitmero procurado. Temos que rr : 3q * 2:4'q'* 2, Iogo 3q
que 3 divide 4q':3q'+ q', Iogo 3lq'. Assim q'-_ 3k,logo n:12k*2'
5 dessa forma ocorre quando k: 4,1ogo n : 50-
: 4Q' , o que implica
O menor mírltiplo de
Problemas Suplemeïrtares
SoluçÃo.
a) A asserção é verdadeira païa ÍL :
6ln3 + l.ln. Como
l. Suponhamos que para algum rr € N[ tenharnos
: (n3 * 1'ln) * 3n(n + 1) + 12,,(n*1)'+t1(n+1)
temos que 6l(n+ l)3 +'11 (n* 1), pois 6ln3 * 1ln, 6l3n(n* l) e 6112.
51 làG
b) A asserção é verdadeira para rr: l. Suponhamos que pâïa algum n € N tenhamos 9i|4" +
l5n- l. Como
4n*1 1 15(nf l) 
- 
I : 4n *l5n 
- 
I + 3(4* + 5),
temos que gl4*+1 *]5(n+ 1)- 1, pois 914* + l5n- i e 314'*5 (que se prova por indução)-
c) A asserção ê verdadeira para rr : l. Suponhamos que para algum rr € N tenhamos 7l]2n-1 t
2'+2. Como
32n+3 a 2n+3 _ g(3zn+t +2"+\ _T .Zn*r,
temos claramente que 7132*+3 a /n+3 .
cl) A asserção é verdadeira para ïr: l. Suponhamos que para aÌgum n) 1 tenhamos Q2 - s=
1ls2'+i + (o 
- 
1)n+2. Como
o:LÍ'+3 + (o- 1)n+: 
- 
o2([7+t + (o- l)**t) + (a-1- ot)(o- 1)'*t,
temos claramente que a2 
- 
o * 1la2*+s * (a- I),'*3.
!
T
':
i
il
i
It
!
"* II
3.29. Mostre que, para todo número natural n.ímpar, tem-se que
24U112n a 192n'.
SoluçÃo.
Temos que i12n +19h :121^ +361*. Como n é ímpar, pela Proposição 3.8, temos que
482:121 +36] divide 121- +361n, o que prova o resultado já que 241 divide482'
3.30. Mostre que, se um inteiro é um quadrado e um cubo, então é da forma Zk ou 7k+1.
SoluçÃo.
Todo número inteiro é da forma 7rn*i para algum m,i. € N com 0 < i ( 6. Eler-ando ao
quadrado, vê-se que um quadrado só pode ser da forma 7k + ï com i : 0, I ,2,4. Eleland,: ao
cubo, vê-se que um cubo só pode ser da forma 7k+i com i : 0,.l,6. Juntando essas informações
obtemos o resultado.
6D 
^à
52
3.31. a) ÌV{ostre que o algarismo das unidades de um quadrado sô pode ser um dos sê'g-tljntes:'r'l ' .
0,1, 4,5, 6 ou 9.
b) i{ostre que nenhum clos números 22r?)),2?22,,.--, oü 33,333,3333,"' ou 77'777''7777'"''
ou ainda 88,888,8888, '.., pode ser um quadrado'
SoluçÃo.
a) Todo número inteiro G escreve-se na forma cr:
s2:10(j0k2 +zkL)+i2. O algarismo das unidades de
10k+i, com k,i e N e 0 < i < 9, iogo
o2 é, portanto, o resto d'a divisão de i2
por.10, que sÓ Pode ser Or1',4)5,6 ou 9'
b) Segue imediatamente de (a)'
quadrados 'é'da'forrna 4n * 3' :3.32. a) Mostre que nenhum quadrado ou sòma de dois '
lquência 'l.l 
' 
'l I 1' 
.ll I1', ' ' é um quadrado ou soma d3 foisb) N'Iostre que nenhum eleaento da se
quadrados
c)Idempq,ranenhumelemento.dasse$uintes'.oi^ï11':
44.,4M,4444, . . ., 55, 555, 5555, . ' ', 99 1999,9999 ',' ' ' "
SorcçÃo. Á.1- , .\ Áv J- 2
a'l Todo número inteiro cL é daforma a:4k, a- 4k*1, o :4k*2 ou o":4k*t'
Ëlerando ao quadrado cada uma dessas formas, obtemos t2 -- 4'(q1C) ' az 
: 4(4lC + 2k) + 1 
'
a::4iÁ.1d +4k+ 1) ou a2 :4141c+6k+ 2)+1. Logo todo quadrado é da forma 4k ou 4'k+1,
e portanto â soma de dois quadrados sÓ pode ser da forma 4k,4k* I ou 4k+2' 
:
b) Basta observar que todo número da forma dada escreve-se como
l00n t- 11 : 4(25n+ 2) + 3.
c) Note que
logo se 44"' ot 99 "'
ocorrer por (b).
Por outro lado,
M"':4'11 "'
fosse um quadrado,
99...--9.11
número -l1 " '
)
tambóm seria, o que não Poiie
55 "'
logo não pode ser um quadrado'
: l00n * 55 : 4(25n+ 13) + 3,
53 ÀG
3.33. a) Mostre que nenhum número da fofma 4n4-2 é um quadrado
b) Mostre q,ru o"rrh,rm dos números 66,66;6,6666,... é um quadrado.
Sor,uçÃo.
a) Isso foi provado no Problema 3.32(a).
b) Note que 66...- 100k+ 66:4(25k+16)+2.
SoluçÃo.
a) A soma dos quadrados de dois números ímpares, pelo Problema 3.17(c), é par mas não
divisível por 4. Por outro lado, um quadrado par tem que ser divisível por 4.
b) Isso foi feito no Problema 2.9. Refaçamos a conta. Todo número inteiro o é da forma
51,51+1,,51"+2,5i+3 ou 5t+4. Elevando ao quadrado, temos s2:5(5L2), s2:5(512+21)+I,
ú:5(5L2+41"+l)-.l, e2:5(512+ 6L+2)-l ou s2:5(5L2+Bl+3) +l,logo o2 êd,aforma
5kou5k+-l.
c) Pelo item (a) o número b ou c tem que ser pâr. Se b e c não são múltiplos de 5, então
b2 : 5l* I e cz :5k* 1, logo oz :b2 + c2 êda forma 5m, 5m*2. Por (b) ot só pode ser da
forma 5m, logo o é múltiplo de 5.
.3;35. ,.Mostfe'qúè,,de.n',,iíteiros,:eirlrgêc rô.sitiiirr,rie;ápeAráS:úm;.,Agles;,ê t4ivisível por ïr.
SoluçÃo.
Considere os
ie{0,1,...,i1-
inteiros o,o*1,o*2r...ra*n-l eescreva o na forma o:nk*i. can
1]. Apenas o número a *n 
- 
i é divisível por n.
EãA 54
3.36. Um número é clito liure de qu.*.{roi,1-: se não for d.ivisível pelo quadrado.de 
nenhum
número diferente de 1.
"iOar-r*ine 
qual ê o maior número de núneros naturais consecutivos livres 
de q'adrados'
b) Defina números livres de cubos e resotrra o problema correspondente'
Soluç.l.o.
a) Do Problema 3.35 temos que, de quatro números naturais consecutivos) 
um deles ê divisíveì
por4,iogoamaiorquantidad"edeintebosconsecutivoslivresdequadraclosê3.Essenúmeroê
atingido, como mostra a sequência 1, 2' 3'
b) como de oito números consecutivos, um deles é múltiplo de 8, que é um 
cubo, deduz-se que o
maior número de inteiros consecutivos liwes de cubos é 7' Esse 
número é atingido' como mostra
a sequência 1, 2, 3, 4', 5, 6, 7'
0d'o* d'o +zd"o* 3d'"'' onde o'd € N' se há um3.37. lVlostre que na sequência o -J
bermo quadrado, então há infinitos termos quadraclos'
SoluçÃo.
suponha que exista um número natural s tai que of sd -bz,definindo ri: s +2íb +td'
temos, para todo i € N, que
o+ (s +2íb+t2d) d: s* sd* zíbd'+i2&
bz +Ztbd+í2&: (b + id)z.
o*rtd
rk-7
g;g8- rSe,k >'2'e-;.o'ë,.ímpai;,15163.11e,qüe 2k divide oz- 
-:,,1:
Sugestão. Por indúção sobre k '
SoluçÃo.
Para k: 3 e s:Zrrv* 1 ímPar temos que
(2m+1)'_ 1 :4n] +4m* 1
que é multipio d.e 8, já que m(m * 1) é par'
-1-4m(m*i)'
55
ÀAA
Suponha que 2k divide c'}*-t - 1' Note que
or*-, 
--t : (otn )t - r : (szk-z - 11(a2o-'+ i).
indução temos que 2k divide ú2o'2 -1 e 2 divid" (ú"'+ 1)' jâ que o éComo por hiPÓtese de
ímpar, temos que 2k+1 diúde o2"-' -.1.
Ì
i
Í
!
t
t
+
il
I
ii
{IIi
!
1
t
a
=
56
Problemas ProPostos
1. Generalize o resultado do Problema 3'4(a), mostrando que o 
produto de inirmeros inteirre
(não necessariamente naturais) é divisívei por i!'
2. Sejam ï1r m € N, com n2 2' Mostre que
(lr,- ])tl"*-- l e rr- 11m"
3. ÌViostre que para todo o € N tem-se que
(o*-l)21o"("'-t)-i.
4. Para quais valores de n € N tem-se que
a)n*l divide r:f+1? b)n*l dividena+l?
5. Determine os valores de n € N tais que
a)n-llnifi; b)*-.lln5+1; c)Generalize'
6. sejam OemnúmerosnaturaiscomrTÌímpare opal' Mostreque o* 
j divide 1m12m*
...* o*. Em particular, concluâ' que m divide l*+2*+ "'+ (m- 1)*' o
sugestão. Agrupe as parcelas da última soma âos pares: i* + 
(a 
- 
i + i )*' i - .1) " ''1 1'
7. Mostre que nenhum número da forma T + 1é potência de expoente 
ímpar de um número
inteiro.
8. Mostre que
a) a soma de quatro inteiros consecutivos nunca é um quadrado;
b) a soma dos quadrados de quatro inteiros consecutivos nunca ê um 
quadrado. Mostre o m6mo
para a soma dos quadrad'os de três inteiros consecutivos'
9. Mostre que
a) todo quadrado é da forma 8n' 8n * 1 ou 8n * 4;
c) Generaiize.
L_
ED t^
b) nenhum número na sequência 3, 1l' l9r 27, - -., é um quadrado'
10. Seja r" um inteiro ímpar. Mostre que o resto da divisão por 12 de
n2 + (n +2)z * (n+ 4)2
é igual a .l1. E se n fosse Par?
Sugestão. Escreva n na forma 6k * i, onde 0 < i < 6'
11.. Mostre que não existe nenhum n natural tal que 7 divide 4rJ -3'
L2. (PROF\4AT 2011) Sejam a e b números naturais'
a) Determine os possíveis restos da divisão de a'3 pot 7 '
b) Mostre que se s3 + 2b3 for divisível por 7, então o e b serão divisíveis por 7'
13. a) Mostre que se 7lú +b2, onde s e b são números inteiros, então 7ls'e7lb'
b) Resolva a equação diofantina ,J + Ut : 637 '
L4. (PROFMAT 2011) Sejam p e q dois números naturais, com 1
a) Mostre que existem números naturais ïh, pt e Qt, com Pt 1P,4t
PlPt
Q ïrr 'q,'
b) }[ostre que existem números naturais ï €ït1 ]"íI2] "'>n' tais que
P:1+l+...+ l.
Ç nr T1u2 Ílr
t5- I[ctrequese n>2éuminteiro, entãoasoma i+i+"'+* nuncaéumnúmerointeiro'
$ugestão. seja m o maior inteiro ta1 que 2* < n. separando na soma a parcela fi, a soma
das parcelas restantes é da forma 6ft, ond.e a e b são números naturais ímpares, e k um inteiro
menor do que m, podendo ser negativo. Assim, â nossa soma é igual u ffid, que não é inteiro,
pois o numerador é ímpar e o denominador par.
<P<Qe(P'Qi:l'
< q e (Pr, qr) : l, tais que
57 AG
RHtrRmsml{TAÇA* ffits
ï{ {J i\iltrffi,ü g ãru TEãfi,*Ë
r
4.1 Sistemas de Numeração
SoluçÃo.
Seja abc o número representado
problema conduzem-nos às seguintes
Da primeira relação, obtemos
na base '10, ou seja, obc:.l00q.+ lOb_Fc. Os dadcs do
relações:
ccb: s.bc*36
bo.c: sbc-270.
l00a* lOb + c *36: l00s* lOc +b __ì b +4 : c"
Da segunda relação, obtemos
l00b + l0o* c : .1000.+.l0b * c _ 270 _ìb : a_3.
Dessas duas últimas relações, obtemos c _ o : 1. portanto,
cbo- c.bc: ggc-g?a:99(c_ s):gg.
]:2,'--'critu,lt:,o" llvisiuinaade por uma potência de 2 seja dado um número natural,,... I r. , : -: - vvJa uouv urrÌ uulllel-u natruïal
ï.1Ïïïll-11"^ 11-l"se l0 o:' ": Gnon*r ' " o6' usando o rato ã" qu. 2kltok, *"'ì'. *. r.lt 'o 'è, . 1o*.nte se, ó nírr,€ro o1ç_1 . .. o, oo ã ãirrirttàip;;i;,.iã-;;r;;;,'ïïilïr":;...:, :, I i :. .: .. - .. *t ïu v uryrÈry(;l pu+ z . .DIrÌ partlcu
\?r,r,se, 
e somente se, a6 é 0, 2, 4, 6 ou g; também, o e divisivel o"O o ;;;divisível por 4. somente se, oi a6 é
Sor,uçÃo.
Escrevamos o: (or,"'op)10k*ot-r...o6. o resultado segue do fato de (a,r...a1)10kserdivisÍvei por 2k.
606D 
^
4.g. Escolha um número abc d,e três algarismos no sistema decimal, de modo que os:àlgârisgrqs
das centenas o e o das unidades c difiram de, pelo menos, duas unidades cons]9"t.t,3t,"11tt*
obc e rúo. subtraia o menor do maior, obtendo o número xyz. A sonra de xgz coú z"yx'uaIe
1.089. Justifique esse fato.
Sor,uçÃo.
seja dado o número obc representado na base 10, com lo.- cl )-2- seia
KUz: labc 
- 
cbol : 99ls 
- 
cl'
Como la- cl e {2r3r4.,5,617 r8r9}, calculando os possíveis valores de xgz:991s- cl' ver'nos que
KAz: x9$, com a* Í3 :9, logo x*z:9 e\J:9' Daí,
xAz+zyx: (x+z) '-l00 + 2A'10 *x* z:900 + lB0 +9 :108?'
4.4, Seja dado o número 4.783 na base 10; escreva-o nâs seguintes bases: 2,7,12 e 15'
SoruçÃo.
\abase2: 100-l0'10101.11i. Nabase 7: 16642. Nabase l2: 2927. Nabase l5: 153õ, onde
6: 13-
{5- o número 34-|6 está na base 7; escreva-o nas bases 5 e12.
Sor,uçÃo.
Onúmero,nabase.l0é3.73+4.72+7+6:1.238. Essenúmeronabase5escreve-se 14423
e na base '12 escreve-se 872.
4.6. Um número nà base l0 êscreve-se 37; em que base escrever-se-á 52?
SoluçÃo.
Supondo que a base procurada seja b, temos que 5b *2:37' logo b:7'
61 ÀG
4.7. considere v3 na base l0; em q'e base ele escrever-se-â,2437
SoluçÃo.
supondo que â base procurada seja b, temos qlue 2b2 + 4b + 3 :73,1ogo b : 5.
4.8. Escreva a tabuada na base 5; Use-a para calcuÌar 113215 a [4l3ls e [23]s x [342)s.
Sor,uçÃo.
Tabuada na base 5
0
1
I
2
3
4
00 0 0 0
012 3 4
024il.13
03il1422
04132231
342
231
+4
X32
13
1100
2't 31
1234
20021
4,9.', Utilizq,,o,.mêtodo,do'.Fxêúp1q,-4.9.páia,calcular..5.1f,,,'4.J,;;,:.,;.,
SoluçÃo.
72 527
36 1054
18 2108
9 4216
4 8432
2 16864
1 33728
62
I
I
tL-
A.AÂ
Portanto,
7 2 x 527 
-- 
4?1 6 + 337?3 : 379 44.
4.10. Escreva; :
a) O,número 2*' .l na base'2' b'- 
l
b) O número # na base b."/ " -'"'-"-- b-1
SoluçÃo.
a) Temosque 2*-l 
- 
T-1 +2n-2+...+2f l. Logo, essenúmero nabase 2 escreve-se
1l ...i (n dígitos iguais a 1).
b) Temos o..r. ffi -b,,-l *bn-zf ",*b+1. Logo, esse número nabase b escreve-se 
ll "'l
(n dígitos iguais a 1).
Mostre que o nú4r19;o
:
l . :: rr ::i;:r::l
SoruçÃo.
Temos que
o- (oo + "' + c,') : o',(b* 
- 
1J + "' * ot(b 
- 
1)'
qre é claramente divisível por b 
- 
1 (Proposição 3'7)'
4.2 de F{im
63 ÀG
SoluçÃo.
") Segura:
Grupo 1
Grupo 2
Grupo 3
b) Insegura:
Grupo 1
Grupo 2
Grupo 3
010
010000
011
010
010
020 031
c) Insegura:
Grupo 1
Grupo 2
Grupo 3
d) Segura:
Grupo 1
Grupo 2
Grupo 3
010
001
001
001
001
000
0L2
.4,,.,1ê ;,,,, D g.!g1mip.e qual d as 1 e gu i1! es .!ituaç-.õ 9s, i.nici ais, n o
loguàot traçar uma estratégia vencedora.
a) (12, 14, l5), b) {7,9,14), ,(7,9,15,17).
Em tal caso,faça uma jogada que lhe çeiá favorável. l
jogo de Nim
a. ,:.
:r1;1,:lii,:',,.. ;..,.
P9rtritç ao pnmelro
SoluçÃo.
a) Situação favorável:
Grupo 1 1100
Grupo 2 1110
Grupo 3 1111
3321
Jogada a ser feita: retirar 13 palitos do Grupo 3, obtendo a configuração segura
Grupo 1
Grupo 2
Grupo 3
1100
1110
0010
trDA 64
2220
--
t
t
,!
)
)
)
)
)
)
)
)
)
t
)l
c) Situação favorávei:
Grupo 1 0111
Grupo 2 1001
Grupo 3 1110
2222
Grupo 1 00111
Grupo 2 01001
Grupo 3 01111
Grupo 4 10001
Jogada a ser feita: retirar 16 palitos do GruPo 4,
Grupo 1
Grupo 2
Grupo 3
Grupo 4
72224
obtendo a configuração segura
00111
01001
01111
00001
t:
IIfipip:tr
l-
Problemas Propostos
1- \fmtre que o quadrado de um número natural na base '10 só pode ter como algarismo da
umi*tade um dos algarismos 0,1t4r5)6,9.
2- \[ostre que a quarta potência de um número natural na base 10 só pode ter como algarismo
da unidade um dos algarismos 0, -l,5,6.
3. Mostre que todo número inteiro pode ser escrito de modo único na forma
oo + a.i3 * a232 + "'+ o',3*,
para alguns fl € Gs,GIr...,o,,.,, inteiros, onde rt)-0, oi:0r+i, ì':0,.lr"'rn e ont'0'
4. Mostre que, com ,r*u bulunça de dois pratos e pesos de 1,3, 9.,27 e 81 gramas, pode-se pesar
qualquer objeto, com um peso inteiro de gramas, de 'l atê 121 gÏamas.
b) Situação desfavorável:
65 AEã
o.
7,
Efetue a soma e o produto dos números ú'3411s e [3]21s, sem sair da base 5'
Efetue a soma e o produto dos números 1101-l00112 e [1001]2, sem sair da base 2.
Mostre que todo número natural o escreve-Se de modo írnico na forma
o. : o11t + s22t + "' + c,rnl * "' 1
onde para todo i, tem-se 0 { ai { i e a soma é fi.nita'
Essa escrita permite defi.nir a representação fatori,al de um número natural ô como s:u:r
("', or,, on*lr"',ot)l : otll+"'* o"-t(n- l)l+ a'nl +"' '
Por exemplo,
(3,4,2,1,l)r :1l+2 +2'3t +4'4! +3'5! :461.
Sugestão. Para mostrar a possibilidade dessa escrita, utilize a identidad. ILt i' i! : .n -
1 )i 
- 
'l 
, que pode ser {aciimente verificada por indução'
66AAÁ.
Ag,GGRãTh/l*
trLJüLïnms
*H
5,1 Máximo Divisor Comum
SoluçÃo.
a) (3.887, 637) : 13 : l0 . 3.887 
- 
61 . 637 .
b) (1.21 8,,648): 6 : _25 .1.218 + 47 . 648.
c) (874,551) : 19 :12-875 
- 
19 -551.
d) (8.485, 7.325) : 5 : 
-562. 8.485+ 651 . 7.325.
á.2. Seja n 
€ 
N. Mostre que
a) (n,2nl_1) : l;
b) (tr*1,n2*n*l):l;
c) (2n f i,9n t 4) : '1'
d) (n! *1,(n+1)l+lj:1.
Sor,uçÃo.
a) (n,2n*1) :(n,l):'|.
b) (tr +1,rÉ*n*'l) : (n+ l, 1) : l.
c) (2n*1,9n+4): (2n* 1,n) :'1.
d) (n! * 1, (n+ l)!+ 1) : (n! + l,-(n+'l)+ 1) : (1,n) :1.
5.3. iVlostre que [o, t2 +"ns. + bJlb, quaisquer que seìam o, b, n € N.
SoluçÃo.
Note que (o,,ot *na+b) : (o,b) e que (a,b)lb.
6D ^à 68
5.4. Sejadado se Z\{-1}
a) Se rn € N, mostre que
b) Se m € NU{0}, mostre que
(#,"+r) :ia* 1,2m).
(qï+t, o* 1) : ,"+ r,2m+ 1l
SoluçÃo.
a) Para m: l, temos que
(t=, o +ì : \cr 
-1, o Ì\) : \-+,, o.Ì\\ : \u\\,4,\o+l'*' ')
mcstrando a validade da propriedade nesse caso.
Suponhamos rn 2 .1, então
o'* 
-l : &*-1 
- 
ú*-z * g.21rl-r-... * a- l
o+ I u
: (s2*-t +t)- (s.2m-z 
-l)+...+(s+l)-(1 -l)+Zm.
Como s*'1 divide as parcelu, o2m-l +1,, s2*-2 
-.l,..., s*1 e (1 -1), temos que(t r \
\ a+t 'C-+1):(c*1'2rn)'
b) Para m : 0 o resultado é óbvio. Suponhamos ïr ) i, então
O2m+t a 1 : o2*_g,zÍL-l *..._a*ls* I
: (ú* 
-1) - 1oz*-t +i) +...- (o* l) + (t -1) + (2m+1).
Como q*l divide as parcelas 02* - 1, s2*-1f 1,..-, otl e I -1, temos que
/ o?rft+1 +1 _\("-+' o * 1) : t"+ 1'2m+ 1)'
69 âre
5.5. CaÌcule
^,, (3oo_ 1 r5 ,'a; Irs .,,s--r);\J"- t /
^, (240 +1 ..,a ,\.) [ffi,2'+1);
o)(t/,')'
.,(##,2'o+r)
SoluçÃo.
a) Pondo 35 : o, peio Exemplo 5.3, temos que
(#+'35 - r) : (gi1' a- 1) : 
'"- 
r'B) : (242'8):2'
b) Pondo 5 : o, pelo problema anterior item (a), temos que
(?'6) : (#'"*t) :(o*r'ro) :(6'10):2'
c) Pondo 28: e, pelo problema anterior item (b), temos que
(2oo
\7#'2s +1) : (;}1'o+r) : (a*r'5) : (2s+1'5) :r'
d) Pondo 210 : a, pelo problema anterior item (b), temos que
(7#'210+1) :(#'"*t) :(orr'5) : (2'o+1,5) :i'
5.6. Sejam o e rr números naturais com c I 1. Mostre que
(o- 1)2lo'- I (+ c-'r'1t4''
SoluçÃo.
Note que (o-1)2le*-1 se, e somente se, G-ll*+,oque é equivalente a
(on-l ,\( 
"-i' "-'): o- l'
Isso por sua vez, pelo Exemplo 5.3, é equivaiente a (o 
- 
l, n) : o 
- 
1 , daÍ o resultado-
EDA 70
5.2 Propriedades do mdc
6.7. sejam o,b, d e z com ó.> 0.lv{ostre que se lio,bl - dv', então 4 : (4, b).
SoluçÃo.
Como o,b € I(o,b) 
- 
dZ, temos que dlo e
d : mo * nb, para alguns m) lt € Z, temos que cld'
dlb. Por outro 1ado, se clc e clb, como
Como d> 0, segue-se que d : (o, b)'
d):(o.b).=-[a'd)ç;bJ;,..[c,.,+").:.i].,i#9#g,ççn'!icra)
") ,. (o,b):1,=o*ão firutoao, n,m € NU{0} bem-se 
que (4",b*) :'1.
Sor,uçÃo.
a) Das condições alc e blc temos que existem r,s € Ztais que c:Ïo e c: sb' Do fato de
ic"b): l, sabemos que existem m,n € Ztais que mo*nb: l' Multiplicando essarelação
pff c. obtemos
c:smo*cnb:ob(ms*nr),
o que mostra que oblc.
b) Seja d.: (c,b). Logo, dlc e dlb e, portanto, dlac e dlb. Falta mostrâÏ que d é divisível por
todo divisor comum de oc e b.
Seja e um divisol comum de ac e b. Como (e, o)la e (e, a)le e e divide b, temos que
(e,o)l(o,b); logoemsendo (o,b) : l, temos que (e,o) :'1. Como eloce (e,o) : l, temos que
elc. Portanto, elc e elb e, consequentemente, eld'
c) Temos que (oc,b) :1 implica que existem mrn € Ztaïs que moc*nb:'l,1ogo (mc)a*
nb:.1 e (mo)c*nb: l, o que implica que (o,b) : (c,b) :1'
Reciprocamente, se (o,b) : (c,b) : l, do item (b), segue-se que (oc,b) : (c,b) : l.
d) Se (o,b) : (o,d) : (c,b) : (c,d) :1, do item (b) temos que (oc,bd): (ac,d) : (c,dl:
1.
Reciprocamente, se (oc'bd): ], do item (c) temos que (oc,b) : ] e (oc'd] :1. \ola-
mente, pelo item (c) obtemos que (o,b) : l, (c'b):1, (o,d) : I e (c,d) :1'
77 AG
e) Tomando c: Ír em (b), obtemos (o2,b) : (a,b). Aí procede-se por indução pâra mostrar*..jï;jl;l j:::f,:ll" r"r"trarlo apenas provado permire concluir que (a.,b*) : l.que lu -) C"'J : l.outraprovapara(e):comoaebsãocoprimos,existeminteirosrestaisqueïo*sb-1.
Elevando â 
'. 
+ m ambos os membros dessa úrtima igualdade, temos que
1 
- 
(tc+sb)n+m
: rn*mon+m + . ..+ ("ï*)r^o's*b*
+(ï1ï)t'-l on-trm*r6m+i 4 . . . * sn*mbn+m
: on frn+mo'+ ...+ ("1*)r.r".O*)l
+b' l(ïlï)rn-Ì on-lsm+rb + . . . + r*+*b,],
o que, em vista da Proposição b.10, prova que (a^,b*) : l.
5.9. Para toclos o, b 
€ Z e toclo n 
€ 
N, mostre que
(o', b") : (o, b)"
lt
í
i
t
ii-
Sor,uçÃo.
De fato, seja d. : (a, b), logo
anterior, item (b), que
o: ord e b: brd, com (o.1,br) : l. Temos, do problema
(a*,b*) : (d'of, d^Uï) : dn{oï,bï) : d,: (a,b),.
5.10. a) Mostre que, se
b) Mostre que 24 divide
n é ímpar, então n(n2 _ 1J é divisír,.el por 24.
n(n2- l)(3n*2) para todo n e N. rv- -r'
SoruçÃo.
a) Seja n:2m1- 1. Logo,
1): (2m+ t)t(2m+ t)2 _ tl
NDA
n(n2 
-
72
: (2m + 1)(2m + 2)2m.
Por outro lado,24:4! divide 2tn(2r*+1)[2rn+2][2m+3)' Daísegue-se que 8l2tn(2m+1)(2m+
Z), já,que (8, 211-*3) : l, pois 2r*i3 é ímpar- Por outro lado, 3 divide 2'n"(2tn+1)(2n+2),
logo como (8,3) : i, pelo Problema 5.8(a), temos que 24l2rw(2m+1)(2rn+2)'
b) Se n é ímpar, o resultado segue do item (a). Suponhamos n par' logo n :Zrv para algum
m. Portanto,
n(n2 
- 
l)(3n +2):2rn(2tn- 1)(2m+ l)(6m+2): Ztn(Ztn 
- 
1)(2m+ 1 ) (2m + 2) + 2rn{2rn- 1 ) (2m *',i )4m"
Têmos qÌle24:4! divide 2rn(2tT"-1)(2m+l )(2rt+2) (produto de quatro inteiros consecutivos)
e que 5:3t divide 21Tr(Zfi-- 1)(2m+ 1) (produto de três inteiros consecutivos). Assim, 24
diride ;'n(Z".,-- l)(2m* 1)4m. Portanto, 24 divide n(n2 - 1)(3n+2)'
5-11. a) Mostre que
b) Mostre que n' e n
n5 
--n é divisÍvel Por 30.
possuem o mesmo aÌgarismo das unidades'
SoluçÃo.
a) Temos que
r15 
-r, : n(na - l) : n(n - 1 )(n + l)(n2 + l)'
Lcgo. 6:31. divide n5 
-n. Por outro iado, pelo Problema 3.12(c), temos que 5lns -ft ê,
portãrto, pelo Problema 5'8(a), temos que 30 : 6 '5 divide n5 - n'
b) Como 301n5 
- 
n, temos que 10lns 
- 
rI' o que implica que n5 e rt possuem mesmo algarismo
das ünidades.
. .: l:. r',..:..r:.r1. lì.: .- , .,,, I G I
5.L2.' Mostre que se b e c não são ambos nulos, então olbc se, e somente se, G:Jlc'
Sor,uçÃo.
A condição albc implica que
Como, pelo Corolário 5.9, temos que
ob
-l-r-
(o, b) ' (o, b)-'
( o b \-[col'("J),) : t'
t-7 4/J AG
segue-se que
o-
io,bì lt'
5.13., Seja- o e b,deis números inteiros com (o,b) = 1.
a) N{ostre que (b * o,b 
- 
c) é I ou 2.
b) Mostre que (o * b, o2 + b2) é 1 ou 2.
Sor,uçÃo.
a) Como (b,b 
- 
o) : (o,b) :1, segue-se do Probiema 5'8(b) que
(a*b,b 
- 
o) : (2b,,b 
- 
a) : (2,b 
- 
s),
que é igual a I se b 
- 
a. ê.ímpar e igual a 2 se b 
- 
o é par.
b) Temos que
(o -t b, ú +v21: (o * b,b' 
- 
ob) : (a .]- b,b 
- 
o),
cujo valor foi caicuiado no item (a).
5.L4. Mostre que, se o, b, x, A e Z, com ox * bg 
-.- 
(a, b), então ,(x,g) -- 1 .
I
SoluçÃo.
A condição ox*bU: (o'b)
(x,g) : l.
implica que Ghx* f6u : i, logo, pela Proposição 5.10,
SoluçÃo.
Pelo Corolário 5.9 sabemos q.rr. 
.}, . # são coprimos, logo se o primeiro for Ptr, o
segundo é necessariamente ímpar.
Ciaramente, não vale a recíproca, pois 3 é coprimo com 5 e ambos são ímpares.
74EãÂ
Ë,16. um prédio possui duas esca{arias, uma delas com 7S0 ]es;aus 
e 
1oul.râ'com'700''4ê-$faus
r:r.:-:f: J -, .. .t, ir
Sabendo que os degraus das duas escadas so estao no mesl
:^
'descubra quantos andares tem o prédio'
SoluçÃo.
Sejammenosnúmerosdedegrausemumandardaprlmeiraedasegundaescada'respecti-
vamente. Pelo fato de os degraus das duas escadas só estarem no 
mesmo nível quando conduzem
aumandar,segue-seque(m'n):l'Sexéonúmerodeandaresdoprédio'temosquexm:780
3 ïÍL : 700. logo, 7O0m - 780n' o que implica que 35m :39rt" como (*' *) : (35' 39) :1'
p*dio tem x:20 andares'
o-tï- Calcule (1 116,984,-855)'
SoruçÃo.
Temos que
(1 116,984,855) : ((1 1 16,984)',855) : (.l2' 855) : 3'
Sor,uçÃo.
Sejam dados
Exemplo de
c,b e c com o e b coprimos' Temos que (o'btc) : ((o'b)'c): ['l'c): i'
três números coprimos que não são dois a dois coprimos: 5 ' 2, 2'3 '7 e 5 '7 '
75 AG
SoluçÃo.
a) Se B c A, então o mdc de À divide todos os elementos de B, logo divide o mdc ce B- u
que prova a desiguaÌdade.
b)Sejamd-l:mdc{o]l...,oi},i:1,2....Peloitem(a)temosqued12dz)...>
nos dá uma sequência decrescente de números inteiros não negativos; logo, pelo Princípio da P"-,4
Ordenação, existe n tal que d,' : dn+l : '" . Portanto,
d', : mdc{o1r..., Gr,}: mclcA.
5.20. N4ostre que
(cr, oz,...r Gn-t, orr) : ((ar, az,...r on-l), o.).
SoluçÃo.
A prova é muito semeihante à da Proposição 5.13.
5.3 Algoritmo de Euclldes Estendido
5.2L. Refaça os cálculos para o e b dados no Problema 5.1, utilizanclo o algoritmo dessa seção.
Sor,uçÃo.
É só fazer as contas.
ü(;
J'JJJ
Ç
;
J
!
a
;
I
ü
t
tt
ìttI
u z,', 
,sgJam
or i oz, , , , , on números inteiros,,não todos, nul,qç:
i:li::'lr': i ì-.i r::riìi
': ì .:: 1 : ' , . :
,I(gt, gz, , , r,, Êo) :.{xr ar *.{zoz * i,],,:, * xrropi
Cpnsid eré 
.o..c Q4j unto
a) IVlostre que
l
b) .Seja d : min (I(or, .. . , o,") n N.
.:'rr_!ì::Ì:i:.:l:ii.lrì".tl,:Ì:tr._.:t..irìr:í:t:,r'tr,r:i::{i:::,,ì;,:::.airt::r.:,i:';. ;i_t,l
À
^À 76
c) Mostre que (o1 ,Q2r.' ', o',-.) : d'
d) Ì\4ostre Que oiro2,...)Gn são coprimos se. e somente se) existem inteiros xltx2'"'Ìx"
tais que xror f x2c4 Ì.''' *x',.o,, : l'
SoluçÃo.
É uma generalização sem dificuldade'
tais que
5-23. Generálize:o algoritmo dessa seção para acìar inteiros x: txzt "'tx''
_ I ., .:, ) a :.
o-ì 
= 
xrç':','+ xìc,zir- "i:r,+ xrror.i ' 'I Ut! s/ì...l9TLJ .-t:-.1. i: -. ,ì..- ," '['*t' o2; 
"' 
,,'1 o") = xt 4ftÍt.'x2a2 
" 
'' 
' 
', 
,
srrÈe"rão. Cóària"1e.a matriz A quja priúe;a@â,,9 lorláaa,OOr iì,oz' ' ' ' ':G"':seg$da 
da
matriz identidacre n >_< n. : Efe.tu.ar -aneraeQçi sobre as ltin"ï de.Ãrsôm,9,n49 ï.:"ur 
linhll mril.illos
ae ootiàs tilár,,;ie our* 
"à n'*e,1í t9tÏi--::1"; os elembntôs ìiúlos' :":*to 
um deles' Supo
nha que a iinha orrd"l'urtâ.rrê'átà*ento não nulo 'da Plimeira coluna seja (d' xr' x2' "' 'x")-
N{osbre que
-rytt)
SoluçÃo.
a) Se ai f 0, temos que lcriï : toi e l(oi'tzt"''4") nN'
b) como d e l[ar,..., o*), temos que d :x1o1+." + x-,'o'n.se g € z, temos que
gd: Hxtc.t+ "'+UX'o* e i(41' "'' o.-,)'
Assim, mostramos que dV'C l(ort "'t G'.)'
Sejax€I(o1,...'o,,).Peloalgoritmodadivisão,temosquex_dq{rparaalgumqeZ
ealgum r€V,,com0 (r< d. Portanto, r:x-dq € l(o1,"',o")'logor:0'pois'
caso contrário, r € I(o1 t Q2.t . .. , 4,,) íì N e r ( d, contradizendo a minimalidade de d' Assim'
mostramos que x- dq € dV'e, portanto, I(sr tc;z't"''o") C dV''
c) Temos de (b) Que oi e dv",logo d|oi para todo i : 1, . . . )í1. Por outro lado, se c|oi 
para toclo
i, temos que c divide x1o1 * "'*xrror,: d, logo d: (or' "''o')'
d) Se o11...,o,Ì' são coprimos, então i : d : X1a1+...+Xno,.. Por outro lado' se existi-
rêrtr xlr...rxrr € V" taïs Que xior * "'*x"on : l' então min(I(o1'"''o") nN) : 1' logo
i.arr 
-.., ar.) : 'l '
77
,AÀA
5.4 Mínimo Múltiplo Comum
5Q4. caÌcuÌe o Ínmc dos pares de números do problema 5.1.
SolucÃo.
. ,. ^-- ---" 3887'637a) [sasz, 637]: i9ffi :190463.
b) [648, 1218J :1I+g! : 131544.
c) Isst ,s741:Y# :25346.
d) 17 32s,B4ssl:'ëëE : i2430s2s.
59.5, a)r.
g)':$g: ïÌrré
- : . :: ; -'
, .-,;r .r{.,i..:: ;.a ).::
' 
. :'l':
c) Seres .;..,:não são nuÌos e ro: sb
'rf0 ,: .t.,
(r, s) ,
SoluçÃo.
a) Se a, b ou c é nulo, o resultado é óbvio. suponhamos que c, b e c são não nulos, logo que
[ca, cb] 
- 
lcscbl 
- 
tt]gb]- : t"t lobl 
- 
r"= Go, cb) : l.l(", b) : ltl6ü : lcl[o' bì'
b) Sendo m um múltiplo comum de o e b, temos que
/**\_liil m2 m
\ t't/ - Ti,+I : 1*o-t : [o;b]'
Portanto, (i, ï) : I sê, e somente se, [o,b] : m.
c) Suponhamos ïo : sb. Temos
[o,b] :11 :,11:"0,1.:.lrsabl sb ra' (o, b) lri(a, u) : {r;r) : (r, s).
KHA 78
tl---"
5.26" Sejam o,b,c três números natura-i:. ìïostre que
cbc : [arb,c;íob, oc,bc)-
SoluçÃo.:
'I'emos que
Por outro lado,
Portanto,
[o,b, c] - [o' [b, rJ1 : j*, #l
(ab, oc, bc) : (o[b, c),bc) : (1, c) (o, #)
[o,b,c][ab,cc,bcJ : [",#] tt,c) (c,#)
bc: (b, c)affi : obc.
-o.27 
. Seja n"e' N;''Cá1qule::ffi'+,1 ;ír#Ì};
teirrcs ![ue
t#+t,n*11 :
(nz + 1)(n + 1) 
, se rL é ímpar
2
(t2+1)(n+1), senêPar
L
79 Ê^G
Sor,uçÃo.
a) suponhamos que (o,,bl : [o,b]. como (a,b)lo e alfa,bl, temos qrie o-l(a,b), daí a:
(o, b), o qüe implica que olb. Do mesmo modo, mostra-se que bla, logo a : b.
Reciprocamente, se o : b, é óbvio que
[o,b] : [o, o] : o: (o, o) : (o,b).
b) Pelo ProbÌema 5.9, temos que
ro',b*r : i#5 : ## : (#ï)" : ra,br-
5.29. Sejam o,b 
€ 
Z ambos não nulos. Considere o conjunto
' :: ' ': ""
I
a) Mostre que fo, bl : min (M(o, b) n NJ.
b)'MoÉtre qüe :M(o,'A1'- [a,Ujz.
5,30. Sejam d, ll1 .e ,I$. .Moçtre que uma çondição.uecessária.e..suflcienle para que existem
o,b 
€ 
Z taisque (a,b) : d e [o,b] : m é que d.lm.
Sor,uçÃo.
a) Segue poï ser o mmco menor mirltiplo comum positivo de a e b.
b) E claro que [o,b)V'c M(a,b), pois todo múltiplo do mmc de oe b é múltipio comum de o e
b. Por outro lado, se x 
€ 
M(c., b), pela divisão euclidiana podemos escrever x : [q, b]q +r, onde
0 ( r < [a,b], logo r: x- [a,b]q € M(o,b), pois a diferença de dois múltipios comuns de a e
de b é múltiplo comum desses inteiros. Daí decorre que devemos ter r :0, pois, caso contrário,
teríamos um número r 
€ 
M(o,b) com 0 < r < [a,b], o que contradiria a minimalidade de [s,b]
estabelecida no item (a). Logo temos também que M(a,b) C [c,b]2, o que acaba de mostrar
que M(a,b):la,blZ.
SoluçÃo.
Suponha que existam o e b tais que d : (o, b) e m : [a, b]. Como o mdc de dois númerre
divide o seu mmc, temos que dlm.
^
^
80ND
Reciproca.mente, de d e
[d, m1 : m. Portanto, o :
m são dois números naturais tais que dlm' temos que (d' m) : d e
d e b : rn ê uma solução do Problema'
5.31. Sejam Grr..., o,, € Z\{0} N4ostre que
(ai, a;) :1, t l ) 14 [41, "', oJ : lor " ' o"l'
SoluçÃo.
Podemos, sem perda de generalidade, Supol Que oi € N para todo i - l'"'ron' Fatremos
a demonstração por indução sobre n- Para n : 2, o resultado Segue cia Proposição 
5'15'
Suponhamosoresultadoverdadeiroparan-lesejamolr"''o"€Ntaisque(oi'sj) :1para
todos r,j:],...,Ït, com i+).Decorre d.aí que (4,,...o,Ì.-1,o,,) :1. Como [ot,...,0,'] :
[[ar,...ro._r], aJ e por hipótese de indução [or,...r 0r,-r] - G1 "'on-I, pelo caso rl:2 temos
que
lctr..., orr] : [or "'o*-tr or.] - o1 "'on-l Gn'
Reciprocamente, note que [or,...,or.] ( ar."onr já que [ot,...,o'r] é o menor múltiplo
pmitivo dos números o1, . . . r o11 e que G1 . . ' o," é um múltiplo positivo desses números'
Suponha.mos que [sr, oz] : &1o2, temos que (o1 , o,z) : 1' pois, caso contrário, se (o1 ,o;z) 
:
d> 1, t€ríamos o absurdo
Sryonhamos o resultado válido
Srymhanos por absurdo que Pâra
larr. . ., orr] :
- 
QlGt[or,azl :i1o1o2.
para ïr- l, e seja o,' € N tai que 1o1,"',o"] - sl "'on'
1 < t< j < ntenhamos que (ai,o1) - d> i' Logo'
[ai, olr orr... r oi-1r oi+lr "' r oj-l, oi+lr "'' o"]
[[oi, o;r Glr ... r cli-lr ot+lr "', oi-lr oi+lr "']' o,,']
[oi, oir oir... r oi-lr oi+l r "', oj-l , o1+1 r "'' o"-]]ot'
AiOiOl "'ot-tOi+t "'Oi-tO;+t "'On-l Gn
O1 "' On-l Ont
absurdo.
81 AG
SoluçÃo.
Prova semelhante à da Proposição b.1g.
5.5 A Equação Pitagórica
5:33: Mostre que se
enïão o,ê'6.ia.'áAÈà;
SoluçÃo.
A demonstração é exatamente igual à do Lema 5.20, substituindo o quadrado pela potência
n-ésima.
SoluçÃo.
De fato, pelo Problema b.8(b), (nr,n2 + m2) : (#rm2) : L por outro lado, novamente
peÌo Problema 5.8(b), temos que
(o,c) : bJ 
-m2,r* +n{): (2r}.,n2 +rr}) _ (2,n2+m2) :.1,
onde a última iguaÌdade segue do fato de n2 *m2 ser ímpar, pois n e m têm paridades distintas.
Por outro lado, é fácil ver que (n2 
-fl2rm) : (nz 
-m2,n) : (r] -#,2):1, logo, peloProblema 5.8(c), temos que
(o, b) : (n2 
- 
fl2r2nnt) :1.
Finalmente, o caso (b, cJ : I é semelhante ao caso anterior.
KD ÀAA 82
Soluçeo.
Provar essas asserções diretamente usando apenas a relação 
pitagórica cz : * * b2' não
é tão simples. Vamos mostrar como isso se torna simpÌes, utilizando as 
soluções cle Euclides:
61 : l(r-12 
- 
m2), b :21-r.rr.;- e c:f (n2 + ml)'
De fato,
(c-a)(c-b) V(TJ +iÍ* -# +úG +# -tu*)
--Ên?(n- nt)z
2
(c+a)(c+b) tz(rf +r# +# -#lo+ +# +2*l :L2rt3(n+ *)t
onde c
Sor"uçÃo.
a) como todo número inteiro x escleve-se na formax:3k+i, com i :0'1'2' E fácil
deduzir daí que xz :3Ll j' com j : 0' 1' Alêm disso' x2 :3L se' e somente se' 3lx' Da relação
ú+a2:c2,vemosquesec2:3l,aunicapOSsibilicladeéque 
q2:3reb2:3s,oqueimplica
gueo'bectêmofatorcomum3,oquenãoépermitido,poisotriânguloêpitagÓrico.Portanto,
c2êdaforma3l+.1'oqueimplicaquec2eb2sãod.aforma3re3s*lemalgumaordem.Isso
prova a asserçao.
b) Aqui utilizaremos as soluções d'e Euclides' Temos qu€ o : nz
e b : tJ - rrrze c : n2 +rrf,com rt e m de paridade distinta'
múltiplo de 4, o resultado segue'
e.4.,
::l.r ::ì:::r i :r
,'..;.':l:
tye\q1'u1a,
:; ,.
t-1,]1:1;;,,;:']y11l,,r: lr, t:t t:'1
c)Essefoioconteúdod.oProblema3.34.Refaçamosaprova.Todointeiro
x : 5k { i, como i : 0, 1 ,2r3r4' Elevando ao quadrarlo' vemos que x2 é
onde j:0,'1,4. Além disso, x2:51"se' e somente se' 5lx'
- 
TTJ e b : 2nm ou a:2rLTÍr
Sendo ï+ 
- 
ÍTJ ímPar e 2rtm
x escreve-se na forma
da forma x2:5L* j,
i
t-_
83
-r r- .:. - - --1.-'.-a,:rirj;+Ì'rY::aj5:ii
r
Agora' se c2 : 51, as únicas possibilidades são a2 e b2 da forma 51, o que não é admissÍvel,dado que o triângulo é pitagórico' ou que s2 eb2 assumem cada um deles uma das duas formas:5l + I e 51 * 4. Isso prova a asserção nesse caso.
A possibilidade c2 :5J"* 4 não pode ocorreï em virtude da relação c2 : ,'2f b2. portanto,
só resta a analisar o caso em que c2 : 5L* 1, quand o s2 e b2 têm or. urru,'.'ir cada um deresuma das duas formas: 5l e 5l * .1, provando o resuitado.
d) Decorre imediatamente dos itens anteriores.
l;r1,.1;"r,^T::lï,j-ï" 1 média,|itmética da hipotenüsa com o careto ímpar de um rriânguloprtagórico primitivo é um quadrado.
Sor,uçÃo.
Esse é um o[tr'o exernplo 
-onde o uso das soluções de Euclides tornam o problema trivial.De fato,
o*c n2-rrf*n2+m2
: ïI2,
t t*, MaStre que exutem,infinilos ternoq pita€óricos io;b.,.c),tais.q,üè
a) c é um quadrado; b) ._b : 1
SoluçÃo.
a) Devemos mostrar que existem infinitos ternos pitagóricos satisfazendo a equaçã o s2 +b2 
-c2, com c: d2. Podemos escrever d2: c:'rt2 **i., o:Ír2 
-n,'2 eb:2..,m,onde n,m e N,(n,m) :l e-n>m.
A equação d2 :n2 *m2 tem as seguintes soluções primitivas: d,:f*s2, n:l_s2 em:2Ts, onde r,s 
€ N, (r,s) : I e r > s.
Portanto,osternospitagóricos c:ü:(r2+s2)r, o:(r, _rr)r_4r2s2eb: 
 rs(f_,z),onde r,s 
€ N, (r,s): I e r ) s, são soluções do problema.
b) usando as soluções de Eucrides, a condição c-b 
- 
1 é equivaÌente a 1:nz , 
''.2_zrtrn:(n-m)2, já que b deve seï par por c ser ímpar. portanto, equivaiente a ïÌ:m*r.Agora, é só tomar as soÌuções da forma c:ÍL2-rn* : (m*r )r+mr,b :2rtm:2m(m*rì
e c : rt2 
-m2: (m+ l)2 
-mz.
ND ^ 
^'
84
Ìs..eg. Mosrre que se relaxarmos a condição sobre '' e '* na solução * u"t]tti_l;ï .].tï
pitagOrica, eliminando a restrição (n, m) : .1, mas só mantendo n > m) as eKpIpFSqe! :x :
...i 
-ÍT\:,u:2rrr*e z:nr +n},são ainda soluções cla equação X2 +,, 
= 
(.}'1 '" ol.
,desse modo ainda não obtemos todas as soluções (incluindo as não primitivas) da equaçãô'
SoluçÃo. 
-_ 
- 
Ã\r
E imediato verificar que x - 
'{-Tn2,! :hlne z:"r}+m2' quaisquer que sejam n'm 
€ 
N'
com r-L ) ffi, são soluções da equação X2 +Y2:22' Para ver que tais soÌuções não descrevem
todas as soluções, basta verificar qile o terno (361641100) não pode se explessaÏ desse modo'
5:40. Existem
a) 78?
triânguios Pitagóricos com
b) 120? c) 1 .000?
as seguintes áreas
cl) 2.730?
SoluçÃo.
a) Para que exista tal triânguÌo deveriam existir n' m €
paridades distintas tais que
N, com (*,*) : 1, n ) m e de
nrn(n 
- 
m)(n + m) :78 : 13 x 3 x 2'
Comoosquatronúmerosnaturais0,fr,1.t-men*msãocloisadoiscoprimos'devemoster
m: I ou rr-m: L Nenhuma dessas possibilidades conduzem a uma solução da equação
acimâ- Portanto, a resPosta é não'
b) O mesmo procedimento conduz-nos à resposta não'
c) Idem.
d) O mesno proced.irnerrto conduz.nos à soiução 11 : l0 e m: 3' Portanto' â' resposta é sim e
o terno pitagórico é (60,91,109).
Froblemas SuPlemeïïtares
85 ÀnH
O número ït : ct....otoo representad,o na base 10
número or . . . o1 
- 
2oe é múttipto de 7.
é, d,,iuiisíü-ct :gar.7 'e..:S'A-ffiente
.'.:1: l .. :
se, g
k)r Ú-riiirã ;;piitiáisi+'árb;i' 
" 
uriã;io' áôr*a, para'mifi eâr se o número
de /. : 32.789 ê.,.au
Sor,uçÃo.
a) Note que
2(Ac * r) + (c 
- 
2r):21c.
Corno 21c ê divisível por 7, temos que c 
-2r ê, divisível por 7 se, e somente se, 2(10c*r) c
divisível por 7, o que é equivalente a I 0c * r ser divisível por 7 ,iá que (2,71 : 1 .
b) Sen:c'...oro0,representadonabasel0,aplica-seoitem(a) aonúmeronescritonaforma
ï1 : or... o1 . l0 * oo.
c) Fortanto, temos qu,e 32.78g é múltiplo de Z se,
de 7. Repetindo o argumento, 3.250 é múltipÌo
Novamente,326 é múltiplo de 7 se, e somente se,
caso.
e somente se,3.278 
- 
lB : 3.260 é múltiplo
de / se, e somente se, 
-226 é múltipto de 7.
32 
- 
12 : 20 ê múltiplo de 7, o que não é o
5.42. Seja o eZímpar,
a),C.picufe,{.,t, :o..#.5,.q-17J 
.,
Sor,uçÃo.
a) Como o. é ímpar, temos que s. t 3 e a 17 são pares, logo
(a*3,o*5, s*7) :
:
b) mdc{o -t2n+ l;n 
€ 
Z}:2.
((a+3,af5),o*7)
((o +3, o *5 
- 
(a + 3)J, a 1-7)
((o + 3,,2), a + 7) : (2, o * 7) : 2.
AAA 86
Sor.uçÃo.
a) De fato, cd.:l1ob e C: mo, logo mad: ruob. Portanto, md: rrb. Como (b,d; :1,
temos que blm, iogo m - lb, o que implica que c : lba' Issc mostra que oblc'
b) Note inicialmente que o produto de r números naturais consecutivos é divisível por r!. De
fato,
Em seguida, note que
(o+.1)(s+2) "'(a+r) 
-r!
/2n\ (2n)l 2n(2n- 1) "' {n+2):
\^/ - nlnl - n!
("1) €N. (5 1)
(5.2)+l).
Pondo a: (*-l)!, b:rr, c:Ztr(Zn-l)"'(n'l 2) e d:ïÌ*1' temos que ablcd' Por
outrolado'de(1)temosqueolc'obviamente[b'd'):(n'n*]):l'logo'por(a)'temosclue
ablc, o que prova o que se querla'
S.44.Sejamo,brc,deNtaisque(o,b)=(c,'dJ:'1'Mostrequeseod:bc'entãoo:ce
b: d.
Sor,uçÃo.
De fato, tem-se olbc e pelo Lema de Gauss segue-se que olc. Inversamente, tem-se 
que clod
e (crdj:1, logo clo. Tendo em vista que os números são naturais, segue-se que o: c €r
consequentemente, b : d.
5.45. Sejam.ae.b ctoisnúmelo naturais, Conside,le o algoritmo de Euclides para determinar
, : ii:.i.l.:.rìr r.r; .:.i
Tn.-2: T* 1Qnf ln
i
lIÈ-
87 AEã
Soi-uçÃo.
iVlultiplique a primeira igualdade por ï0 : ll, a segunda
seguida, some membro a membro as igualdades obticlas.
por ï1, a terceira por ï2 etc. Em
5.46. Sejam o, b, o,, b,, fl,m) r, s e Z Áis que jms _ nrl : 1.
b/ : ro. * sb, então (o,, b,) : (o, b).
N{ostre que se o/ : mo f nb e
Sor,uçÃo.
Basta, peÌo Teorema 5.7,
nb e I(o, b) e b/ : ro*sb 
€
as relações entre c, b, a, e b,
mostrar nessa situação que I(o,,b,) : i(a,b). Como s/: mof ,
I(4, b), temos que I(a,, b,) c I(a, b). por outro lado, manipuiando
temos que
sq-'- llb' : smo 
-. 
nrb : (sm _ nr) _ :ta,
ro' 
-mb' : rnb - smb : (rn_ sm) : çb.
Donde o 
€ I(o,,b,) e b e I(o/,b,)
, ou seja, I(o,b) c I(o,,b,).
Froblemas Propostos
1. Seja m um número natural. Mostre que
a) 1615* 
- 
i ê=) 4lm;
b) 914* 
- 
1 ê=* 3lm;
c) Se m é Ímpar, mostre que não há nenhum número natural Ímpar o tal que (a+.1 )rlo*+ t.2- Suponhaque o e b sejam doisinteiros tais que (o,b) : l. Calcule (s+b,a_b,ob).
3' a) sejam dados dois números naturais s e d.. Mostre que existem dois números inteirqs x e utais que x*A: s e (x,U) : d se, e somente se, dls.
b) Mostre que existem infinitos pares de inteiros x e U tais que x+U:.100 e (x,g):5. Achetoclas as soluções positivas.
4. Ache todos os pares de números naturais x e ltais que (x,V) : 10 e
5' Ache todas os ternos de números naturais x, u € ztaisque (x, !rz):
6. Sabendo que (o,4) : (b, 4) : 2, calcuÌe (a * b,4).
fx,gl : i00.
10 e [x, !,2] :700.
NBA 8B
,tr't
cr=iilpã
-e7ã
áërlé_rf ã#r=
E-;ro:Çrl
rl
É*F
t-
ã5rt
Gll
-t4,
*1#
.Ath
)F
rü7777H
;-;#r}r+rrirt
rfl
.InJl#
7. Seja n urn número natural maior do que 6'
clols números naturais coPrimos'
Sugestão. Escreva n na forma 4rrr+ i, com i
8. Sejam a,b € N. Definimos
I(a,b) :{x € N; lu,v € N, x:\La-vb}'
](b, a) : {x € N; lu,v € N, x : ub -va}'
Mostre que |(o,b) : J[b,o): dN' onde d: [a'b)'
g. Ache os números naturais ïï para os quais o número n(r' * 14 ) seja um quadraclo' I
10. Um terno pitagórico consistindo de três números em PA ê' (3'4'5)' \{ostre que os ternos
daforma (31,41,51) são os únicos ternos pitagÓricos formados por três números 
em PA'
11. Determine todos os triângulos pitagÓricos cuja área vale 360'
12. Determine todos os triânguios pitagóricos cujo perímetro vale
a) 80; b) 110.
13.Umtriânguioéditoheroni'anoseasmedidasd'osseusladosedesuaáreasãonúmeros
naturais. Por exemplo, todo triânguio pitagÓrïco é heroniano'
Utilizando a fÓrmula para a área de um triânguloÀ:@,
mde o"b e c são os lados d.o triângulo e s o seu semiperímetro, teste se 
os seguintes triângulos
[orb, c) são heronianos:
") (7:15,20); b) (9,10,17); c) (13' 24'25); 
d) (39'41'50)'
L4. Ache as soÌuções primitivas da equação X2 + ZYz:Zz'
Respostaix:*(n'- 2"Ì)' a:Zrvrrt e z:r*+Ztr*' com (rr'2m) :1'
Mostre que podemos escrever rr como soma de
:011,,2r3.
89 Are
ã
á
R{
ãrr
á
*{
{F#F;r
E-
#l
;{)
+t
c-
*t
-{rilrÇt
--
*sF
,-7h
-;-777
'rt
7
*tFFFF
#attf,
]-
á
í-
á)
ã
,qFLãü,qÇ*Hs **
h/ãAxrh/Ã# *ãvrs*R
iloï!€uM
6.1 Equações Diofantinas Lineares
SoluçÃo.
a) Solução geral: x:55 *14t, U:-176-45t, t€V'.
b) Solução geral: x : 333 
-28t, ! :295 - 25L, t e V".
c) Soluçãogeral: x:135-13t, U:8.| 
-8t,tÇ2.
d) Soiução geral: x : -l15+ 13i, U : 69 *8t, t eV'.
6.2. Para quais valores de c em I\ a equação1OX +14Y 
= 
c não pgssui'soluções em NU{0i?
Soi,uçÃo.
Inicialmente observemos que a equação não possui soluções quando c é ímpar. Quando c é
par, a equação original tem solução se, e somente ser â equação 5x t 7y : ! admite solução.
Essa última equação não possui solução quando
l: l, 2, 3, 4', 6, 8, 9, 11',-l3, 
.l6, 18, 23'
qqqq
fF!r;;rqqeqqqq
ë
ü
;ï
art
Uã
'HC"
€
ë
ê
aj
IF
>r-
lE
a)
f-
Ë
aÊ
CË
cËt
IIF
C-F
ê
€
Ç
Ç
F
Ç
Ç
6.3. Resolva em N U{0} as equações:
a) 16X t7Y :601 b) 30X +17Y:201
c) 47X + 29Y : 1288 d) 8X -f 13Y : 23
SoluçÃo.
a) Solução minimaÌ: xo : 3 e Ao :79.
Solução geral: x:3*7t, !:79 _ 16t. Como estamos buscando as soluções em NU{0},
devemos ter 0 ( t ( 4; logo as soluções são:
(3,7?), (10,63), (17.,47), (24,31), (31,15).
b) Solução minimal: xo :5 e Uo :3.
92NDA
solução geral: x:5 + 17t, ! : 3- 30t. como estamos buscando as soluções em N u {0}'
devemos ter t :0; logo a única solução é (5' 3)'
c) Soiução minimal: xo :20 e !6 :12'
Soluçãogerai:x:20+29í,a:12-ATt.ComoestamosbuscandoassoluçõesemNU{0}'
clevemos ter t:0; logo a única soiução é a solução minimal QAJL)'
d) Não tem solução.
6.4. Dispondo de 100 reais, quais são as guant-ias que se podem gastar comprando selgs d.,e ,S
'':' ";':'':Ì'''. 'I 
r' i' l
ô
reais e de 7 reais'/ '
SoluçÃo.
Podem ser gastos os seguintes valores:
5r 7, 10) 12., 14, 15, 17, 19, Zor 21, 22',
bem como todos os naturais de 24 a 100'
6.5- Determine,todos os
a) 79; b) 80;
múltiplos naturaÌs,{e
c) 270.
II e de 9,,cuja soma é igual a
t,ãf:
áFta
*l
-t
ã-rr
áãr
rll
ã
rú
*a
ã
â
ãil
rf
--l
--FF
á
áFFFt7
*tt
*lFJA
ãl
-ta
*t
+lF
{)
--
--
á-ãi
'â
Sor,uçÃo.
a) Não existem.
b) Uma única soiução: (44,36)'
c) Duas soluções: (99,171) e (198,72)'
6.6. Determine o menor
mente, por 37 e 48.
inteiro positivo que tem restos 11 e 35 quando dividido, respeçtivq'-
SoluçÃo.
O inteiro n pïocurado tem que satisfazer às igualdades
n:37x*11 e rl:489 *35
93 AEH
para alguns x,U 
€ 
NU{0}.
Logo, devemos procurar
equação é clada por
as soluções da equação 37x 
- 
48a 
- 
24. A solução geral dessa
x: 13. 24-49t, u : I 0. 24 
-37t.
Como A > 0, isso implica que t < 6. Como estamos procurando n mínimo, isso ocorre quando
t : 6, conduzindo à resposta Í1 : 24. 37* ll : ggg.
6'7' Numa criação de coelhos e galinhas, contaram-se 400 pés. Quantas s{o as gaÌi4has e
quantos são os coeÌhos, sabenclo que a diferença entre esses cloisnúmeros é a menor possível?
Sor,uçÃo.
Se c é o número de coelhos e g o
2c * g :200.
número de galinhas, temos que 4c * 29 :400, ou seja.
Devemos achar a solução dessa última equação sujeita à condição lc 
- 
gl mínimo.
Como 9o:0 ê c6 :100 é uma solução particular, a solução geral é dada por c: .100-t eg:2t; logo lc- gl : lloo-3t1, o qual é mínimo para t :33,o que nos diz que o número de
coelhos ê 67 e o de galinhas ê 66.
6'8' Subindo uma escada de dois em dois degraus, sobra um degrau. Subindo a mesma escada
de três em três degraus, sobram dois degraris. Determine qu;ïto, a*;r, ;r;;; ;.r.;
sabendo que o seu número é múltiplo de 7 e está compreendido entre 40 e 100.
SoluçÃo.
Sendo n o número de degraus, temos que Íì"
40 ( n < 100 e n múltiplo de 7.
:2x*1- 39 *2para aÌguns x,g 
€ N,
Somos conduzidos à seguinte equação diofantina , Zx-3y: I , cuja solução geral é x :2_3t
e U:1 
-2t.
A condição 40 ( n ( .l00 implica que 
-.15 < t < -6 e a condição de n ser múltiplo de 7implica que t : 
-12. assim, a escada lem 77 degraus.
94
|#
as cédulas 5flç,'ds 1$4
Sor,uçÃo.
O conclutor de S (4,7) ê rc:3-6:18, logo a resposta ê (b): a partii de $,l8'
inciusive.
SoluçÃo.
Trata-se de determinar as soluções da ecluação
10; x:5,1 : 7;x:10,U : 41x:15'g :1'
3x*59 :50 em Nu{0}' Essas são x:0'U :
á=
.ra 
=#.=
á=
á:
á,
á
#a
á
ãí)
rAãt
á
â
+t
l|3
c4
á'-*
,*,7h
b
.ü77>|7?c)#
.tüh
>r
**
*.
*1
cfdP
-!ï
-!3c!Ü
-4lCI
6-11.
SoluçÃo. , t ^ì,r:
Se a equação possui uma solução b',...,b*, como d: (or'.",onJ divide cada oi' temos
que d divide o1b1 * "'* o''b*, logo d divide c'
Reciprocamente, suponhamos que c: rÍL'(at'"''s"')' Pelo problema 5'23 sabemos que
existem inteiros ctr...r c* tais que
(oir..., crr) : í1C1+ "' + o"Cn'
Logo,
o qne mostra que
c : ÍïL' (or,. .', o*) : olïÌtcl +' " + s'Lmcrr,)
bi. : ïtrcr, i: 1,. ..rÊ, é uma soluçao da equação diofantlna'
rìKJÚ ê6H
I
I-'hq
6.2 Expressões Binômias
6.12. Sejam o,m)n 
€ 
Ní, com o > i. N{ostre que c*- Jla*- 1 se, e somente se, n[m.
SoluçÃo.
Como (o* 
- 
1, a*
-l): o(m,n)-1, temos que c'-l cl.ivide cL*-1 se, e sornente se,
gt- I : (o*- Ir ot- l) : o(m'tt) 
- 
1,
o que é equivaiente a n : (ïïr, n), que por sua vez é equivalente a nlm.
q<
q
Ç/
ü
€qqqqqqqqf;i!r
-lH
át
ü
.t(üE
aE
-;:F
JF
fF
-;#
fÉ
aË
aÉ
ü
TJJ
ë
Ç(F
ëede
ë
.m6.13". Sejam n, rn 
€ 
N com nlm e 
- 
impar. Se a € N, mostre queït r'-
"'r ' t,: (o*fl,ao*,1)'=,o*+-l.
;:i:l:1::1!r:rl: I :L: :'::' ::a: 
-:'': 
-.
;1 ",''li , ,:r li lrf i i: :::.: : :
SoluçÃo.
Nessa situação,
**_
(m,n)2
logo, pelo CoroÌário 6.21, temos que
(a*+ l, a^_;- 1) 
- 
s(*'*) + I : o*+ l.
m
ã,
qq
SoluçÃo.
Aplique o Corolário 6.22 com "çnt :2^ no lugar de m e ïr' : 2n no lugar de n.
6.15. Calcule
r) (5202+1,574+1);
Kã 
^à
Í
'i:'ll 
rr':i:r 
'
aj 36oit +t,3621ôii); c) (3104-t,Jza+'11.
96
SoluçÃo.
Respostas (a) 52 + 1; (b) l; (c) 36 + 1.
6.16. Seja (M"J. a sequência definida por M.,:2n 
- 
1. lVlostre que
a) 3lM" se, e somente se, n é par;
b) 5lM" se) e sonÌente se, n é múltiplo de 4;
c) 9lM,,. se, e somente se, n é múltiplo de 6.
SoruçÃo.
a) Como M,, : 2n 
- 
1 e 3 : 21_1 , temos que 3lM,' se, e somente se, (2' 
- 
1 ,2 + I ) : 2 + I .
Pelo Corolirio 6.22, essa última condição ê equivalente a (n,l) : 1 . 6fu ,Ó par, ou seja,
quando n é par.
b) Como M,., : 2n 
-1 e 5 : 22 +1 , temos que 51M,. se, e somente se, (2'- 1 ,22 +1) :22 +1. Pelo
Corolário 6.22, essa última conclição é equivalente a (n, 2) 
-- 
2. 6}1 é par, ou seja, quando n
é um múltipio de 4.
c) Como Iúr.: T-1 e9 :23+1,temos que 91M,, se, e somente se, (2*-1 ,23+1):23+.l. Pelo
Corolário 6.22, essa última condição é equivalente a (n,3) : 3 u J". é par, ou seja, quando ntnr JJ
é um multiplo de 6.
6.3 Números de ï'ibonacci
6.17. Mo-stre. que, 
, 
se :na sêquêncla de ,Fibonacci existir um
natural m, então existem infinitos tais termos.
Sor,uçÃo.
Suponhamos que mlrr". Pelo Teorema 6.25 temos que
(un ru*) : ü1kn,n) : tlnr Vk e N.
Logo, u*luu, para todo k e N. Portanto, ïftlun, para todo k e N.
ÀAA97
6.18. Na sequência de Fibonacci, mostre que
a) u* é par se, e somenle se, m é divisÍvel por 3;
b) .r^ é divisível por 5 se, e somente se, m e aivisivel por 5;
c) u^ é divisÍvel por 13 se, e somente se, m é divisíver por z.
SoluçÃo.
a) Observando que ]:112t pelo CoroÌário 6.26, temos que
2lu* ç=4 qlu* ç=1 3lm"
b) Observando que 5 : .Lts, pelo Corol inio 6.26, temos que
5lu^ ê* u5lu* e) 5lm.
c) Observanclo que 13:1Lt, pel,c Corolârio 6.Z6,temos que
l3lu* ê+ uTlr-h. ê+ 7lm.
fCIclcTGIt;,ljlÇfÇt?t;t;lolçlr
{Íi#iGl-lElÇ:lçi?lË
íÇi.i.F
í-iqi-i,itti:jCjËiËiCrj-
iÉiq
:Ëid
'Jf
', 1ü
:-j
.eeLë
-Ë üq
ú
6.19. Na sequência cle Fibonacci, mostre que
a) u^ é divìsível por 21 sempre que m for divisível por g;
,ib) r- é divisÍvel por 8 sempre que m for divisível por 6.
veremos no Exemplo g.26 que valem as recÍprocas dos itens acima.
Sor,uçÃo.
como nlm -J rrrlu", 
€ rL6 : B e us 
- 
21, ambos os resultados seguem.
Sor,uçÃo.
a) Sabemos do Teorema 6.2b que
trHA
(rtrrrtr"l*z) : at(n,n+2) : U1n,z1 : 1.
b) Sabemos do Teorema 6.25 que
(rt,rL,,-,*:) : tl1n,n+3) : ü1n,3)
c) Sabemos do Teorema 6.25 que
(tçr tt r*o) : tl1n,n+4) : 1"11n,4)
(:t l) se3 ln2, se 3ln.
:{ i, se4 fn3, se 4ln"
6:2L.
p.oi,.8,
SoluçÃo.
Suponhamos que tln : 8q + 4, logo
'tt1n,6) : (rr-,*u) : (u',',8) : (u' 
- 
8Q,8) : (4' 8) :4'
Isso mostra que não existe tai n, pois não há nenhum número de Fibonacci igual a 4'
Problemas SuPlernentares
SoluçÃo.
Seja X o número de homens,
Por outro lado,
Y o cie mulheres e Z o de crianças' Assim, temos
X+Y *Z:30'
2000X + 500Y + 1002 : 30000,
(6 1)
cìCI
AAÂ
logo, devemos resolver o sistema,
7
X+Y *Z:30
20X+5Y + Z:300
uma solução minimal (x,u) da equação 19xj_4Y:270 êtal que 0 < x ( 3 (veja a discussãologo acima da Proposição 6.9). Testando valores, vemos que (2,58) é uma solução particular
dessaequa,ção, iogo asolução geralé x:Z*4t eg:58 
- 
1gt,com t 
€N. portanto, âsoluçãogeraÌ do sistema (1) é clada por
x: Z I4t
U :58 
-19t
z:30 
-x_U: _30+ l5t
Assim, a única possibilidade é t:3, logo x:14,U:1 e z:15.
r'ç9
ë
ë
ë
ë
a2
ë
t?
ë
ë
Ç
aj
Ç
ë
ë
ë
Çrqq
-t
ç
ë
ÇÊ
rF
-:;
-1Ú>d
;;
Ë
FF
-rr
-:ë
aË
JÊ
ë
ê
ü
JÊ
ê
íx*Y+z:30
._ | rlx l_4Y:270
distintos (xt,Ur) e (xz,Uz), no plano, que são
o.,b e c são números naturais com (o,b):1_
6.23. Ache a menor distância entre dois pontos
soluções da equação diofantìna o.X-by: c. onde
SoluçÃo.
Sejam P1 : (x1,Ur)e Pz: (xz,g2) duas soluções daequação ax- by: c. Logo ,x2:xr *tb
€ uz : ur -l to para algum t 
€2. seja d a distância entre p1 e p2, logo
d2 : (xz 
- 
xt)2 + (Uz 
- 
Uì2: (tb)2 + (to)2 : t2(a2+ bt).
Portanto, a menor 
'distância não nuÌa entre dois pontos p1 ep2ocome quando t: *l; logo a
menor distância entre dois pontos distintos é dada por d : \/ãL+bz.
:''n' 
sejam 
",1-'),.o* (o,b) : 1. Mostre que s(o,b) é simétrico no seguinte sentido:para todos z,w 
€ Nu{0}, comz*w = K_ l, onde r: (o_ 1)(b_ l) é o.orrd,ito. de S(o,b}-tem-seque :i:.r"I '' ' r"::r':li:':'r :::l 
''
conclua què no intervalo 0 < u { K- I 
- 
ab- a-b existeú tantos èlementos pertencentes aS(o, b), quantos elementos não pertencentes a S(o,b).
i00
4t*
.*
^.ÀA
+rãrErã
rã
l.E
l.ënìtr:ir:f:tp
nft
+r
+r
''lbh
+r
+ìlìtJ.TIhh
ilrl|5t
'ü
,'
't
üp
F.fflt
Ëfrt_t't
*
Ëtütü
E
SoluçÃo.
A maior lacuna cle s(a,b) é, pelo Corolário 6.8, dada por K - I - (b - l)o- s'
Suponhamos que ze S(orb) e quew e NU{0}seja tai que zlw: r(-1' 1'emos então que
w 4S(s,b), pois caso contrário r-l : z*w e S(a,b), umabsurdo'
Reciprocamente, suponhamos qrle w É S(s,bJ e que z e NU{0} seja tal que z*w: K - l'
Temos, pelo corolário 6.6, que w:rÍL[--nb, oncle 0 (m<b en"e N' Daísegue-seque
z-- K- I 
-*: (b - l)s-b -w: (b - I -m)a* (rr- i)b e S(a,b)'
jáqueb-l-rn)0en-1>0.
6.25. Sejam c,1t(12t...rQ. g N tais que (o1 ,Q2t...,orr) .- l' Definamos
S(41,o2,...,G.,) :{x1o1 |_xzaz+ "'+x,rcni xirx2r"'txr. e NU{0}}'
N4ostre que existe um número nalural K para o qual
x e S(o1 tozi"',o.)' Vx) r'
'l
Sugestão. A condiÇâo (a1, o2r. ..r á^) = i implìcá,,péio Pfoblella n ZZ,,que exrstem núúliol
inteiros x1tK2t..,- tais que xrar I xzazl* **',ãr' ='1 Sêparando os termos positivos
de um lado e transferinclo os termos nggatlyos para"o outro, vemos que existe o e N tal que
c"o-i-leS(gr'....,G*).Portanto,::,..,.:.....,..i...
' i ...
ComoxeS{o,a*1)
todo x 2 (o-'1)o.
SoluçÃo.
A solução do problema foi dada na Sugestão.
Problemas Propostos
1. seja n e N. Resolva em X e Y, nos inteiros, a equação diofantina
(n f 1)tx + tlY :1.II
l
I
I
!
!
t
I
i
I
II
íÍIË
101
^à KH
2. Ache o maior valor de c para o quai a equação SX+7y: c tenha exatarnente nove soluções
em N u {0}.
3' (PROFMAT 2011) Em Tumbólia a unidade monetária ê a pataca, e existem scmenie dois
tipos cle moedas: de 7 e de 15 patacas. Deseja-se compïaï uma peteca com um certo número
de moedas e recebendo no máximo duas moeclas de troco. Determine os possíveis preços (que,
em Tumbóiia, sempre são dacios por uma quantidade inteira de patacas) da peteca para os quais
isso não seja possível.
4' (Problema do Século 16) Um total de 4l pessoas entre homens, mulheres e crianÇas fora.m a
um banquete e juntos gastaram 40 patacas. Cada homem pagou 4 patacas, cada mulh er Z patacas
e cada criança um terço de pataca. Quantos homens, quantas mulheres e quantas crianças havia
no banquete?
5' (Proposto por EuÌer) Um grupo cle homens e mulheres gastou numa taberna \.000 patacas.
Cacla homem pagou 19 patacas e cada rnulher 13. Quantos eram os homens e quantas eram as
mulheres?
6' Uma pessoa comprou cavalos e bois. Foram pagos 37 escud,os por cavalo e 20 por boi. e
sabe-se que toclos os bois custaram 7 escud,os a mais do que todos os cavalos. euantos cavalos
e quantos bois foram comprados, sabendo que o número de bois está entre 40 e gE?
7. Resolva o sistema de equações diofantinas:
6X-Y *52:3
2X+Y-Z:g
lqT;t'h1qlqiüifir:i;r
rTãiái;-i#i#i;:!qi;í
:* q
:?7:
-:aÊ1n
aÊCÊÜr.
.r;
, el:
;Ë
E
Ë:
Ç-
B. sejam o e b inteiros com o 
-b +0 e seja n um número natural.
(o^ 
-b- \
\ o-b, "-o ) : (*(o,b)n-t,o-b) .
g. Sejam a- e b inteiros com a +b +0. Mostre que
a) se n é um número natural ímpar.
f 
*ï::,o+b) : (*(o,b)n-r,a*b) 
.\ a*b /
b) se (a,b) : 1 e p > 2 é um número primo, então
(i+#,"*o)
Mostre que
:{ I, sept(o+b)pt sepl(o+b)
L02reã
ildGi
Ç-dd.daái
,ã
á
,áÇt€:,.Grl 
=-=.çf $,='-ti ã..,'dr =ãCF
d.#
,14
à-
FJuh/EffiR*s Fm,ãh/Ã#g
rf
-tülda
ã
,ã'F
,.Uí,4
;fd)
*t
^ë1
-4d-Cnëaéa
d-
dü
,á
44
d-
-ü
í{Ét
á
aâ
F
nuqrero
Ç
Ë?
Ç
Çd
Ë
Il
riq
Ç
a;
rj?
ç
7 -! Teorema Fundamental da Aritrnética
7.L. Ache os póssÍveis
a) 2Z divisores;
valores de n, m e N u {0} de modo que o
b) 243 divisores.
SoluçÃo.
O número de divisores de a : 9*]0'. 
- 
32n2n5n é ígual a
d(a.) : (2rru-t l)(n+ t)(n+ 1): {2m+ l)(n+ l)z
a) d(a) :27 implicaque (2tn+1){n+1)2:33,cujassoluçõessão m: I ,.ír:2€ï!:0,m:.13'
b) d(g-) :243 implica que (2m+ l)(n+ l)2 
- 
3t, cujas soluções são 1tr:0, m: ..21i ïl:Zrr:";:l3en:B,m:1.
7.2- Qual é a forma geral dos números naturais que admitem:
a) um só divisor além de 1 e dele próprio?
b) um número primo de divisores?
Sor,uçÃo.
Escrevamos rr : pï, . . .pï" 
.
a) Os números procurados devem satisfazer à condição (cur+l)...(a,+ l) :3. Isso implica
que ï : I e h * 1 : 3, logo &t : 2. Fortanto, esses são da forma rL :p2,com p primo.
b) os números procurados dejvemsatisfazer (er+l)...(a,+l) : q, onde q é um número primo.
Isso implica que r: I e ar * 1 : q,logo a1 -_ q- l. Portanto, esses são da formarL:pQ-r,
compeqprimos.
7.3- sejam o,b 
€ N, com (o,b) :1. lVlostre que, se ob é um quadrado, então a e b são
quadrados. Generalize para ob uma potência r_ésima.
:r-id
=\\j-t
t\Ìb?
Iiqi7-
Sor,uçÃo.
Suponhamos que ab
dos fatores primos de b,
: p1"t . . .pl"'. Como (a, b)
logo se pi é um fator primo
: l, os fatores primos de a são distintos
de o, então pl". ê um fator de a. o qüe
tlFleïr*l-ltPlrPleV
lF
rrr
aÊ
ts;d
r)
-;lËd
É(tË
l|F
tF
Ë
É
l;
rt:
1rË
e
.F
.4
rcA 104
tftltlr!
,f,
:rlrttfItTtt
ifllrr|.|f
ìirl
JI
e)ilnift!
-
't
t7
{u
#a
+f
+flafr
Jüfrtfr
aÜ
á
ì{
#rD
ã
mostra que o é um quadrado, o mesmo ocorrendo para b. A generalizaçã"o segue a mesma linha
c1e raciocínio.
7.4. Seja m e N. Pode o número m(m * 1) ser a sétima potência de um número natural?
(Generalize).
SoluçÃo.
A resposta é não. De fato, suponhamos que m(m+ l) : s7' Como (m,m+ l) : 1, pelo
problema anterior, temos que m : c7 em* I 
-b',ou seja b7 - c7 : l. Como,
1 :b7 
- 
c7 :(b 
- 
c)(u6 + cbs + c2ba + c3b3 + cab2 +c5b + c61,
devemosterb-c:'l eb6+cbs +c2b4+c3b3 +c4b2+csb *c6:l.IssosóépossÍvelseb:l
e c : 0, logo m(m + I ) : b7 c7 :0, contradição. Esse argumento generaliza-se para qualquer
potência.
7.5. (ENC-2002) Qual é o menor valor do número natural ïr que torna n! divisível por 1.000?
)oLLçÂO.
Como .l000: 2' .5', para termos 53lnl, devemos ter n >15. Como 23115!, a nossa resposta
e':1: 15-
?.6. llostre que a-soma cle todos os números naturáis menores ou iguais a n divide o seü
lproduto se, e somente se,l n* I é composto. ': , , '
Sor,uçÃo.
Usando a notação
devemos mostrar que S,.ln! se,
S.ln!
S,,: I +2+"'*n: {T!
e somente se, rr + 'l é composto. Temos que
fi +nìn,r-----\ \ ' / tlr 4+(1 +n)nl2n!\------z 2 l,
<+ (l +n)12(n-l)1.
^.AA105
:t-::.i1:*:Ìr,1irr:iï?irisrrii
Portanto, estamos reduziclos a provar que ïr-F.l ê composio se, e somente se, nf I 12(n- lì:.
Se n* 112(n- l)!, então n* I é composto, pois n* I é maior do que qualquer fator pri:no
de 2(n- l)!.
Suponhamos que n*l seja composto, logo pelo Exemplo 7.10, temos que n*1 divide (n-ì11.
Ìogo divide 2(n 
- 
1)!.
7;7.' Usando'a ca4act'erizaÇãô dê mclc:e mmc de dois númeios'natufais a e b através da fatoração
em pnmos desses numeros) pïove que
Soi,uçÃo.
Basta observar que max{a,Í3}+min{a.,í3}: a+ í3. Aplique isso à decomposição de o eb
em fatores primos.
7.8. Mostre que todo modo;,í1nico como difergnça de dois
' ':. ,,. ., ::.: . . . 
.1,! : . ':
quadr.ados.
SoluçÃo.
Considere a equação p :xz 
-92, logo
p:* _A2: (x_U)(x+U).
Comop éprimodevemosterx-g: I e x+A- p. Pelofatodep serÍmpar, temosuma (única)
solução *:* eU:+.
S e' p Qiúild e,p, p,í:tíd,uiie..,.:dè.t,, di,uide,úm
. : ::.a:.:+!t:::j.:r:l
'::::t1:r:::iì:ì r' .
SoluçÃo.
Suponha qiie p
coml<c<pe1
tenha a propriedade mencionada, mas
< b < p, e, portanto, plo ou plb, logo 1
que não seja primo.
<p<ae1<p<
Assim ? : cb
b, contraüção.
KãA 106
il
á
ã#t
--bts
-f
-áFçrl
{
rr)thh
ã
ã
ã
c)taFF
--
,-)ir
*:
{.
-ê
{t
*Cp
--pl
â
-â
â
{
ü
J.
Ç-
ri
rã
Ëi.ffig::1.'Ìdínm)ir'
Mostre quel se n e rri são cÌois númêios'nàïuraiS"não nülos tais que (tr,ttÏ=,],,êttão
: d(n)d(m). ' :
SoluçÃo.
Se m:pï' ".pï' ê ïr: qf'..-4F,, acondição (m,n) : I implicaque pit eiparatodosi
e j. Logo temos que a decomposição em fatores primos de mn é dada por
pï' "'pï'ql'"'Qf',
Assim,
d(nm) : (ccr + 1)' " (q"+ 1)(í3r + 1)'.' (í3,+ l) : d(m)d(n).
7.1'L. ÌvÍostre que, se n>V é composto, então o n-ésimo número de Fibonacci u* é composto.F--
Sor-uçÃo.
Note que todonúmero ÍL>4possuium divisor rtal que 3 (r<n. Logo,
2:tl,s(tç<tr,..
Como r+lu"., já que rln (cf. Lema 6.24), segue-seque u,. é composto.
!
IIL
Fdúmeros Primos
SoluçÃo.
a) 239 é primo, pois basta verificar que nenhum dos primos 2,315,7r11 e '13 o dividem, já
que i72:28? >239.
b) 241 é primo, pois basta verificar que nenhum dos primos 2,3r5r7r11 e 13 o dividem, já que
172 :289 > 241.
AEH107
-:Fïrïrfí:_#ï ïiÍ:
c) 247 é primo, pois basta verificar que nenhum dos primos 2,3,517r11 e l3 o clividern, já que
172:289 >247.
d) 253 :23 .11, Iogo não ê primo.
e) 1.789 é primo, pois bastaverificar que nenhum dos primos 2)3r5r7,11,13,17,1?,23129r31r37
e 41 o dividem, já que 432 : 1 .849 > 1 .789.
7,13: (ENC 98) Uma das afirmativas abaixo sobre núme1os naturais é falsa. Qual é ela?
(A) Dado um número primo, existe r.nrpi. um número primo acima dele.
(B) Se dois"números'não primos São'primos entr.e si, unildeles é,ímpai, , ,
(C) Um númç1o prirno é sç1npre ir-npâï; .. .,:.::,,:, , , , .i .(D) O prpduto de três números naturais,consecutiv:os.é.múltiplol, de,6.
(tr) A soma de três números naturaìs consecutivos é múlliplo de três.
Sor,uçÃo.
A afirmação (C) é falsa já que 2 é primo e é par.
7.t4. Dados a>b€N,mostrequeexisteminfinitosnaturaisntaisque (of n,b*n) :1.
Soi,uçÃo.
Temos que
(a-tn, b *n) : (a-b,b * n).
Escolha um m€ N ial que m ) b e (m,o-b) : l. Tais números mpodem ser escolhidos de
infinitos modos distintos, pois basta escolher m um número primo maior do que b e que não
figure na fatoração de o. 
- 
b.
Assim, pondo Íï : rrL 
- 
b, temos
(a*n,b*n) :(o-b,b+n) :(a-b,m) :1.
m A
^4.
108
â#f#r
É{tddail##r
á
*|ltGIÉrrtëa
â
--
ã
,
t
-a
.n
ã
ã
"
áFF
*t
*:
âtt
d-J*l
+fDlfa
-a
-ta
*t
ê
J.
úa)
!{
ã
rì
7.3 Pequeno Teorema de Fermat
7.11. h1lostre que 421o7 
- 
o. pàra todo número naturai o.
SoruçÃo.
Note que 42:2.3 .7 e que
t7 
- 
o.: (o- 1)a(o* l)(s2 * cf i)(o' 
- 
a*'l).
Como 6:3! divide os três inteiros consecutivos (a- 1Ja[a* i J, ele divide s7 
- 
a. Por outro
lado, pelo Pequeno Teorema de Fermat, 7l{17 
- 
o. Assim, temos que 421t7 
- 
o,.
T.tG. Ache o resto da divisão de l2p-1 porp quando p é primo.
Sor,uçÃo.
Quando (12rp) : I , ou seja, p * 2 e p + 3, temos pelo Pequeno Teorema de Fermat que o
resto da divisão de I2P-r por p é 'l .
Quando P:2 oü p :3, o resto ê zero.
7-17- lüost5e,que, para todo n 
€ 
N, é natural o númeroa-
'; 3 , 2 , 11
;11" *;n'* *n'' tr . ): t. 1Ê'J 5 t5
Soi,uçÃo.
E só notar que
3 * 2 , ll 3íns-nì
Bt '+ 3'n'+ l5r: 
- 
+
e utilizar o Pequeno Teorema de Fermat.
2(n3 
-n)3 +/rL
7.18. Mostre que, para todo n 
€ N, l5l3ns * 5n3 * 7n.
11 KH109
.. ji:I:rr+.ì,1ï:,:liii.tc:ïÊìïryÌj:Té
t?-
I
SoluçÃo.
E só notar que
3ns + 5n3 + 7n 
- 
3(nt 
- 
n) + 5(n3 
- 
n) + l5n
e utilizar o Pequeno Teorema de Fermat.
SoluçÃo.
a) como Slnt-n, d-ïr-n(n-l)(n+l)(ttt*1)e s In,5 Xn-1,5 [n+1, enrão
5ln2 + 1.
b) como 7lÍ{ 
-tï,1a7 -ïÌ-n(n-l)(n2*n*l)(t r+l)e 7 Xn,7 In-1,7 !nu+1, então
7ln2+rr+"l.
SoluçÃo.
Note que se (o,7):1, então (orr7): l, logo pelo pequeno Teorema de Fermat, Z divide(o3)t-l : o18-"l. O resultado generaliza-se como segue: Se (a, 7) : je k e N, então 7la6k_ 1.
SoluçÃo.
Dados três números ïrr ï1 *2 e n* 4, é fácit rnostrar que um deles é divisível por 3. Seguese
que se PrP * 2 
" 
pf 4 são primos, um deles é 3, o que mostra que 3,5 e 7 ê o inieo terno de
primos trigêmeos.
EãA 110
#r
"#r##t
ca
-
-â
-át
{târ
â;thp
ilDt
*a
*aF
+a
-_lpíatl
Jauuuttapnut
-af,pp
+.
+.ülh
7.22" Mcstrequeol2- b12 édivisÍvelpor13,seoebsão:primoscom13. N{ostre '''66*.qüe
é divisíveÌ por g.l, se o e b são primos com g1.
SoluçÃo.
Se (c,13) : (b,13) : i, pelo pequenoTeoremadeFermat, temos que 13lo.j2-1 e
logo 13 divide o"12 
- 
1 
- 
16tz 
- 
l) : o12 
-612.
Como 91 :7.13 e (91,o) : (9-l,b) : I implica (7,o"): (7,b): (.l3, o) : (13,b)
parte anterior, basta mostrar q:ue 7ld2 
-b12. Isso segue do fato de que 7 divide 6-12 
-1pois o12-'1 
- 
(on 
- 
l)(a6 * l) e b12 
- 
I : (b6 
- 
t)(b6 + l).
t3lbi2-I,
: 1, pela
eb12- 1,
Ps"oblemas SuplemeÍItares
743. Se, p 'e q:'são núm.eroq primos p,e)_-5, então 2.+1fz -.,,,r2
SoluçÃo.
Como p ) 5 e q> 5, temos eue (p,31 : (q,3) : l,logo Zlpr-1 e3lq2-1, consequentemente,
3lp'- qt.
Por outro lado p2 
- 
q2 : (p 
- 
q)(p + q) e os possíveis pares de primos p,q são da forma
4k+1r4k'+1;4k* 1,4kt *3 ou 4k+3,4k'+3. Formando os possíveis (p-q)(p+qj, vemos
que estes são sempre divisíveis por 8.
Assim, temos que 241p2 
- 
q2.
Sor,uçÃo.
Todo primo maior do que 3 é da forma 6m -f I ou 6m * 5. Note que um primo da forma3n* I é necessariamente maior do que 3 e não pode ser da forma 6m*5, pois a equação
3n+ I : 6m*5 não possui soluções em N. Logo, um primo da forma 3rr+ I é da forma 6m+ .1.
:fô'ãó ao':aa.rô'ffi :gË{f :È ;rã*u,:amüà':lô.laà.r56,,i,i 
..r1 :. ;
l
I
I
111 AAA
7'25. Nlostre que o único número primo daforma n3+'l ê2 e o único primo daforma n3-l
ê7.
SoluçÃo.
Como n3 + J : (n* l)(n2-n* 1), para que n3* 1 seja primo é necessário que n* I
ou n2 
-n* I : l A única possibilidade é n : l.
Como n3 
- 
I : (ÍL- 1)(n'*nf 1), para que n3 
- 
1 seja primo é necessário q1e n-'l
ou n2 *n* I : l. A única possibilidad,e ê n : 2.
7.26. o único número primo n tal que 3n+ I é um quadracro é 5.
SoluçÃo.
Sejanprimo. Se3n+l:42, então n+2en+ 3 (ésónotarque a2:7 e oz:10é
impossível). Poroutrolado,3n: (c-l)(o+1), logo o-l : J ou a-l 
-3. Como a:211ão
satisfaz a condição e o : 4 a satisfaz, temos que Ír : 5 é o único valor possível.
-t
-1
7.27. Seja k 
€ N, k > 2. Mostre quç
a) Se k dividê or 
- 
l,oz- 1,...,o.- l, então kdivide otoz...o,_ L
b) Se n e N, enlão existe um primo p talqüe k, 16-l)e pl(pk- l)
c) Existem infinitos primos p tais que k ï (p 
- 
f )
aF
Ç
ëFe(tE
Cl:t
tJE
ë
ItE
ë ìrJ,F
ë
ë
ë
aÊq
rÍI<
tE?
ëJÊ
.Ê
F
r:
I'E
ê
JUeT:r
Ë
É
Êee
tf
JE
JÊ
;ljil
,P
.F
JÕ
JÊ
aÕ
Sor,uçÃo.
a) Se or : I * qrk,...r o, : 'l + qrk, temos que
c1 ...a,: (1 * Qik) ...(1 + Q,k) : 1 * qk.
Assim, se klal 
- 
1 para todo i, temos que klal ...o, 
- 
l.
b) Seja dado n e N. Seja nk-1 
- 
pï'-..pf" a decomposição em fatores primos de nk-1.
Urn desses primos p :pj é tal que k X p 
-'1, pois caso contrário se klpr 
-'l para todo i, temmque klpft-1,logo de (a) tlpït ...pï'-1, ou seja, klnk-2, o que implica que kl2, contradi@o.
pois k > 2.
ë
**
KãA 772
I
l
)
t
p
)
c) Para provar a infinidade de primos p tais que p y k- 1, basta mostrar que podemos escolher
rr e m de infinitos modos tais que (nk- 1,mk- l) : l' Vamos mostrar que dado n podemos
escolhermtaisquenk-l eml<-l sejamcoprimos. Defato,como (nk-l,k) :'l,temosque
(nk- i,mk- l) : (nk- 1, (m-n)k) : (nk- l,m- n)'
Tomando m : rL*rk, com (r,nk- l) : 1, temos que
(irk- ì,m1c- l) : (nk- 1'rk) : (nk- 1,r) :1.
Este argumento, juntamente com indução, permite mostrar a existência de uma infinidade de
:
tais números.
7.28. Mostre que existe uma correspondência biunír'oca entre pares de primos gêmeos e números
1tn tais que n'- .1 possui quairo divisores.
Sor,uçÃo.
Dado um par de primos gêmeos (p,q) com q : p +2, tomando ïl : p + 1, temos que
rr2-l : [Tt-1)(n+ l) :pQ, o qual tem quatro divisores.
Inr-ersamente, se * 
-l tem quatro divisores, então ele é da forma p3 ou pq, onde p < q são
ffimeros primos. Mas como # _ l: (n- l)(n+ 1), devemos ter p :ïÌ- 1 e q :n* i' o que
mrm dá nm par de primos gêmeos.
SoluçÃo.
Se n: pït ...pf', consideremos a fatoração de n: ob onde fi e o são um dos fatores que
fguram na lista abaixo:
t,
pït, i:.l,...)r
pr' "'pï", 1 (ir {í2"' (i, (r
113 AAê\
pl'" pï:;", I < )t<iz"'{ j'-, (r
Pï' '''Pï' (: n)
Note que temos o seguinte número de escolhas païa o:
(;). (;) " . (i):'
Mas, paraessas escolhas de s contamos d,uas vezes cada fatoração de n, pois, ao escolhermos
ofator o:pï....pïJ", teremosnecessariamente b :pï" .pï];", queserácontadonovamente
quandotomarmos o:pï' ' 'pï':;'eb:pï" '''pï".
Assim, o número de fatorações de rL em produto de dois números coprimos é metade de 2',
ou seja, 2'-1.
7:30. ,Sgja n:> 2r'Môstre e,enfi-è 6,e Ír'[;éxïStê'pêtO'men9si1,rm número,primo'
':
Sor,uçÃo.
O número n!- I
todo número maior
nl 
-l <nl.
está entre n e n! e é coprimo com cada um dos números'1,2,... rÍ1. Como
do que 2,, to caso n! 
- 
1, tem um fator primo p, devemos ter n < ? <
{1
G
-
e;ë:
i-l:'.:Ë :,ád:ii.:i
SoluçÃo.
a) Se 3lo, temos que 3lo*-o*, logo podemos supor (o,3) : l. Hádois casos aconsiderar:
n:2k e ïTr : 2k', ott n:2k* I e rn 
-- 
2k' * 1.
Caso n :2kem:2kt: Pelo Peciueno Teorema de Fermat, temos que 3l(ak)2-1 e 3l(ak')2-l:
logo 3 divide a diferença desses dois números, que ê (ou)' 
- 
(ot'12 : om 
- 
s'.
Caso n : 2k*l e m :2k'* l: Como 3lo'o 
- 
1 e 3lo2k' 
- 
1, logo 3ls2t+t 
- 
o e 3lo'zk'+t- o €,
portanto, 3 divide a diferença desses dois números, que 6 ozk+1 
- 
Q'2k'+1 
- 
om 
- 
o''
114
t
áãitt
+atF
-#
-+aFÊqt
r-
rr
+;F
,a
ã#lr
E|l
-a
J.{ataF
e-
á
â
{
êii
,Jada
â
J.
â
â
â
â
{
ât
â
e-df
.I
b) Sep>3,temosquepeltêmmesmaparidade, logoap-aédivisÍvelpor3.PeloPequeno
Teorema de Fermat temos que plar 
- 
o 
€, finalmente , 2lú 
- 
a, pois oP e o têm mesma paridade.
Assim, podemos concluir que 6plar 
- 
o.
Agora observe que 6plb(or-a) e 6plo(br-b), logo 6p divide a diferença clesses dois números,
que é, pecisamente, cPb 
- 
bPo.
Ì:gZ. Sejám'orb e N, com'(o,b) + I, e-n € N tal que n* /=p'ê:nrrtnúmeromim'
que o mác de oì b e oz 
-nob f b2 d,eve ser 1 ou p.
iìVl'oStrê
.,.:l :, ',
SoluçÃo.
Note que (o, b) : 1 implica que (a * b, ob) : i.
De fato, se q é um primo tal que qlcb, então {la ou qlb. Se qla, então q Y b e assim,
q I o*b. Seqlb,então q I aeassim, q I s*b. Issomostraque (o*b,ob) :1.
Temos que
(a * b, a2 
- 
ïrb + b2) : (o f b, s2 
-'nb +b2 - (a + b)2)
: (a * b, 
-po.b) : (a * b,P),
Como (a * b,p) é igual a -l ou a p, o resultado segue.
SoluçÃo.
Se (n, rfl) + i, então (*,*) - 2't, onde t é Ímpar. Qrieremos mostrar {tr€ t':"1. De fato,
se t ) 1, escrevendo n : l(n,m) e m 
- 
k(n,m), temos que ot *b* : tr- +vt, onde u : s12' a
v : bP', logo
a* + b* : rrt *vt : (u* v)(ut-l - v',Í-2+ . . . +vt-l ),
com I <u*v < ut*vt: o,**b*, Iogo o*+b* não seria primo.
;i:ìì :J!-
115 anã
Sor,uçÃo.
Note que dada a simetria dessas expressões em b e c, dado um número primo p, pode-se
supor, sem perda de generalidade, que Eo(b) ç Eo(c). Portanto, há três possibilidades a serem
consideradas.
i) Eo(a) < Ep(b) ç Eo(c)
ii) Ep(b) < Eo(c) ç Eo(c)
ii) Ep(b) ç Er(c) ç Er(a)
a) Vamos analisar os três casos acima.
i) Eo(c, [b, c]) : min{Ep(a), Ep(ib, cl)} : min{Ep(c), max{Eoiu)' Eo(c)}} : Ep(o)'
Por outro lado,
Eo([(a,b), (o, c)]) : max{Eo((o,b)), Eo((4, c)) : Eo(o)
ii) Eo(c, [b, c]) : min{Ep(o), Eo([b, c])] : mìn{Eo(o), max{Ep(b), Ep(c)}}: Eo(n).
Por outro lado
Eo([(a, b), (s, c)]) : max{Eo((a,b)), Eo((o, c)) : Eo(ct)
iii) Ep(a, [b, c]) : min{Er(a), Ee([b, c])] : min{Eo(o), max{Eo(b), Eo(c)}} : Ep(c).
Por outro lado,
Eo([(o, b), (s, c)]) : max{Eo((o, b)), Eo((o, c)) : eo(c)
b) Segue de uma análise semelhante.
7.35. Generalize o exercÍcio anterior, mostrando que se r )- 3, então
a) (ar, [az; o3r.';., o,]) 
=,[.(aì.,,o2)rr(,Qri'Qs)i;.,.:, 
(ori o')1;
b) lor, (oz, ct3r..., o,)] : ([or, oz], [ar, or],...,14r, o'J).
SoluçÃo.
Vamos provar por indução sobre r a validade de ambas as fórmulas simultaneameúe- O caso
r :3 foi provado no probÌema anterior. Vamos supor que ambas as fórmulas sejam válidas para
reprová-lasparar*.l.
a) Temos, pelo Problema 5.32 e pela hipótese de indução, que
(ar, [o2,... r Grr or+r]) : (or, [[o2,..., o']r o'+r])
: [(or, [o2,...,0.]), (or, a,*r)]
: [[(0r, oz),..., (cr, c,)], (or, ar+r)]
: [(or, cz), . . . , (or, o..), (or, or+r )].
A prova de (b) é análoga.
EDA 116
fr+ït
<f,-r\f,r{I
-nïrfÉrtç;ft
+ï
rrt
r{l
âh)rr
âhãf
d-
â
*a
.Õ7
:-
:-77ru2{af,
-Ja
-Òu
1*t
ü5J.J|tb
Problemas Propostos
7. Mostre que todo número da forma 6m * 5 admite pelo menos um fator primo dessa mesilra
forma.
2. Seja a e N. Mostre que existem infinitos números naturais n tais que [n* o, n- a] : r12 
- 
s2.
3. Mostre que nenhrim número da forma 2an+2 a '1, onde n € N, pode ser primo.
4. Determineumnúmeronaturalntalque ] éumquaclraclo, ] éumcuboe $ éumapotência
quinta.
5" Se a, b, c, d 
€ 
N, mostre que
(ab,cd) :(o,c)(b,d) (#,#) (#,#)
€. Mostre que para todo n 
€ 
N tem-se 120lns 
- 
5n3 * 4n.
7. Mostre que tns * Jrr3 + *n é um inteiro para todo inteiro n.
8. Mostre que
u) o1'-b16 é divisível por 17 para todos a e b inteiros primos comlT;
b) ot' 
- 
b16 é divisível por 85 para todos a e b inteiros primos com g5.
9. Ache os números primos p tais que
z) pl2o + 1; b) plzp + 3; c) pl3v * 2; d) pl3r + Z.
10- Sejap *2,5 um número primo. Mostre que p divide infinitos números daforma .l,l...-1.
C;onclua que p divide infinitos números da forma oa.. . c, onde e é um aigarismo de I a 9.
Sugestão. Tem-se que 'lOn(P-l) : I mod p, logo p divide infinitos números da forma
7L7 AEH