(a) State and prove the Fermat-Euler theorem. Let $p$ be a prime and $k$ a positive integer. Show that $b^{k} \equiv b(\bmod p)$ holds for every integer $b$ if and only if $k \equiv 1(\bmod p-1)$.

(b) Let $N \geqslant 3$ be an odd integer and $b$ be an integer with $(b, N)=1$. What does it mean to say that $N$ is a Fermat pseudoprime to base $b$ ? What does it mean to say that $N$ is a Carmichael number?

Show that every Carmichael number is squarefree, and that if $N$ is squarefree, then $N$ is a Carmichael number if and only if $N \equiv 1(\bmod p-1)$ for every prime divisor $p$ of $N$. Deduce that a Carmichael number is a product of at least three primes.

(c) Let $r$ be a fixed odd prime. Show that there are only finitely many pairs of primes $p, q$ for which $N=p q r$ is a Carmichael number.

[You may assume throughout that $\left(\mathbb{Z} / p^{n} \mathbb{Z}\right)^{*}$ is cyclic for every odd prime $p$ and every integer $n \geqslant 1 .]$