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

Let $b, k \geqslant 2$ be integers. Show that if $N \geqslant 3$ is an odd composite integer dividing $b^{k}-1$ and satisfying $N \equiv 1 \bmod k$, then $N$ is a pseudoprime to base $b$.

(b) Fix $b \geqslant 2$. Let $p$ be an odd prime not dividing $b^{2}-1$, and let

$$n=\frac{b^{p}-1}{b-1} \quad \text { and } \quad m=\frac{b^{p}+1}{b+1} .$$

Use the conclusion of part (a) to show that $N=n m$ is a pseudoprime to base $b$. Deduce that there are infinitely many pseudoprimes to base $b$.

(c) Let $b, k \geqslant 2$ be integers, and let $n=p_{1} \cdots p_{k}$, where $p_{1}, p_{2}, \ldots, p_{k}$ are distinct primes not dividing $2 b$. For each $j=1,2, \ldots, k$, let $r_{j}=n / p_{j}$. Show that $n$ is a pseudoprime to base $b$ if and only if for all $j=1,2, \ldots, k$, the order of $b$ modulo $p_{j}$ divides $r_{j}-1$.

(d) By considering products of prime factors of $2^{k}-1$ and $2^{k}+1$ for primes $k \geqslant 5$, deduce that there are infinitely many pseudoprimes to base 2 with two prime factors.

[Hint: You may assume that $\operatorname{gcd}(j, k)=1$ for $j, k \geqslant 1$ implies $\operatorname{gcd}\left(2^{j}-1,2^{k}-1\right)=1$, and that for $k>3,2^{k}+1$ is not a power of 3.]