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 8 de 23

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. Por