Prova-2-2009-1-Numeros-Inteiros-e-Criptografia-Severino-Collier-Coutinho

Prévia do material em texto

Segunda Prova–2009/1
1. Prove, por indução em n, que
7 + 5 + 3 + · · ·+ (9− 2n) = −n2 + 8n.
Indique claramente cada etapa da indução.
2. O objetivo desta questão é mostrar que existem infinitos primos positivos p
que satisfazem a condição p ≡ 5 (mod 6). Suponha, por contradição, que
p1, . . . , pm são todos os primos diferentes de 5, que deixam resto 5 na divisão
por 6. Seja N = p1 · · · pm.
(a) Calcule os possíveis resíduos de 6N + 5 módulo 6.
(b) Prove que (a) implica que 6N +5 tem que ter um fator primo que deixa
resto 5 na divisão por 6.
(c) Use mdc(N, 6N +5) = 1 e (b) para provar que existem infinitos números
primos que deixam resto 5 na divisão por 6.
3. Sabe-se que 3 tem ordem 126 módulo 127. Use isto para:
(a) determinar as ordens de 9 e de 27 módulo 127;
(b) calcular o resto da divisão de 9250049 por 127.
A sua resposta à letra (a) deve ser cuidadosamente justificada utilizando os
resultados provados em aula.
Resolução
1. Seja
Sn = 7 + 5 + 3 + · · ·+ (9− 2n).
Nosso objetivo é provar por indução em n que
Sn = −n2 + 8n,
para todo n ≥ 1. Seja
V = {n ∈ N≥1|Sn = −n2 + 8n}.
Vamos mostrar, usando o princípio de indução finita, que V = N≥1.
Começamos com a base, que consiste em mostrar que 1 ∈ V . Como
S1 = 7 e − 12 + 8 · 1 = 7,
temos que S1 = (−n2 + 8n)|n=1, o que confirma a validade da base.
Para o passo de indução suporemos que k ∈ V , para algum inteiro k ≥ 1. Em
outras palavras, a hipótese de indução nos diz que
Sk = −k2 + 8k.
Já o que queremos mostrar é que k + 1 ∈ V ; isto é, que
Sk+1 = −(k + 1)2 + 8(k + 1).
Contudo,
Sk+1 = Sk + (9− 2k).
Usando a hipótese de indução, isto fica igual a
Sk+1 = −k2 + 8k + (9− 2(k + 1)) = −k2 − 2k − 1 + 8k + 8,
que pode ser reescrito na forma
Sk+1 = −(k2 + 2k + 1) + 8(k + 1) = −(k + 1)2 + 8(k + 1),
como queríamos mostrar. Portanto,
1 ∈ V e toda vez que k ∈ V também temos que k + 1 ∈ V.
Logo, pelo P. I. F., V = N≥1.
2. Como
6N + 5 ≡ 5 (mod 6),
temos que 6N + 5 tem que deixar resto 5 na divisão por 6, não importa qual seja o
inteiro positivo N escolhido. Por outro lado, como pi ≡ 1 (mod 6), temos que
p1 · · · pm ≡ 1m ≡ 1 (mod 6).
Portanto, se todo os fatores primos de 6N + 5 deixassem resto um na divisão por 6,
então 6N +5 também teria que ter resto um na divisão por 6. Como já sabemos que
isto é falso, podemos concluir que 6N + 5 tem que ter algum fator primo que deixa
resto 5 na divisão por 6. Acontece que, por hipótese, estamos supondo que
5, p1, . . . , pm
são todos os primos que deixam resto 5 na divisão por 6. Logo, 6N + 5 teria que ser
divisível por um destes primos. Mas isto não é possível porque
mdc(6N + 5, N) = 1.
Como 5 não divide N , teremos que tratá-lo separadamente. Mas se 5 dividisse 6N+5,
então dividiria 6N , o que não é possível pela definição de N . Obtemos, assim, uma
contradição e a demonstração está completa.
3. (a) Para fazer (a) precisamos usar o lema chave:
se ar ≡ 1 (mod n), então a ordem de a módulo n tem que dividir r.
Como sabemos que 3 tem ordem 126 módulo 127, podemos concluir que
3126 ≡ 1 (mod 127), e que 3m 6≡ 1 (mod 127),
qualquer que seja 1 ≤ m ≤ 125. Contudo, 126 = 2 · 63, de modo que
963 ≡ 32·63 ≡ 1 (mod 127).
Pelo lema chave isto significa que a ordem de 9 módulo 127 divide 63. Por outro
lado, se a ordem se 9 módulo 127 fosse k < 63, então
9k ≡ 32·k ≡ 1 (mod 127),
de modo que 3 teria ordem
2k < 2 · 63 = 126,
módulo 3; o que é falso por hipótese. Logo, a ordem de 9 módulo 127 é realmente
igual a 63. Um argumento análogo mostra que, como 126 = 3 · 42, então de
2742 ≡ 33·42 ≡ 1 (mod 127).
segue que 27 tem ordem 42 módulo 127.
Para fazer (b) basta dividir 250049 pela ordem de 9 que é 63, o que nos dá
250049 = 63 · 3969 + 2.
Assim,
9250049 ≡ (963)3969 · 92 ≡ 1 · 81 (mod 127).
Logo, o resto desejado é 81.