A fact you should use. Let p be a prime. Then Zp has a generator. Namely g Zp whose powers give all the group. Zp = {1,g,...,gn2}. In particular all the different powers of g give different numbers. 1. Question 1: (a) Define (n k ) = n! k! (n k)! . Show that for a prime p, p divides the number (p k ) . (b) Is it true for non prime numbers? (c) Use (x+y)p = p i=0 (p i ) xi ypi to show that for a prime p, (x+y)p = xp +yp mod p. 2. Question 2: This question is about the Chinese remainder theorem. Say that x = 6 mod 10 x = 4 mod 9 And x = 2 mod 7. Find what is x modulo 10 9 7. 3. Question 3: (a) Consider the group Zp for a prime p with multiplication mod p. Show that (p 1)2 = 1 (mod p) (b) Is the above true for any number (not necessarily prime)? (c) Show that the equation a2 1 = 0, has only two solutions mod p, for a prime p. (d) Consider (p 1)! for a prime p. Show that (p 1)! = 1 (mod p) 4. Question 4: Show that if (n 1)! = 1 (mod n) then n is prime. 5. Question 5: Consider the RSA with p = 11 and q = 29, n = 319 and e = 3. What is the value of d (the inverse of e mod (319))? Show what is the encryption of M = 100.