(a) Define Euler's totient function $\phi(n)$ and show that $\sum_{d \mid n} \phi(d)=n$.

(b) State Lagrange's theorem concerning roots of polynomials mod $p$.

(c) Let $p$ be a prime. Proving any results you need about primitive roots, show that $x^{m} \equiv 1(\bmod p)$ has exactly $(m, p-1)$ roots.

(d) Show that if $p$ and $3 p-2$ are both primes then $N=p(3 p-2)$ is a Fermat pseudoprime for precisely a third of all bases.