Prova 1
Nome:
RA:
Teoria de Números
23/04/2013
Escolha 5 questões.
1. Mostre que 267 + 334 é múltiplo de 17.
Solução: Pelo teorema de Fermat 216
tanto,
267 = 264+3 = 216
1 (mod 17) e 317
4
8
8 (mod 17)
2
e 334 = (317 )
9 (mod 17). Daí que 267 + 334
67
signi…ca que 2 + 334 é múltiplo de 17.
2. Mostre que a7
3 (mod 17). Por-
8+9
0 (mod 17), o que
a (mod 21) para todo inteiro a.
Solução: Em primeiro lugar pelo teorema de Fermat a7
a (mod 7), o que
7
signi…ca que 7=a
a. Tomando congruência módulo 3, suponha em primeiro
lugar que (a; 3) = 1. Então, a2
1 (mod 3) e daí que a7 = a6 a a (mod 3).
Por outro lado, se (a; 3) 6= 1 então a 0 (mod 3) o que implica que a7 0
a (mod 3). Em ambos os casos 3=a7 a. Como (3; 7) = 1, segue que o produto
21 = 3 7 é divisor de a7 a, isto é, a7 a (mod 21).
3. Encontre todos os números x 2 Z tais que i) 3x
e iii) 23x 2 (mod 11).
1 (mod 5); ii) 8x
2 (mod 7)
Solução: Trata-se de uma aplicação direta do teorema chinês dos restos. O
teorema se aplica pois 5, 7 e 11 são primos entre si.
As congruências do enunciado são equivalentes, respectivamente a
x
2 (mod 5)
x
pois 2 é a inversa de 3 (mod 5), 8
seguintes a…rmações:
2 (mod 7)
x
2 (mod 11)
1 (mod 7) e iii) 23
(a) A inversa de 77 = 7 11
2 módulo 5 é 3.
(b) A inversa de 55 = 5 11
6 módulo 7 é 6.
(c) A inversa de 35 = 5 7
2 módulo 11 é 6.
1
1 (mod 11). Valem as
Portanto, pelo teorema chinês dos restos, o conjunto das soluções é a classe de
congruência módulo 385 = 5 7 11 do número
x = 2 77 3 + 2 55 6 + 2 35 6
= 462 + 660 + 420
= 1542:
Como 1542
2 (mod 385) as soluções são dadas por
385 n + 2
n 2 Z:
4. Encontre todos os números x; y; z 2 Z que satisfazem as seguintes congruências
8
< x + 13y 2 (mod 12)
y + 14z 1 (mod 12)
:
x + 3y + 13z 3 (mod 12)
Solução: Como 13
1 (mod 12) e 14 2 (mod 12) o sistema é equivalente a
8
< x + y 2 (mod 12)
y + 2z 1 (mod 12)
:
x + 3y + z 3 (mod 12)
A matriz dos coe…cientes desse sistema é
0
1
1 1 0
1 2 A
A=@ 0
1 3 1
cujo determinante é 5 7 (mod 12). Esse determinante tem inversa módulo
12, portanto, pelo teorema de Cramer, a matriz tem inversa módulo 12. Essa
inversa é dada por
A 1 = 7Cof (A)T
pois 7 é a sua inversa módulo 12. No entanto,
0
7 2
@
1 1
Cof (A) =
2
2
Portanto, a solução é dada por
0 1
0
x
7
@ y A 7@ 2
z
1
1
1
2
Isto é,
2
1
1
2 A
1
10 1
2
2
A
@
2
1 A (mod 12) :
1
3
(a) x
7 ( 14
(b) y
7 (4 + 1
6)
(c) z
7 (2
3)
2
1 + 6)
21
9 (mod 12),
5 (mod 12) e
21
3 (mod 12).
5. Use o teorema de Wilson para encontrar o resto da divisão de 32 52 72 92
112 132 152 por 17.
Solução: Valem as seguintes congruências módulo 17:
3
14; 5
Como a2 =
32
112
12; 7
10; 9
18; 11
6; 13
4; 15
2:
a ( a), se obtém as seguintes congruências módulo 17:
3 14; 52
11 6; 132
5 12; 72
13 4; 152
7 10; 92
15 2:
9 18;
Daí que 32 52 72 92 112 132 152 é congruente módulo 17 a ( 1)7 15! =
15!. Pelo teorema de Wilson 16!
1 (mod 17). Mas, 16
1 (mod 17),
portanto 15!
1 (mod 17). Daí que 15!
1 (mod 17) portanto o número
do enunciado é congruente a 1 (mod 17). O resto de sua divisão por 17 é 16.
6. Seja a função de Euler. Escreva a fórmula para (n) em termos da decomposição primária de n. Mostre que se (n) é divisor de n então n não é
multiplo de 5.
1
Solução: Se n = pm
1
s
pm
então
s
1
s
(pm
(pm
1 )
s )
s
1
1 1
s
pm
pm
pm
pm
1
1
1
s
1
1
1
:
= n 1
p1
ps
(n) =
=
1
Suponha agora que (n) =n. Se n = 2 então n não é multiplo de 5. Se n 3
então (n) é par e a hipótese (n) =n implica que n também é par. Isto é, n =
2k m com k 1 e m 1 ímpar. Nesse caso, (n) = 2k (m) = 2k 1 (m).
Suponha por absurdo que 5=n. Então, 5=m e a decomposição primária de
1
s
m é da forma m = 5l pm
pm
com pi primos ímpares. Portanto, (m) =
1
s
m1
l
ms
5
(p1
ps ). Mas,
5l = 5l 1 4. Daí que o expoente de 2 na
decomposição primária de (n) é pelo menos k 1+2 = k+1 (k 1 proveniente
de
2k e 2 proveniente de
5l ). Isto é, 2k+1 = (n). Mas, isso é absurdo
pois (n) =n e a maior potência de 2 que é divisor de n é 2k .
3
7. Dado os inteiros positivos a; b e c, mostre que se a b (mod c) então (a; c) =
(b; c). Use isso para mostrar que não existem x; y inteiros tais que x + y = 100
e (x; y) = 3.
Solução: Sejam d = (a; c) e e = (b; c). Se a
b (mod c) então existe um
inteiro n tal que b = a + nc. Dessa igualdade segue que d=b pois d=a e d=n.
Portanto, d=b e d=n o que implica que d=e. Pelo mesmo argumento se conclui
que e=d.
8. Para cada uma das a…rmações a seguir diga se é verdadeira ou falsa. No caso
verdadeiro apresente uma justi…cativa e no falso, um contra-exemplo.
(a) Se x é um número inteiro positivo tal que 4x
quadrado perfeito.
(b) Se m e n são inteiros tais que m2
(c) Existe um inteiro positivo n tal que
(d) 17144
2 (mod 5) então x não é
n2 (mod 8) então m
n (mod 8).
(n) = 217. ( é a função de Euler.)
1 (mod 36).
Solução:
(a) Verdadeira. Um número y é congruente a 0; 1; 2; 3; 4 módulo 5. Portanto, y 2 é congruente a 0; 1; 4 módulo 5, isto é, se um número é quadrado
perfeito então ele é congruente a 0; 1; 4 módulo 5. Por outro lado, se
4x 2 (mod 5) então x 8 3 (mod 5), pois 4 é a sua inversa módulo
5. Daí que x não pode ser quadrado perfeito.
(b) Falsa. 32
1
12 (mod 8) e, no entanto, não vale 3
3
1 7 (mod 8).
(c) Falsa. A função
1 (mod 8) nem
de Euler só assume valores pares.
(d) Verdadeira. (36) = (22 32 ) = (22 ) (32 ) = 12. Como (17; 36) = 1,
o teorema de Euler garante que 1712
1 (mod 36). Daí que 17144 =
12
(1712 )
(1)12 1 (mod 36).
9. Sejam m e n números inteiros com (m; n) = 1 tal que (m3 + 7mn + n2 ) =m3 n3 .
Mostre que não existe um número primo p tal que p= (m3 + 7mn + n2 ) e,
portanto, m3 + 7mn + n2 = 1.
Solução: Suponha por absurdo que o primo p seja divisor de m3 + 7mn + n2 .
Então, p=m3 n3 e portanto p=m3 ou p=n3 , pois p é primo. Suponha, por exemplo
que p=m3 . Novamente, como p é primo, segue que p=m. Daí que p=m3 e p=7mn
e como por hipótese p=m3 + 7mn + n2 segue que p=n2 e, portanto, p=n. O que
é um absurdo pois (m; n) = 1.
4
Como nenhum primo é divisor de m3 + 7mn + n2 a única possibilidade é que
m3 + 7mn + n2 = 1.
5