Recall that phi(n) counts all the numbers less than n (and greater than 0) that are relatively prime to n.

1. Practice RSA.

a) Let p=3, let q = 11. Compute n= pq and phi(n).

b) Let e=3, compute the multiplicative inverse of e mod phi(n).

c) Pick a number, a, between 2 and 31, such that (a,n)=1 (that is, a and nare relatively prime). a is your message. Compute a^d mod n.

d) Decode your number by raising it to the eth power and reducing mod n. Does RSA work?

2. Repeat the above steps with $p=7$ and $p=11$.

3. Compute phi(4), phi(8), phi(16), phi(32). Make a conjecture for phi(2^k). Explain why your conjecture works.

4. a) Compute phi(3), phi(4), phi(5), phi(6). Then compute phi(4*3), phi(4*5), phi(5*6), phi(3*5).

b) Now compute phi(4*6), phi(3*6).

c) What patterns do you notice?

5. Explain why phi(p*q) = (p-1)*(q-1) where p and q are primes.

Hint. Try it without the hint first!