Homework 6 (assigned July 29, due August 4)

Reading: Rosen chapter 3, sections 3.4–3.7.

Written assignment : Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in. Note: You are responsible for the material covered in both "Do" exercises and assigned problems.

"Do" Exercises (not to be handed in):

1. Exercises 25 and 31c on Rosen page 209.
2. Exercises 2b, 2c, and 4a, 4c, and 4d on Rosen page 229.
3. Exercises 24c and 24d on Rosen page 230.
4. Exercises 19 and 29 on Rosen page 245.

Assigned problems (to be handed in):

1. For each of the following, state whether a has an inverse modulo m. If none exists, prove it using facts from class. If it has an inverse, find the inverse using Euclid's algorithm (or Euclid's extended algorithm). Show the intermediate steps of the algorithm. (5 points each)
   1. a = 22, m = 36.
   2. a = 77, m = 92.

2. Compute 13²⁴ (mod 25). Show your work. (5 points)

3. True or false? If true, give a proof. If false, give a counterexample. (5 points each)
   1. If p is a prime number, then every integer a where 0 < a < p has an inverse mod p.
   2. If p is a prime number, then p has an inverse mod n for every integer n > 1.

4. Exercise 28a and 28b on Rosen page 245. (5 points)

5. Find the unique solution to each of the following sets of congruences. (5 points each)
   1. x ≡ 12 (mod 3)
      x ≡ 4 (mod 7)
      x ≡ 15 (mod 11)
   2. 3x ≡ 2 (mod 5)
      2x ≡ 1 (mod 3)
      (Hint: First put congruences in the form x ≡ a (mod m).)

6. Consider an RSA key set with p = 7, q = 11, N = 77, and e = 13. What value should be used for the secret key d? What is the encryption of the message m = 27 with these keys? (5 points)

7. In an RSA crptosystem, p = 47 and q = 59. Find appropriate encryption and decryption keys e and d. (5 points)