Provas

UNIVERSIDADE FEDERAL DO RIO DE
JANEIRO
Departamento de Ciência da Computação–UFRJ
30 de abril de 2015

Números inteiros e criptografia
S. C. Coutinho
Provas e gabaritos

Até a página 25 você encontrará as provas do curso de Álgebra para a informática–que era basicamente uma versão anterior do mesmo curso.
Lembre-se: Nas provas não são aceitas respostas sem justificativa. Você deve saber explicar tudo o que fizer.

1

Prova 1: segundo semestre de 1995

1a Questão. Determine:
1. o máximo divisor comum d de a = 272828282 e b = 3242 e inteiros α e β tais que αa + βb = d.
2. um fator de 6883901 pelo algoritmo de Fermat.
3. um fator primo de 23965157 − 1.
4. as soluções de x2 ≡ 7 (mod 43).
5. o resto da divisão de 3950! por 2251.
6. uma seqüência de 5646345 inteiros consecutivos que sejam todos compostos.

2a Questão. Chamamos de hexagonais os números definidos pela fórmula hn = 1 +
3n(n − 1) para n = 1, 2, . . . . O nome vem do fato de que estes números podem ser dispostos em hexágonos regulares concêntricos.
1. Calcule a soma dos n primeiros números hexagonais quando n = 1, 2, 3 , 5, 6 e
7. Use estes dados numéricos para advinhar a fórmula da soma dos n primeiros números hexagonais.
2. Prove a fórmula obtida no item anterior usando o método de indução finita.

Page 2

Prova 2: segundo semestre de 1995

1a Questão. Determine:
1. Um fator primo de M (37).
2. Dois inteiros positivos que sejam solução de φ(n) = 136.
2a Questão. Verifique se 703 é:
1. um número de Carmichael;
2. um pseudoprimo forte para a base 7.
3. um pseudoprimo para a base 7;
3a Questão. Três satélites passarão sobre o Rio esta noite. O primeiro passará à 1 hora da madrugada, o segundo às 4 horas e o terceiro às 8 horas da manhã. Cada satélite tem um período diferente. O primeiro leva 13 horas para completar uma volta em torno da
Terra, o segundo leva 15 horas e o terceiro 19 horas. Determine quantas horas terão que se passar, a partir da meia-noite, até que os três satélites passem ao mesmo tempo