Quiz # 7 for Dr. Z.’s Number Theory Course for Nov. 7, 2013

NAME: (print!)

E-MAIL ADDRESS: (print!)

1. (3 points) Using the formula, find ϕ(3003).

2. ( 3 points) State and prove Euler’s Classical Formula for the sum-over-divisors of n of ϕ.

3. (4 points) For the following prime p and q (let n = pq) public key e, and encrypted message c (i) Check that e is an OK key, i.e. that it is coprime to ϕ(n). (ii) Find the deciphering key, d, such that de ≡ 1 (mod ϕ(n)) (iii) Suppose Alice sent you the encrypted message c. Check that this is an OK message (coprime to n), and if it is find her original message?, m p = 3 , q = 5 , e = 5 , c = 9