exercicios-teonumeros.2003

Prévia do material em texto

Exercı´cios de Teoria dos Nu´meros
Licenciatura em Matema´tica
Vı´tor Arau´jo
2003
1 Divisibilidade e con-
grueˆncia
1. Encontrar, usando o algoritmo de Eucli-
des, o ma´ximo divisor comum dos seguin-
tes pares de nu´meros:
(a) 542 e 234;
(b) 9652 e 252;
(c) 24573 e 1387;
(d) 4276 e 1234;
(e) 48762 e 176;
(f) 42516 e 97421;
(g) 8374 e 24517;
(h) 35262 e 12753.
2. Ache o mı´nimo mu´ltiplo comum dos se-
guintes pares de nu´meros:
(a) 44 e 32;
(b) 234 e 12;
(c) 35 e 24;
(d) 142 e 742;
(e) 17 e 141;
(f) 42 e 52;
(g) 501 e 2141;
(h) 144 e 64.
3. Deˆ exemplo de uma sequeˆncia de pelo me-
nos 30 inteiros consecutivos e compostos.
4. Mostrar, por induc¸a˜o, que
(a) 12+22+32+· · ·+n2 = n(n+1)(2n+1)6 ;
(b) 1+3+5+ · · ·+(2n−1) = n2;
(c) 1 · 2+ 2 · 3+ 3 · 4+ · · ·+ n(n+ 1) =
n(n+1)(n+2)
3 ;
(d) n! > 2n,∀n ≥ 4;
(e) n2 > 2n+1,∀n ≥ 3;
(f) 9 | (10n+1−9n−10),∀n ≥ 1.
5. Mostre que o produto de 3 inteiros conse-
cutivos e´ divisı´vel por 6.
6. Mostre que, para todo o n ∈ N, 32n+1 +
2n+2 e´ mu´ltiplo de 7, e que 32n+2 +26n+1
e´ mu´ltiplo de 11.
7. Encontre inteiros x e y tais que
(a) 93x+81y = 3;
(b) 43x+128y = 1.
8. Mostre que se a,b sa˜o inteiros positivos
com (a,b) = [a,b], enta˜o a = b.
9. Mostre que n5− n e´ divisı´vel por 30 para
todo o inteiro n ∈ N.
10. Mostre que a equac¸a˜o x3+7x+17= 0 na˜o
admite qualquer soluc¸a˜o inteira.
1
1 DIVISIBILIDADE E CONGRUEˆNCIA 2
11. Mostre que 2n + 1 nunca e´ um cubo, para
todo o n ∈ N.
12. Pode o nu´mero 11111 . . .1111 formado
por trezentos 1′s ser um quadrado?
13. Sejam F1 = 1,F2 = 1 e Fn = Fn−1 +
Fn−2,n ≥ 3 (Fn e´ o n-e´simo nu´mero de Fi-
bonacci). Mostre que para todo o n ∈ N
(a) F1 +F3 +F5 + · · ·+F2n−1 = F2n;
(b) F2 +F4 +F6 + · · ·+F2n = F2n+1−1;
(c) F1 +F2 +F3 + · · ·+Fn = Fn+2−1;
(d) F1F2 + F2F3 + F3F4 + · · · +
F2nF2n+1 = F22n+1−1.
14. Mostrar que os nu´meros de Fibonacci sa-
tisfazem:
(a) (Fn,Fn+1) = 1;
(b) (Fn,Fn+3) = 1 ou 2.
15. Mostre que, ale´m de 2 = 13 + 1, nenhum
nu´mero da forma n3 +1 e´ primo.
16. Usando a sucessa˜o Rn = n!+1 demonstre
a infinitude da sequeˆncia dos primos.
17. Mostre que qualquer inteiro maior do que
11 e´ soma de dois inteiros compostos.
18. Mostre que 3 e´ o u´nico primo p tal que
p, p+2 e p+4 sa˜o todos primos.
19. Determine a soma de todos os nu´meros
formados pelas permutac¸o˜es dos dı´gitos
1,2,3,4,5, isto e´, 12345+ · · ·+54321.
20. Mostre que na˜o existe n tal que 7 | (4n2 +
3).
21. Sabendo que o resto da divisa˜o de um in-
teiro b por 7 e´ 5, calcular o resto da divisa˜o
por 7 dos nu´meros seguintes:
(a) −b;
(b) 2b;
(c) 3b+7;
(d) 10b+1;
(e) b2 +b+1.
22. Seja un = 111 . . .11 formado por n alga-
rismos 1 consecutivos. Mostre que se un e´
primo, enta˜o n e´ primo.
23. Mostre que se, para algum n, m | (35n+
26), m | (7n+3) e m > 1, enta˜o m = 11.
24. Sendo 1/a+ 1/b um inteiro, em que a,b
sa˜o inteiros positivos, mostre que a = b.
Mostre ainda que a = 1 ou 2.
25. Mostre que se (a,b) = 1, enta˜o (2a +
b,a+2b) = 1 ou 3.
26. Mostre que, se n e´ um inteiro, enta˜o o
nu´mero n(n + 1)(n + 2)(n + 3) + 1 e´ um
quadrado.
27. Determine todos os nu´meros de treˆs alga-
rismos divisı´veis por 8,11 e 12.
28. Ache todos os inteiros positivos n para os
quais (n+1) | (n2 +1).
29. Dados a,b inteiros com b 6= 0, mostre que
existem inteiros q,r que satisfazem a =
qb± r, 0 ≤ r ≤ b/2.
30. Mostrar que se a,b sa˜o inteiros, (a,3) =
(b,3) = 1, enta˜o a2 + b2 na˜o e´ um qua-
drado perfeito.
31. Mostrar que para n > 1 os nu´meros n4 +4
e n4 +n2 +1 sa˜o ambos compostos.
32. Mostre que (a,bc) = 1 se, e so´ se, (a,b) =
1 e (a,c) = 1.
33. Mostre que se b | c enta˜o (a + c,b) =
(a,b).
1 DIVISIBILIDADE E CONGRUEˆNCIA 3
34. Mostre que se (a,c) = 1 enta˜o (a,bc) =
(a,b).
35. Mostre que (a,b,c) = ((a,b),c).
36. Diga qual e´ o maior inteiro que se pode so-
mar ao dividendo sem alterar o quociente
entre 431 e 37.
37. Para cada par de inteiros abaixo, encontre
o quociente q e o resto r que satisfazem o
algoritmo de divisa˜o de Euclides.
(a) a = 59,b = 6;
(b) a =−71,b = 5;
(c) a =−48,b =−7;
(d) a = 67,b =−13.
38. Mostre que se n,m forem inteiros ı´mpares,
enta˜o 8 | (n4 +m4−2).
39. Encontrar o menor inteiro positivo da
forma 36x+54y, em que x,y sa˜o inteiros.
40. Exprimir o nu´mero 274 nas bases 2,5,7 e
9.
41. Transforme para a base 10 os seguintes
nu´meros:
(a) (2351)7;
(b) (1001110)2;
(c) (7706)8;
(d) (11122)4.
42. Mostrar que se 2n + 1 e´ um primo ı´mpar,
enta˜o n e´ poteˆncia de 2.
43. Provar que se (a,b) = d, enta˜o d
e´ o nu´mero de inteiros na sequeˆncia
a,2a,3a, . . . ,ba que sa˜o divisı´veis por b.
1.1 Congrueˆncia
44. Mostre que 47 | (223 +1).
45. Determine o resto da divisa˜o de 734 por 51
e de 563 por 29.
46. Mostre que se q e´ ı´mpar e a2 + 2b2 = 2q,
enta˜o a e´ par e b e´ ı´mpar.
47. Provar que se p e´ primo enta˜o (p− 1)! ≡
p−1(mod 1+2+3+ · · ·+(p−1)).
48. Ache o ma´ximo divisor comum de (p−
1)!−1 e p!, com p primo.
49. Mostrar que para n ≥ 4 o resto da divisa˜o
por 12 de 1!+ 2!+ 3!+ · · ·+ n! e´ igual a
9.
50. Mostre que para n inteiro 3n2−1 nunca e´
um quadrado.
51. Resolva as seguintes congrueˆncias:
(a) 5x ≡ 3(mod 24);
(b) 3x ≡ 1(mod 10);
(c) 23x ≡ 7(mod 19);
(d) 7x ≡ 5(mod 18);
(e) 25x ≡ 15(mod 120).
52. Mostre que 5n3 + 7n5 ≡ 0(mod12) para
todo o inteiro n.
53. Seja f (x) = anxn + · · · + a1x + a0 po-
lino´mio com coeficientes inteiros em que
an > 0 e n ≥ 1. Mostre que f (x) e´ com-
posto para uma infinidade de valores in-
teiros x.
54. Mostre que se p1, p2 sa˜o primos com p2 =
p1 + 2 e p1 > 3, enta˜o p1 + p2 ≡ 0(mod
12).
2 FUNC¸O˜ES ARITME´TICAS 4
55. Mostre que para a,b inteiros vale 3 | (a2+
b2) =⇒ 3 | a e 3 | b.
56. Sejam p1, p2, p3 primos tais que p = p21 +
p22 + p
2
3 e´ primo. Mostre que um dos
p1, p2, p3 e´ igual a 3.
57. Mostre que p | (pnk ) em que 0 < k < pn.
58. Mostre que 310 ≡ 1(mod 112).
59. Resolva os seguintes sistemas:
(a)

x ≡ 1(mod 2)
x ≡ 2(mod 3)
x ≡ 5(mod 7)
(b)

2x ≡ 1(mod 5)
3x ≡ 2(mod 7)
5x ≡ 7(mod 11)
(c)

x ≡ 7(mod 11)
3x ≡ 5(mod 13)
7x ≡ 4(mod 5)
60. Encontre todas as soluc¸o˜es das seguintes
congueˆncias lineares:
(a) 5x ≡ 3(mod 7);
(b) 13x ≡ 14(mod 29);
(c) 15x ≡ 9(mod 25);
(d) 37x ≡ 16(mod 19);
(e) 5x ≡ 20(mod 15).
61. Mostre que a7 ≡ a(mod21) para todo o
inteiro a.
62. Mostre que para a,b inteiros com (a,b) =
1 temos aφ(b)+bφ(a) ≡ 1(mod ab).
63. Prove ou deˆ um contra-exemplo: se a e
m sa˜o inteiros com (a,m) = 1, enta˜o m |
(1+a+a2 + · · ·+aφ(m)−1).
64. Mostre que se p,q sa˜o primos, p ≥ q ≥ 5,
enta˜o p2−q2 ≡ 0(mod 24).
65. Encontre um sistema completo de
resı´duos mo´dulo 11 formado apenas por
mu´ltiplos de 6.
66. Encontre um sistema completo de
resı´duos mo´dulo 7 formado apenas por
nu´meros primos.
67. Dado um primo p e´ sempre possı´vel en-
contrar um sistema completo de resı´duos
mo´dulo p formado so´ por primos? Justifi-
que.
68. Prove que para todo o inteiro n 6= 4 se tem
(n−1)! ≡ 0(mod n).
2 Func¸o˜es aritme´ticas
69. Determine τ(n),σ(n) e φ(n) para os se-
guintes valores de n:
(a) 10;
(b) 35;
(c) 200;
(d) 512;
(e) 10000;
(f) 1234.
70. Diga quais os valores de n para os quais
φ(n) e´ ı´mpar.
71. Diga quais os valores de n para os quais
φ(n) | m.
72. Mostre que se m,n sa˜o inteiros positivos e
m | n, enta˜o φ(m) | φ(n).
73. Mostre que φ(n) e´ par se m > 2.
74. Mostre que existe uma infinidade de intei-
ros m tais que φ(m) e´ um quadrado per-
feito.
3 RESI´DUOS QUADRA´TICOS 5
75. Mostre que se f e´ func¸a˜o multiplicativa,
enta˜o f (1) = 1.
76. Mostre que ∏3i=0 µ(n + i) = 0 para qual-
quer inteiro positivo n.
77. Mostre que um inteiro positivo p e´ primo
se, e so´ se, σ(p) = p+1.
78. Ja´ sabemos que as func¸o˜esτ e σ sa˜o mul-
tiplicativas. Mostre que nenhuma delas e´
completamente multiplicativa.
79. Mostre que para um inteiro fixado r a
func¸a˜o h(n) = nr e´ completamente multi-
plicativa.
80. Mostre que as func¸o˜es F(n) = f (n)g(n) e
G(n) = f (n)/g(n) sa˜o multiplicativas se f
e g o forem com g(n) 6= 0 para todo o n.
81. Deˆ um exemplo que mostre que a func¸a˜o
F(n) = ∑d|n f (d) nem sempre e´ completa-
mente multiplicativa mesmo que f o seja.
82. Mostre que para qualquer inteiro n > 1
existe uma infinidade de inteiros m tais
que τ(m) = n.
83. Ache os menores inteiros positivos m,n
para os quais σ(m) = 6 e φ(n) = 6..
84. Mostre que ∏d|n d = nτ(n)/2.
85. Mostre que se f e´ multiplicativa, m | n e
(m,n) = 1, enta˜o f (n/m) = f (n)/ f (m).
86. Seja h(n) o nu´mero de factores primos
distintos de n — por exemplo, h(15) =
h(21) = 2 e h(30) = 3. Seja f (n) = ah(n)
em que a esta´ fixado. Mostre que f (n)
e´ multiplicativa mas na˜o e´ completamente
multiplicativa.
87. Mostre que existe uma infinidade de intei-
ros m para os quais 10 | φ(m). (Sugesta˜o:
φ(11) = 10.)
88. Mostre que
φ(2n) =
{ φ(n) se n e´ ı´mpar
2φ(n) se n e´ par
para qualquer inteiro n.
89. Mostre que todo o inteiro positivo pode
ser escrito como soma de nu´mero de Fi-
bonacci distintos e na˜o consecutivos.
3 Resı´duos quadra´ticos
90. Calcule
(48
97
)
,
(235
991
)
,
(138
883
)
.
91. Determine os resı´duos quadra´ticos e na˜o
quadra´ticos de 19 e 23.
92. Mostre que na˜o existe n tal que 7 | (4n2−
3).
93. Mostre que se p,q sa˜o primos distintos
com p = q+4a e a inteiro positivo, enta˜o
(a) (pq)= (aq);
(b) (ap)= (aq).
94. Mostre que se p e´ primo ı´mpar enta˜o(
3
p
)
=
{
1 se p ≡±1(mod 12)
−1 se p ≡±5(mod 12) .
95. Fornec¸a uma congrueˆncia que descreva to-
dos os primos para os quais 5 e´ um resı´duo
quadra´tico.
96. Mostre que 17 e´ um resı´duo quadra´tico
mo´dulo 19. (Sugesta˜o: Lema de Gauss.)
97. Averigue se a congrueˆncia 3x2 ≡ 12(mod
13) admite soluc¸a˜o.
98. Determine
[327
635
]
,
[429
563
]
,
[181
991
]
.
99. Se p,q forem primos ı´mpares distintos
com p ≡ q ≡ 3(mod4), mostre que p e´
resı´duo quadra´tico mo´dulo q se, e so´ se,
q na˜o e´ resı´duo quadra´tico mo´dulo p.
5 INTEIROS COMO SOMA DE QUADRADOS 6
4 Raı´zes primitivas
100. Determine uma raiz primitiva mo´dulo
(a) 5;
(b) 6;
(c) 10;
(d) 11;
(e) 18;
(f) 19.
101. Determine o nu´mero de raı´zes primitivas
de
(a) 5;
(b) 11;
(c) 13;
(d) 17;
(e) 23;
(f) 31.
102. Mostre que se m e´ inteiro positivo e a um
inteiro com (a,m) = 1 e ordm(a) = m−1,
enta˜o m e´ primo.
103. Mostre que os divisores primos ı´mpares de
um inteiro da forma n2 + 1 sa˜o da forma
4k+1.
104. Se p > 2 e´ primo e a > 1 e´ inteiro, mostre
que os divisores primos ı´mpares de ap +
1 sa˜o divisores de a+ 1 ou sa˜o da forma
2np+1.
105. Mostre qye se a e´ uma raiz primitiva
mo´dulo p (primo) com p ≡ 1 (mod 4),
enta˜o −a tambe´m e´ raiz primitiva.
106. Mostre que se a e´ resı´duo quadra´tico
mo´dulo p primo ı´mpar, enta˜o a na˜o e´ raiz
primitiva mo´dulo p.
5 Inteiros como soma de
quadrados
107. Averigue quais dentre os pri-
mos 11,17,19,23,29,31 admitem
representac¸a˜o como soma de dois qua-
drados e fornec¸a a representac¸a˜o caso
exista.
108. Resolva as seguinte equac¸o˜es usando ape-
nas inteiros
(a) x2 + y2 = 146;
(b) x2 + y2 = 625.
109. Averigue se existe um triaˆngulo
rectaˆngulo iso´sceles de lados inteiros.
110. Mostre que se o primo p e´ tal que p ≡ 3
(mod 4) enta˜o a equac¸a˜o p2 = a2 + b2
possui soluc¸a˜o inteira. Mostre ainda que
a = 0 ou b = 0.
111. Determine um inteiro n e racionais na˜o in-
teiros r,s tais que n = r2 + s2.
112. Mostre que todo o quadrado perfeito pode
ser representado como soma de quadrados
de racionais na˜o inteiros r e s.
6 Fracc¸o˜es contı´nuas
113. Determine o nu´mero racional represen-
tado na forma de fracc¸a˜o contı´nua em cada
caso abaixo
(a) [3,1];
(b) [1,1,1];
(c) [0,6,5];
(d) [1,2,3,4];
(e) [2,2,2];
7 PARTIC¸O˜ES 7
(f) [3,6,1,7];
(g) [3,7,15,1];
(h) [2,3,2,1,2].
114. A representac¸a˜o na forma de fracc¸a˜o
contı´nua simples infinita (na˜o perio´dica)
do nu´mero e comec¸a assim
e = [2,1,2,1,1,4,1,1,6,1,1,8, . . . ].
Calcule os 6 primeiros convergentes desta
fracc¸a˜o contı´nua.
115. Determine o irracional representado pela
fracc¸a˜o contı´nua [1,1,1,1, . . . ].
116. Expresse os seguinte racionais na forma
de fracc¸a˜o contı´nua
(a) 11/7;
(b) −51/23;
(c) 114/235;
(d) 34/21.
117. Mostre que se pn/qn = [a1,a2, . . . ,an],
enta˜o qn/qn−1 = [an,an−1, . . . ,a3,a2].
118. Suponha que r > s > 0, (r,s) = 1 e que
r/s = [a1,a2, . . . ,an]. Mostre que se pn |
(q2n +(−1)n) enta˜o ai = an−i para 1 ≤ i <
n, isto e´, [a1,a2, . . . ,an] e´ sime´trica.
7 Partic¸o˜es
119. Determine a func¸a˜o gerador ordina´ria para
cada uma das sucesso˜es seguintes
(a) (1,1,1,0,0,0, . . .);
(b) (1,0,0,2,3,0,0,0, . . .);
(c) (1,1,1,3,1,1, . . .);
(d) (0,0,1,1,1, . . .);
(e) (0,1,0,1,0,1, . . .);
(f) (0,4,0,4,0,4, . . .);
(g) (1,−1,1,−1,1,−1, . . .);
(h) (1,−1,1/2!,−1/3!,1/4!,−1/5!, . . .);
(i) (ak) =
(2k
k!
)
.
120. Determine a sucessa˜o gerada por cada
func¸a˜o
(a) (x+1)4;
(b) x2(1−3x)−1;
(c) x+ ex;
(d) 1+(1− x2)−1;
(e) e2x + x+ x2;
(f) x2ex.
121. Quantas soluc¸o˜es tem a equac¸a˜o x1 +x2 +
· · ·+ xn = r se cada varia´vel e´ igual a 0 ou
1?
122. Determinar func¸o˜es geradoras ordina´rias
que permitam calcular o nu´mero de ma-
neiras de distribuir 11 laranjas e 6 peˆras
para 3 crianc¸as de tal forma que cada
crianc¸a receba pelo menos 3 laranjas e no
ma´ximo 2 peˆras.
123. Encontre a func¸a˜o geradora ordina´ria que
permita responder ao seguinte: de quantas
maneiras podemos distribuir 300 cadeiras
ideˆnticas em 4 salas de tal forma que o
nu´mero de cadeiras em cada sala seja 20,
ou 40, ou 80, ou 100?
124. Determine a func¸a˜o geradora ordina´ria
para o nu´mero de partic¸o˜es de n em que
todas as partes sa˜o ı´mpares e nenhuma su-
pera 7.
125. Deˆ interpretac¸a˜o em termos de partic¸o˜es
para
7 PARTIC¸O˜ES 8
(a) O coeficiente de x12 na expansa˜o
de (1+ x2 + x4 + · · ·+ x12)(1+ x4 +
x8 + x12)(1 + x6 + x12)(1 + x8)(1 +
x10)(1+ x12);
(b) O coeficiente de x12 na expansa˜o de
(1+x9)(1+x3+x6+x9+x12+x15).
126. Calcule os coeficientes das expresso˜es na
alı´nea anterior.
127. Escreva a func¸a˜o gerador que pode ser
usada para encontrar
(a) o nu´mero de partic¸o˜es de 34 com
partes restritas a 6, 8, 10 e 20;
(b) o nu´mero de partic¸o˜es de 13 com
partes maiores que 3;
(c) o nu´mero de partic¸o˜es de 11 com
partes ı´mpares distintas.
128. Mostre que para todo o m par e maior que
6 o nu´mero de partic¸o˜es de m em par-
tes ı´mpares e´ maior do que o nu´mero de
partic¸o˜es de m em partes pares.