p2-2018-sol

Prévia do material em texto

IM – UFRJ Álgebra I
Prova 2 14/06/2018
.................................................................................................................................
Todos os resultados devem ser acompanhados de contas que os justifiquem.
1a Questão: (2 pontos) Resolve o sistema:
2x ≡ 1( mod 3)
3x ≡ 1( mod 4)
x ≡ 4( mod 5)
c1 = 2, c2 = 3, c3 = 4 N1 = 20, N2 = 15, N3 = 12
r1 = −1, r2 = −1, r3 = −2 x ≡ 59 mod 105.
2a Questão: (2 pontos)
Provar que, se a é inversível em Zm ( nos inteiros módulo
m ), então seu inverso é único.
a inversível se e somente se mdc(a,m) = 1. Se ab ≡
1 ≡ ac mod p entao a(b − c) ≡ 0 mod m. Como
mdc(a,m) = 1, a 6≡ 0 mod m entao b− c ≡ 0 mod m
que significa que a ≡ b mod m.
3a Questão: (3 pontos)
a) Mostre que a79 ≡ a( mod 158)
Pelo Teorema de Fermat a79 ≡ a mod 79 e a2 ≡ a
mod 2.
Como a79 = a mod 7 e a79 = (a2)34.a ≡ a.a ≡ a
mod 2 temos que a79 ≡ a( mod 158).
b) Sejam a, b inteiros e p um primo tal que mdc(a, p) =
1. Se ab ≡ 1( mod p) mostre que b ≡ ap−2( mod p)
ap−1 ≡ 1 mod p. ab(ap−2) = ap−1b = b ≡ ap−2 mod p
c) 331 ≡ (36)5.3 ≡ 3( mod 7).
4a Questão: (3 pontos)
A chave pública é (e, n) = (11, 143). A mensagem re-
cebida depois de cifrar é c = 106. Qual é a mensagem
original m?
d = 11,m = 7