A maior rede de estudos do Brasil

Grátis
132 pág.
Problemas em Teoria dos Números (Resolvidos e Propostos) do prof Diego Marques

Pré-visualização | Página 9 de 23

outro 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)