p2a-sol-alg1

Prévia do material em texto

IM – UFRJ Álgebra I
Prova 2 Turma A 05/07/2016
.................................................................................................................................
Todos os resultados devem ser acompanhados de contas que os justifiquem.
1a Questão: (3 pontos) Resolve o sistema:
x ≡ 2( mod 3)
x ≡ 3( mod 5)
4x ≡ 1( mod 7)
c1 = 2, c2 = 3, c3 = 2 N1 = 35, N2 = 21, N3 = 15
r1 = −1, r2 = 1, r3 = 1 x ≡ 23 mod 105.
2a Questão: (3 pontos)
a) Mostre que a37 ≡ a( mod 91)
Pelo Teorema de Fermat a6 ≡ 1 mod 7 e a12 ≡ 1
mod 13.
Como a37 = (a6)6.a ≡ a mod 7 e a37 = (a12)3.a ≡ a
mod 13 temos que a37 ≡ a( mod 91).
b) Sejam p, q primos distintos tais que (p− 1) | (q− 1).
Se mdc(a, pq) = 1, provar que aq−1 ≡ 1( mod pq)
Pelo teorema de Fermat aq−1 ≡ 1 mod q. Como (p −
1) | (q − 1) temos que q − 1 = k(p− 1) por algum k.
Assim, aq−1 = ak(p−1) ≡ 1 mod p.
c) 3123 ≡ (310)12.33 ≡ 27 ≡ 5( mod 11)
3a Questão: (4 pontos)
A chave pública é (e, n) = (5, 91). A mensagem recebida
depois de cifrar é M = 82. Qual é a mensagem original
m?
a) p = 7, q = 13 e φ(91) = 72.
b) de ≡ 1 mod 72, d = 29.
c) 8229 ≡ 82−1 ≡ 5−1 ≡ 3 mod 7.
8229 ≡ 825 ≡ 45 ≡ 210 ≡ 2−2 ≡ (2−1)2 ≡ 72 ≡ 49 ≡ 10
mod 13.
Como 10 ≡ 3 mod 7, temos que m =Md = 10.