ASSIGNMENT 3

1. Illustrate the proof of Wilson’s Theorem with p = 17.
2. Using Fermat’s Little Theorem, find the remainder when 2^100;000 is divided by 11.
3. Using Euler’s Theorem, find the remainder when 5^100;000 is divided by 18.
4. Show that if n is odd and 3 does not divide n, then n2 = 1 (mod 24).
(Hint: It may help to note that 24 = 3 × 8.)
5. Evaluate ?(n), t (n) and s(n) for each n such that 25 = n = 30.
6. Prove that if n is odd, then t (n) = s(n) (mod 2).
7. Find the primes p and q if n = pq = 14647 and ?(n) = 14400.
8. What is the ciphertext that is produced when the RSA cipher with key e = 3, n =
3763 is used to encipher the message GO?
9. The next meeting of cryptographers will be held in the city of 1739 0923. It is known
that the cipher-text in this message was produced using the RSA cipher key e =
1997, n = 2669. Where will the meeting be held?
10. One of the oldest recorded cipher systems is the Caesar cipher, obtained by using
a cyclic shift of the letters of the alphabet. It is rather primitive compared to the
RSA system, and is easily broken. The following message was sent using this code.
Decipher the message, given that e is the most common letter in English.
UIF DIFFTF JT HPPE
Challenge problem
(a) If n is odd and (n, 5) = 1, show that 5 | (n4 + 4n).
(b) For which positive integers n is n4 + 4n prime?
Hint for (b): Deal with the case n even first. For n odd, factorise n4 + 4n as a product of
two terms by completing squares.