1
exercícios de teoria de números
1. Usando os axiomas mostre que:
(a) a
(b + c) = a
2
b+a
c
a
b + b2
2
(b) (a + b) = a + 2
(c) a + (b + c) = (c + a) + b
(d) (b
a) + (c
b) + (a
c) = 0
2. Use os axiomas para mostrar que:
(a) ( 1)
(b)
(a
(c) ( a)
(d)
a=
b) = a
a
( b)
( b) = a
b
(a + b) = ( a) + ( b)
3. Use os axiomas para mostrar que a
b = 0 =) a = 0 _ b = 0:
4. Mostre que, se a, b e c são inteiros, com a > b e b > c, então a > c.
5. Determine os valores de:
(a)
3
4
1
4
22
(c)
7
(d) [ 2]
(b)
(e) [3]
(f) [
]
6. Qual o valor de [x] + [ x], para qualquer número real x?
7. Mostre que [x] + [x + 1=2] = [2x].
8. Mostre que [x + y]
[x] + [y].
9. Use indução matemática para mostrar que, sempre que n é um inteiro positivo, se
tem n < 2n .
10. Encontre uma fórmula que permita calcular a soma dos primeiros n números pares e
demonstre a sua validade usando indução.
11. Encontre uma fórmula que permita calcular An com A =
1 1
, para qualquer n
0 1
inteiro positivo e demonstre a sua validade usando indução.
12. Os números de Fibonacci de…nem-se recursivamente por
f1 = f2 = 1; fn = fn
1
+ fn 2 ; para n
Encontre uma expressão que permita calcular
n
P
k=1
indução.
3:
fk e mostre a sua validade usando
2
exercícios de teoria de números
13. Use o segundo princípio de indução matemática para mostrar
p que qualquer número
1+ 5
de Fibonacci, para n 3, satisfaz fn > n 2 , com =
.
2
p
p
n
n
1
5
1+ 5
14. Se for =
e =
, mostre que fn = p
, para n 2 Z + .
2
2
5
15. Mostre que fn
n 1
, para n
2.
16. Encontre uma fórmula para calcular
n
Q
2k .
k=1
17. Mostre que
n
P
( 1)k
1
k 2 = ( 1)n
1
k=1
n (n + 1)
.
2
18. Mostre que: 3j99; 5j145; 7j343; 888j0.
19. Mostre que 1001 é divisível por 7, por 11 e por 13.
20. Dos seguintes inteiros quais são divisíveis por 22: 0; 144; 1716; 192544;
195518 ?
285714;
21. Mostre que se a e b são inteiros tais que ajb, então ak jbk , para qualquer inteiro positivo
k.
22. Mostre que se m e n > 0 são inteiros, então:
8 hmi
<
se m =
6 kn 1 para qualquer inteiro k
m+1
ni
hm
=
:
n
+ 1 se m = kn 1 para algum inteiro k
n
23. Demostre que a soma dos cubos de 3 inteiros consecutivos é divisível por 9, usando
indução e sem usar indução.
24. Demostre que n5 n é divisível por 5, para qualquer inteiro positivo n, usando indução
e sem usar indução.
h
p ni
25. Mostre que , sempre que n é um inteiro não negativo, 2 + 3
é impar.
26. Converta (ABCDEF )16 , (DEF ACED)16 e (9A0B)16 para binário.
27. A representação de inteiros em computador é feita usando grupos de k bits para cada
inteiro. O bit mais à esquerda representa o sinal, 0 para positivo e 1 para negativo.
A seguir aparece o valor absoluto do número, se este for positivo, ou o complementar
de cada bit se for negativo (O complementar de 0 é 1 e de 1 é 0). Por exemplo, para
um computador que trabalhe com sequências de 6 bits, 8 representa-se por 0011000
e 8 por 110111.
(a) Encontre a representação, usando sequências de 6 bits, dos seguintes inteiros:
22; 31; 7; 19.
(b) Que inteiros são representados, em sequências de 5 bits, por: 11001; 01101;
10001; 11111?
3
exercícios de teoria de números
28. Efectue as seguintes operações:
(a) (101111011)2 + (1100111011)2
(b) (11111101011111)2
(c) (11101)2
(10001000111101)2
(110001)2
29. Encontre o quociente e o resto quando (110011111)2 é dividido por (1101)2 .
30. Uma dúzia são 12 unidades e uma grosa são 12 dúzias. Usando aritmética de base
12, resolva os problemas:
(a) Se 3 grosas, 7 dúzias e 4 ovos são retirados de uma prateleira onde há 11 grosas
e 3 dúzias de ovos, quantos lá …cam?
(b) Se 11 grosas, 10 dúzias e 6 ovos tiverem que ser divididos em três partes iguais,
quantos ovos há em cada lote?
31. Mostre que um inteiro positivo n na base b tem [logb n] + 1 algarismos.
32. Determine quais dos seguintes inteiros são primos: 101; 103; 107; 111; 113; 121; 201;
203; 207; 211; 213; 221.
33. Use o crivo de Erastótenes para encontrar todos os primos inferiores a 200.
34. Encontre todos os primos que sejam a diferença da quarta potência de dois inteiros
consecutivos.
35. Mostre que não há nenhum primo da forma n3 + 1 à excepção de 2.
36. Mostre que se a e n são inteiros positivos e an
1 é primo, então n é primo e a = 2.
37. Seja n um inteiro maior do que 1. Seja p o menor factor primo de n. Mostre que, se
p
n
p > 3 n, então ou é primo ou é 1.
p
38. Mostre que os únicos 3 primos da forma p, p + 2, p + 4 são 3, 5 e 7.
39. Veri…que a conjectura de Goldbach para os seguintes valores de n: 50; 98; 102; 144;
200; 222.
40. Goldbach também conjecturou que qualquer inteiro impar maior do que 5 é a soma
de 3 números primos. Veri…que-o para os seguintes valores de n: 7; 17; 27; 97; 101;
199.
41. É possível mostrar que:
p
(n) = ( ( n) 1) + n
+
n
n
+
+
p1 p2
p2 p3
n
n
+
+
p1
p2
+
n
n
+
+
p1 p2 p3
p1 p2 p4
+
n
pr
+
n
pr 1 pr
+
n
pr 2 pr 1 pr
+
p
p
com p1 , p2 , ..., pr primos menores ou iguais a ne ( n) = r. Use esta expressão
para calcular (200) e compare com o resultado obtido no exercício 33.
4
exercícios de teoria de números
42. Encontre o máximo divisor comum dos seguintes pares de números: 15 e 35; 0 e 111;
12 e 18; 99 e 100; 11 e 121; 100 e 102; 90 e 100; 27 e 45.
43. Seja a um inteiro positivo. Qual o máximo divisor comum de a e 2a?
44. Seja a um inteiro positivo. Qual o máximo divisor comum de a e 2 + a?
45. Seja a um inteiro positivo. Qual o máximo divisor comum de a e 1 + a?
46. Desenvolva em fracção contínua o número
105
38
47. Mostre que, sendo f (x) = an xn + an 1 xn 1 + ::: + a1 x + a0 , então há um inteiro y tal
que f (y) não é primo. Sugestão: Supor f (x) = p primo, para qualquer x e concluir
que pjf (x + kp) para qualquer k inteiro. Tome em consideração que um polinómio
de grau n toma cada valor no máximo n vezes.
48. Seja n um inteiro maior do que 3 e seja p um primo tal que
p não divide
2n
n
2n
< p < n. Mostre que
3
.
49. Determine mdc(a2 + b2 ; a + b), sendo a e b primos entre si.
50. Mostre que, se a e b são inteiros não simultaneamente nulos e se c não é nulo, então
mdc(ca; cb) = jcjmdc(a; b).
51. Encontre um conjunto de três inteiros primos entre si que não sejam primos dois a
dois.
52. Encontre o máximo divisor comum de cada um dos conjuntos: f8; 10; 12g; f5; 25; 75g;
f99; 9999; 0g; f6; 15; 21g; f 7; 28; 35g; f0; 0; 1001g.
53. Mostre que, se k é inteiro, então 6k
dois a dois.
1, 6k + 1, 6k + 3, 6k + 5 são primos entre si
54. Mostre que todo o inteiro maior do que 6 é uma soma de dois números primos entre
si maiores do que 1.
55. Mostre que, se a, b, c e d são inteiros tais que b e d são positivos e mdc(a; b) =
a c
mdc(c; d) = 1 e + é inteiro, então b = d.
b d
56. Use o algoritmo de Euclides para determinar o máximo divisor comum de: 45 e 75;
102 e 222; 666 e 1414; 20785 e 44350.
57. Expresse o máximo divisor comum de cada par de inteiros do exercício anterior como
combinação linear desses inteiros.
58. Encontre o máximo divisor comum de: 15, 35 e 90; 300, 2160 e 5040; 1240, 6660,
15540 e 19980.
59. Expresse o máximo divisor comum de cada grupo de inteiros do exercício anterior
como combinação linear desses números.
60. Encontre a factorização em factores primos de 4849845.
61. Quais os inteiros positivos que têm exactamente 3 divisores? E 4 divisores?
5
exercícios de teoria de números
62. Mostre que se a e b são inteiros positivos e a3 jb2 , então ajb.
63. Se pa divide n e pa+1 não divide n, diz-se que pa divide exactamente n e escreve-se
pa jjn. Mostre que, se pa jjm e pb jjn, então pa+b jjmn.
64. Mostre que se a e b são inteiros positivos então mdc(a; b)jmmc(a; b). Quando é que
mdc(a; b) = mmc(a; b)?
65. Resolva, se possível as seguintes equações diofantinas lineares
(a) 17x + 13y = 100
(b) 21x + 14y = 147
(c) 60x + 18y = 97
66. Um merceeiro compra maçãs e laranjas e gasta 839 unidades monetárias. Se cada
maçã custa 25 u.m. e cada laranja 18 u.m., quantas peças de fruta ele compra?
67. Um merceeiro compra maçãs e laranjas e gasta 549 unidades monetárias. Se cada
maçã custa 33 u.m.n e cada laranja 18 u.m., qual o número mínimo de peças de fruta
que ele compra? E o máximo?
68. Construa a tabuada de adição módulo 6.
69. Construa a tabuada de multiplicação módulo 6.
70. Qual a hora marcada por um relógio
(a) 29 horas depois das 11?
(b) 100 horas depois das 2?
(c) 50 horas depois das 6?
(d) 549 horas depois das 10?
8
x
>
>
<
x
71. Resolva o sistema de congruências
x
>
>
:
x
8
x
>
>
<
x
72. Resolva o sistema de congruências
x
>
>
:
x
2(mod 5)
1(mod 3)
2(mod 4)
2(mod 7)
0(mod 2)
0(mod 3)
1(mod 5)
6(mod 7)
73. Determine a maior potência de 2 que divide cada um dos inteiros positivos seguintes:
201984; 1423408; 89375744; 41578912246.
74. Determine a maior potência de 5 que divide cada um dos inteiros positivos seguintes:
112250; 4860625; 235555790; 48126953125.
75. Quais dos seguintes inteiros são divisíveis por 3? Desses quais os que são divisíveis
por 9?
(a) 18381
(b) 65412351
(c) 987654321
(d) 78918239735
6
exercícios de teoria de números
76. Quais dos seguintes inteiros são divisíveis por 11?
(a) 10763732
(b) 1086320015
(c) 674310976375
(d) 8924310064537
77. Encontre a maior potência de 2 que divide cada um dos inteiros seguintes
(a) (101111110)2
(b) (1010000011)2
(c) (111000000)2
(d) (1011011101)2
78. Quais dos inteiros do exercício anterior são divisíveis por 3?
79. Quais dos seguintes inteiros são divisíveis por 2?
(a) (1210122)3
(b) (211102101)3
(c) (1112201112)3
(d) (10122222011101)3
80. Dos seguintes inteiros quais são divisíveis por 3 e quais os divisíveis por 5?
(a) (3EA235)16
(b) (ABCDEF )16
(c) (F 117921173)16
(d) (10AB987301F )16
81. Quais dos inteiros do exercício anterior são divisíveis por 17?
82. Uma capicua é um inteiro que se lê do mesmo modo da esquerda para a direita e da
direita para a esquerda.
(a) Mostre que uma capicua na base 10 com um número par de algarismos é divisível
por 11.
(b) Mostre que uma capicua na base 7 com um número par de algarismos é divisível
por 8.
83. Baseado no facto de 103
divisível por 37.
1(mod37), encontre um teste para avaliar se um inteiro é
84. Use o resultado do exercício anterior para veri…car se 443692 ou se 11092785 são
divisíveis por 37.
85. Determine o dia da semana em que ocorreram os seguintes acontecimentos históricos:
(a) Morte de Filipe II (31 de Março de 1621);
(b) Carta régia que expulsa de Lisboa as pessoas "inquietas e escandalosas" (4 de
Junho de 1624);
(c) Intenso terramoto em Lisboa e sul do Tejo (1 de Novembro de 1755);
(d) Extinção da Universidade de Évora (5 de Outubro de 1759);
(e) Fundação do Instituto Industrial de Lisboa (30 de Dezembro de 1852);
(f) Fundação do Real Automóvel Clube de Portugal (7 de Dezembro de 1903);
(g) Assassinato do Rei D. Carlos (1 de Fevereiro de 1908);
(h) Criação das Universidades de Lisboa e Porto (22 de Março de 1911);
(i) Início da publicação do semanário Expresso (6 de Janeiro de 1973);
(j) Criado o Instituto Universitário dos Açores (9 de Fevereiro de 1976);
(k) Criado o Instituto Superior da Beira Interior (11 de Setembro de 1979);
(l) Criação da Universidade do Algarve (28 de Março de 1979).
7
exercícios de teoria de números
86. A tabela seguinte fornece a percentagem de ocorrência de cada letra em língua inglesa:
a
7
b
1
c
3
d
4
e
13
f
3
g
2
h
3
i
8
j
<1
k
<1
l
4
m
3
n
8
o
7
p
3
q
<1
r
8
s
6
t
9
u
3
v
1
w
1
x
<1
A mensagem KY V M R CLV F W KY V BV P ZJJV M V EKV V E, foi cifrada
usando uma cifra da forma C (P + k)(mod26). Determine o valor de k e descodi…que a mensagem.
87. Se numa mensagem em língua inglesa as letras mais frequentes forem o X e o Q
respectivamente e se se souber que a mensagem foi cifrada usando a cifra
C
(aP + b)(mod26);
quais serão os valores mais prováveis para a e b?
88. Dadas duas cifras, pode-se aplicar uma após a outra para codi…car uma mensagem.
Este procedimento conduz à chamada cifra produto. Encontre a cifra produto de
C (5P + 13)(mod26) e C (17P + 3)(mod26).
89. Usando a cifra por blocos 2
CU IDADO
COM
O
2 com matriz
3 10
, codi…que a mensagem:
9 7
M EN SAGEIRO.
90. A seguinte mensagem em língua inglesa foi codi…cada usando uma cifra por blocos
13 4
2 2 com matriz
:
9 1
QW RD DS AK. Decifre-a.
2
3
11 2 19
91. Usando a cifra por blocos 3 3 com matriz 4 5 23 25 5, codi…que a mensagem:
20 7 1
~
N AO M AT EM O M EN SAGEIRO.
RD
SR QO
VU
QP
CZ
AN
92. Um criptanalista, ao tentar decifrar uma mensagem, detectou que os blocos mais
frequentes eram RH e N I que, por isso, devem corresponder aos blocos T H e HE,
que são os mais comuns em língua inglesa. Supondo que o texto foi codi…cado usando
uma cifra por blocos 2 2, qual terá sido a matriz utilizada?
93. Encontre a cifra produto que resulta de aplicar a cifra por blocos 2
2 3
5 1
seguida da cifra por blocos 2 2 com matriz
.
1 17
25 4
2 com matriz
94. Organize um calendário de jogos para um torneio de ténis com
(a) 7 jogadores
(b) 8 jogadores
95. Use o critério de dígito de veri…cação descrito nas aulas para determinar qual o algarismo de veri…cação que deve ser acrescentado aos seguintes números de passaporte:
(a) 132999
(b) 805237
(c) 645153
y
2
z
<1
8
exercícios de teoria de números
96. Qual deverá ser o algarismo …nal dos seguintes ISBN:
(a) 2
113
54001
........
(b) 0
070
38133
........
97. Determine quais dos seguintes ISBN são válidos:
(a) 0
394
38049
5
(b) 1
092
31221
3
(c) 0
404
50874
X
98. Supondo que as seguintes sequências são ISBN válidos, a que falta um algarismo,
representado por ?, determine os algarismos em falta
(a) 0
198 ?3804
(b) ?
261
9
05073
X
99. O governo da Noruega usa um esquema de 11 algarismos, x1 x2 :::x11 , para os números
de bilhete de identidade dos seus cidadãos que funciona do seguinte modo:
- os algarismos x1 x2 :::x6 representam a data do nascimento;
- os algarismos x7 x8 x9 identi…cam uma pessoa em particular nascida nesse dia
- os algarismos x10 x11 são algarismos de controlo determinados por
x10
8x1 + 4x2 + 5x3 + 10x4 + 3x5 + 2x6 + 7x7 + 6x8 + 9x9 (mod11)
x11
6x1 + 7x2 + 8x3 + 9x4 + 4x5 + 5x6 + 6x7 + 7x8 + 8x9 + 9x10 (mod11)
(a) Determine os 2 últimos algarismos da sequência 110491238
(b) Mostre que este esquema permite detectar todas as trocas de um único algarismo
(c) Determine quais as trocas de 2 algarismos que não são detectadas.
100. Encontre um sistema reduzido de restos módulo m, com m =
(a) 6
(b) 9
(c) 10
(d) 16
(e) 17
101. Resolva cada uma das seguintes congruências usando o teorema de Euler
(a) 5x
(b) 4x
3(mod14)
7(mod15)
(c) 3x
5(mod(16)
102. Use o teorema de Euler para determinar o último algarismo de 71000 .
103. Calcule (n) para 21
n
30.
104. Mostre que se fc1 ; c2 ; :::; c (m) g é um sistema reduzido de restos módulo m, então
c1 + c2 + ::: + c (m) 0(modm).
105. Quais das seguintes funções são completamente multiplicativas?
(a) f (n) = 0
(f) f (n) = n!
(b) f (n) = 2
(c) f (n) = n=2 (d) f (n) = logn
p
(g) f (n) = n + 1 (h) f (n) = nn (i) f (n) = n
(e) f (n) = n2
9
exercícios de teoria de números
106. A partir do facto da função de Euler ser multiplicativa é possível deduzir uma fórmula
para o seu cálculo. Seja n um inteiro positivo cuja factorização em factores primos
1
1
1
é n = p1 1 p2 2
pk k , então (n) = n 1
1
1
. Use esta
p1
p2
pk
expressão para calcular (100)
107. Calcule a função
de Euler para cada um dos inteiros
(a) 100
(b) 256
(c) 1001
(d) 2
3
5
7
11
13
(e) 10!
(f) 20!
108. Usando o teorema de Wilson, encontre o menor resto positivo de 8 9 10 11 12 13
módulo 7.
109. Usando o pequeno teorema de Fermat, encontre o menor resto positivo de 21000000
módulo 17.
110. Usando o pequeno teorema de Fermat, encontre o último algarismo de 3100 em base
7.
111. Mostre que se p é primo e a e b são inteiros tais que ap
ap bp (mod p2 ).
112. Mostre que 310
bp (mod p), então
1(mod 121).
113. Mostre que 341, 561 e 645 são pseudoprimos na base 2.
114. Usando o pequeno teorema de Fermat, encontre as soluções das seguintes congruências:
(a) 7x
12(mod 17)
(b) 4x
11(mod 19)
115. Mostre que, se p é um primo impar, então 2(p
3)!
116. Mostre que se n é impar e 3 não divide n então n2
117. Mostre que 42j(n7
118. Se p é primo e p
( 1)(mod p).
1(mod 24).
n) para todos os inteiros positivos n.
3(mod 4), então
p
1
2
!
1(mod p).
119. Usando o teorema de Wilson mostre que se p é primo e p
x2
( 1)(mod p) tem duas soluções não congruentes dadas por x
120. Mostre que se p é primo e a é um inteiro , então pj(ap + (p
1(mod 4), então
p 1
!(mod p).
2
1)!a).
121. Mostre que o par de inteiros positivos n e n + 2 são primos gémeos se e só se
4((n 1)! + 1) + n 0(mod n(n + 2)); n 6= 1.