Prova 2 com resolução - Teoria dos Números

Prévia do material em texto

Curso: Ciência da Computação 
Disciplina: Teoria dos Números 
Professor: Marcelo Cunha 
 
2ª Prova 
Nome: 
______________________________________________________ Valor: 30 pontos 
Data: _____/_____/_____ Nota:_________ 
 
01) 
a) Pelo algoritmo de Euclides determine o máximo divisor comum entre os números 252 e 528. 
Pelo algoritmo de Euclides obtemos como m.d.c 12 
b) Utilizando o item anterior, calcule o mínimo múltiplo comum entre eles. 
 
 
02) 
a) Prove que dois inteiros a e b, não conjuntamente nulos, são primos entre si se e somente se 
existem inteiros x e y tais que . 
 
Se a e b são primos entre si, então o e por consequentemente existem inteiros x e y 
tais que . 
 
Reciprocamente, se existem inteiros x e y tais que e se o , logo 
 , consequentemente, , ou seja . Assim os inteiros e são primos 
entre si 
 
b) Prove que se e se , então 
Pelo teorema anterior sabemos que: 
 
 
 
 
Logo: 
 
 
 
Logo: 
 
03) 
Determine os inteiros positivos e sabendo que e . 
 
Como o , então e , com e primos entre si. Assim 
retornando com essas relações na equação obtemos: 
 
Sendo e primos entre si, os pares e são os que satisfazem a 
equação. Logo os pares , e resolvem o problema. 
04) 
a) Mostre que o número 929 é primo. 
Sabemos que se nenhum "p" primo com divide 929, então 929 é primo. 
Como , vamos dividir o 929 por todos os primos menores que 30. 
Os primos menores que 31 são: 2,3,5,7,11,13,17,19,23 e 29. Dividindo 929 por todos eles 
verificamos que nenhum deles divide 929, logo 929 é primo. 
b) Sendo e , determine o máximo divisor comum e o mínimo 
múltiplo comum entre e . 
 
Se d é o então ele deve conter em sua fatoração em primos, primos que estão em a e b ao 
mesmo tempo, com menor expoente. Logo: 
 
Se m é o então ele deve conter todos os primos que estão em a e b, maior expoente. 
 
 
 
 
05) 
a) Resolva a equação diofantina linear . 
Primeiro vamos verificar se a equação diofantina linear tem solução. 
Fazendo o , e , logo tem solução. 
Fazendo agora o algoritmo de Euclides estendido: 
restos quociente 
172 * 1 0 
20 * 0 1 
12 8 -8 
 8 1 -1 9 
4 1 2 -17 
0 2 
 
 
Logo 
 
 
 
 
 
 
 
 
b) Determine as soluções inteiras e positivas da equação acima. 
 
 
 
 
 
 
 
 
 
O único número inteiro que pertence ao intervalo é o -36. Logo a única 
solução positiva é o par .