This assignment has a total of
Exercise 5.1
Given a,b,c,d,m ∈ Z, m > 0. Show that
(i) (2pts) Ifa≡b (modm),andd|m,d>0,thena≡b (modd).
(ii) (2pts) Ifa≡b (modm),andc>0,thenac≡bc (modmc) Exercise 5.2
Given a,x,y,m ∈ Z, m > 0. Show that
(i) (2pts) ax≡ay (modm)iffx≡y modgcd(a,m) .
m
(ii) (2pts) Ifax≡ay (modm)andgcd(a,m)=1,thenx≡y (modm).
Exercise 5.3 (2 pts)
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 (6 pts)
Given p ∈ P, show that
(i) (2pts) x2 ≡1 (modp)iffx≡±1 (modp).
(ii) (2 pts) (Wilson’s theorem) (p − 1)! ≡ −1 (mod p). p−1
(iii) (2pts) Ifp≡3 (mod4),then 2 !≡±1 (modp). Exercise 5.5 (2 pts)
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 (6 pts)
Given p, q ∈ P, a ∈ Z, show that
(i) (2pts) Ifaq ≡1 (modp),theneitherp≡1 (modq)ora≡1 (modp).
(ii) (2 pts) If 5 | a and p | a4 + a3 + a2 + a + 1, then p ≡ 1 (mod 5).
(iii) (2 pts) Use (ii) to show that there are infinitely many primes of the form 10n + 1, n ∈ N.
Exercise 5.7 (2 pts)
Find prime factors of F5 = 225 + 1 by applying Fermat’s theorem. Exercise 5.8 (2 pts)
Show that 2021 is not prime by Fermat test. Exercise 5.9 (2 pts)
Sove the following system of linear congruence
Exercise 5.10 (4 pts)
x≡2 (mod4) x≡5 (mod7) x≡0 (mod11) x≡8 (mod15)
(i) (2 pts) Show that 6x ≡ 2 (mod 3) has no solutions.
(ii) (2 pts) Show that 6x ≡ 2 (mod 5) has infinitely many solutions.
Page 1 of 2
Exercise 5.11 (6 pts)
Given public key (n, E) = (323, 95), where 323 = 17 × 19.
(i) (2 pts) Encrypt the message 233 by the encryption function e(x) = xE
(ii) (2 pts) Compute the private key D = E−1 (mod φ(n)). (iii) (2 pts) Decrypt the encrypted message in (i).
(mod n).
Page 2 of 2
