Prova1 Resolvida

Prévia do material em texto

Prova 1 Teoria de Números 23/04/2013
Nome:
RA:
Escolha 5 questões.
1. Mostre que 267 + 334 é múltiplo de 17.
Solução: Pelo teorema de Fermat 216 � 1 (mod 17) e 317 � 3 (mod 17). Por-
tanto,
267 = 264+3 =
�
216
�4 � 8 � 8 (mod 17)
e 334 = (317)2 � 9 (mod 17). Daí que 267 + 334 � 8 + 9 � 0 (mod 17), o que
signi…ca que 267 + 334 é múltiplo de 17.
2. Mostre que a7 � a (mod 21) para todo inteiro a.
Solução: Em primeiro lugar pelo teorema de Fermat a7 � a (mod 7), o que
signi…ca que 7=a7 � 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 = a6a � 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 � 1 (mod 5); ii) 8x � 2 (mod 7)
e iii) 23x � 2 (mod 11).
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 � 2 (mod 7) x � 2 (mod 11)
pois 2 é a inversa de 3 (mod 5), 8 � 1 (mod 7) e iii) 23 � 1 (mod 11). Valem as
seguintes a…rmações:
(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
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ências8<:
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 a8<:
x+ y � 2 (mod 12)
�y + 2z � 1 (mod 12)
x+ 3y + z � 3 (mod 12)
A matriz dos coe…cientes desse sistema é
A =
0@ 1 1 00 �1 2
1 3 1
1A
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,
Cof (A) =
0@ �7 2 1�1 1 �2
2 �2 �1
1A
Portanto, a solução é dada por0@ xy
z
1A � 7
0@ �7 �1 22 1 �2
1 �2 �1
1A0@ 21
3
1A (mod 12) :
Isto é,
2
(a) x � 7 (�14� 1 + 6) � 21 � 9 (mod 12),
(b) y � 7 (4 + 1� 6) � 5 (mod 12) e
(c) z � 7 (2� 2� 3) � �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 � �12; 7 � �10; 9 � �18; 11 � �6; 13 � �4; 15 � �2:
Como a2 = �a (�a), se obtém as seguintes congruências módulo 17:
32 � �3 � 14; 52 � �5 � 12; 72 � �7 � 10; 92 � �9 � 18;
112 � �11 � 6; 132 � �13 � 4; 152 � �15 � 2:
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 de-
composição primária de n. Mostre que se � (n) é divisor de n então n não é
multiplo de 5.
Solução: Se n = pm11 � � � pmss então
� (n) = � (pm11 ) � � �� (pmss )
=
�
pm11 � pm1�11
� � � � �pmss � pms�11 �
= n
�
1� 1
p1
�
� � �
�
1� 1
ps
�
:
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 =
2km 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
m é da forma m = 5lpm11 � � � pmss com pi primos ímpares. Portanto, � (m) =
�
�
5l
�
� (pm11 � � � pmss ). 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 � 2 (mod 5) então x não é
quadrado perfeito.
(b) Se m e n são inteiros tais que m2 � n2 (mod 8) então m � �n (mod 8).
(c) Existe um inteiro positivo n tal que � (n) = 217. (� é a função de Euler.)
(d) 17144 � 1 (mod 36).
Solução:
(a) Verdadeira. Um número y é congruente a 0; 1; 2; 3; 4 módulo 5. Por-
tanto, y2 é 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 � 1 (mod 8) nem
3 � �1 � 7 (mod 8).
(c) Falsa. A função � de Euler só assume valores pares.
(d) Verdadeira. � (36) = � (2232) = � (22)� (32) = 12. Como (17; 36) = 1,
o teorema de Euler garante que 1712 � 1 (mod 36). Daí que 17144 =
(1712)
12 � (1)12 � 1 (mod 36).
9. Sejamm e n números inteiros com (m;n) = 1 tal que (m3 + 7mn+ n2) =m3n3.
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=m3n3 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