Description

Exercise 5.1 (4pts)
Given a,b,c,d,m ∈ Z, m > 0. Show that
(i) (2pts) If a ≡ b (mod m), and d | m, d > 0, then a ≡ b (mod d).
(ii) (2pts) If a ≡ b (mod m), and c > 0, then ac ≡ bc (mod mc)
Exercise 5.2 (4pts)
Given a,x,y,m ∈ Z, m > 0. Show that
(i) (2pts) .
(ii) (2pts) If ax ≡ ay (mod m) and gcd(a,m) = 1, then x ≡ y (mod m).
Exercise 5.3 (2pts)
Given x,y ∈ Z, and positive intergers m1,…,mr, show that x ≡ y (mod mi) for i = 1,2,…,r iff x ≡ y (mod m), where m = lcm(m1,m2,…,mr).
Exercise 5.4 (6pts)
Given p ∈ P, show that
(i) (2pts) x2 ≡ 1 (mod p) iff x ≡ ±1 (mod p).
(ii) (2pts) (Wilson’s theorem) (p − 1)! ≡ −1 (mod p).
(iii) (2pts) If p ≡ 3 (mod 4), then .
Exercise 5.5 (2pts)
We know that for all integers a coprime to 561, we have
(i) a3−1 ≡ 1 (mod 3) (ii) a11−1 ≡ 1 (mod 11) (iii) a17−1 ≡ 1 (mod 17)
Show that a561 ≡ a (mod 561) for all integers a.
Exercise 5.6 (6pts)
Given p,q ∈ P, a ∈ Z, show that
(i) (2pts) If aq ≡ 1 (mod p), then either p ≡ 1 (mod q) or a ≡ 1 (mod p).
(ii) (2pts) If 5 | a and p | a4 + a3 + a2 + a + 1, then p ≡ 1 (mod 5).
(iii) (2pts) Use (ii) to show that there are infinitely many primes of the form 10n + 1, n ∈ N.
Exercise 5.7 (2pts)
Find prime factors of F5 = 225 + 1 by applying Fermat’s theorem.
Exercise 5.8 (2pts)
Exercise 5.9 (2pts)
Sove the following system of linear congruence
x ≡ 2 (mod 4)
x ≡ 5 (mod 7)
x ≡ 0 (mod 11)
x ≡ 8 (mod 15)
Exercise 5.10 (4pts)
(i) (2pts) Show that 6x ≡ 2 (mod 3) has no solutions.
(ii) (2pts) Show that 6x ≡ 2 (mod 5) has infinitely many solutions.
Page 1 of 2
Exercise 5.11 (6pts)
Given public key (n,E) = (323,95), where 323 = 17 × 19.
(i) (2pts) Encrypt the message 233 by the encryption function e(x) = xE (mod n).
(ii) (2pts) Compute the private key D = E−1 (mod φ(n)). (iii) (2pts) Decrypt the encrypted message in (i).
Page 2 of 2