Instructions: The quiz is open book (any books) and open notes (any notes or written material).

[1] (a) What is the remainder if you divide 34657863295 by 9? Show your work or explain how you get your answer.

(b) What is the remainder if you divide 3213418 by 5? Show your work or explain how you get your answer.

Solution: (a) Add up the digits and cast out 9's and repeat until you get down to a single digit: 4 is the remainder.

(b) The largest multiple of 5 less than or equal to 3213418 is 3213415, so the remainder is 3.

[2] Decipher the following message, given that it was encrypted using a Caesar cipher (i.e., the letters of the alphabet are just shifted): ju xbt uif cftu pg ujnft, ju xbt uif xpstu pg ujnft.

Solution: We just try various shifts. If we shift back by 1, j becomes i, u becomes t, etc., so we get: it was the best of times, it was the worst of times.

[3] Note that 97 is a prime number.

(a) Find the remainder when you divide 385 = 5*77 by 96.

(b) Compute 45

Solution: (a) Using long division we get 385 = 4*96 + 1, so the remainder is 1.

(b) If we take e = 5 as the encryption exponent with encryption formula y = x

[4] In the cipher using the formula y = x

Solution: We must solve de = 1 mod p-1, where p = 17 and e = 5. Thus we want to solve 5d - m16 = 1 or 5d = 1+16m. So we try various m's until we get 1+16m to be a multiple of 5. We eventually get m = 4: 1 + 4*16 = 65 = 5d so d = 13.

[5] In the RSA cipher using the formula y = x

Solution: We must solve de = 1 mod (p-1)(q-1), where pq = 33 for primes p and q and where e = 3. Thus p = 3 and q = 11, and (p-1)(q-1) = 20. Thus we want to solve 3d - m20 = 1, and we see d = 7, m = 1 works.

[6] For the encryption formula y = x

Solution: You need a prime bigger than 50, so we want p > 50, so we can take p = 53 say. Then we need an exponent e such that gcd(e,52) = 1. Thus we can take any e not divisible by 2 or 13 (since 2*2*13 = 52), say e = 3.

[7] For the encryption formula y = x

Solution: You need a prime bigger than 50, so we want pq > 50, so using p = 5 and q = 11, gives pq=55 > 53. Then we need an exponent e such that gcd(e,(p-1)(q-1)) = 1. But (p-1)(q-1) = 40 = 2*2*2*5, so we can take any e not divisible by 2 or 5, say e = 3.