(a) Define the Euler function $\phi(n)$. State the Chinese remainder theorem, and use it to derive a formula for $\phi(n)$ when $n=p_{1} p_{2} \ldots p_{r}$ is a product of distinct primes. Show that there are at least ten odd numbers $n$ with $\phi(n)$ a power of 2 .

(b) State and prove the Fermat-Euler theorem.

(c) In the RSA cryptosystem a message $m \in\{1,2, \ldots, N-1\}$ is encrypted as $c=m^{e}$ $(\bmod N)$. Explain how $N$ and $e$ should be chosen, and how (given a factorisation of $N$ ) to compute the decryption exponent $d$. Prove that your choice of $d$ works, subject to reasonable assumptions on $m$. If $N=187$ and $e=13$ then what is $d$ ?