Exercise 5.1
Given a,b,c,d,m ∈ Z, m > 0. Show that
(i) If a ≡ b (mod m), and d | m, d > 0, then a ≡ b (mod d).
(ii) If a ≡ b (mod m), and c > 0, then ac ≡ bc (mod mc)
Exercise 5.2
Given a,x,y,m ∈ Z, m > 0. Show that
(i) .
(ii) If ax ≡ ay (mod m) and gcd(a,m) = 1, then x ≡ y (mod m).
Exercise 5.3
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
Given p ∈ P, show that
(i) x2 ≡ 1 (mod p) iff x ≡ ±1 (mod p).
(ii) (Wilson’s theorem) (p − 1)! ≡ −1 (mod p).
(iii) If p ≡ 3 (mod 4), then .
Exercise 5.5
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
Given p,q ∈ P, a ∈ Z, show that
(i) If aq ≡ 1 (mod p), then either p ≡ 1 (mod q) or a ≡ 1 (mod p).
(ii) If 5 | a and p | a4 + a3 + a2 + a + 1, then p ≡ 1 (mod 5).
(iii) Use (ii) to show that there are infinitely many primes of the form 10n + 1, n ∈ N.
Exercise 5.7
Find prime factors of F5 = 225 + 1 by applying Fermat’s theorem.
Exercise 5.8
Show that 2021 is not prime by Fermat test.
Exercise 5.9
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
(i) Show that 6x ≡ 2 (mod 3) has no solutions.
(ii) Show that 6x ≡ 2 (mod 5) has infinitely many solutions.
Page 1 of 2
Exercise 5.11
Given public key (n,E) = (323,95), where 323 = 17 × 19.
(i) Encrypt the message 233 by the encryption function e(x) = xE (mod n).
(ii) Compute the private key D = E−1 (mod φ(n)). (iii) (2pts) Decrypt the encrypted message in (i).
Page 2 of 2
