Exercise 6.1 Modular Arithmetic
Find each of these values.
a) (−133 mod 23 + 261 mod 23) mod 23 b) (457 mod 23 · 182 mod 23) mod 23
Exercise 6.2 Fermat’s (Little) Theorem Show that 211,213 − 1 is not divisible by 11 .
Exercise 6.3 Euler’s Theorem
1. Compute φ(p2) where p is a prime.
2. Compute φ(pq) where both p and q are primes.
1
Exercise 6.4 Congruences
Find all solutions of the congruence 12x ≡ 27(mod18).
Exercise 6.5 Solving Congruences
What are the solutions of the linear congruence 101x ≡ 583(mod4620)?
Exercise 6.6 Fast Modular Exponentiation
22021 mod 2021
2
Exercise 6.7 Chinese Remainder Theorem Solve the following system of linear congruence
x ≡ 6 x ≡ 13 x ≡ 9 x ≡ 19
(mod11) (mod16)
(mod21) (mod25)
Exercise 6.8 RSA
In an RSA procedure, the public key is chosen as (n, E) = (2077, 97), i.e., the encryption
function e is given by
e(x) = x97 (mod2077)
Compute the private key D, where D = E−1(modφ(n)). Decrypt the message 279 ,
(Note that 2077 = 31 × 67.)
that is, find x if y = e(x) = 279(mod2077).
3
Reference
1. Rosen, Kenneth H., and Kamala Krithivasan. Discrete mathematics and its applica- tions: with combinatorics and graph theory. Tata McGraw-Hill Education, 2012.
2. Fraleigh, John B. A first course in abstract algebra. Pearson Education India, 2003.
4
