Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 4 / 11I (Number Theory)

$N$ is a Fermat pseudoprime to base $b$ when it is composite, coprime to $b$, and $b^{N-1}\equiv 1(\mathrm{mod}N)$. Here $N\mid b^k-1$ gives coprimality and $k\mid N-1$, so $b^{N-1}=(b^k{)}^{(N-1)/k}\equiv 1(\mathrm{mod}N)$.

Both $n$ and $m$ divide $b^{2p}-1$, hence so does $N=nm$ after checking $\gcd (n,m)=1$ under the hypothesis. Also $n\equiv p(\mathrm{mod}b-1)$ and the elementary factorization gives $N\equiv 1(\mathrm{mod}2p)$; part (a) with $k=2p$ applies. As odd primes $p$ grow, $N$ grows, yielding infinitely many examples.

By the Chinese remainder theorem, $b^{n-1}\equiv 1(\mathrm{mod}n)$ iff it holds modulo every $p_j$. Since $n-1=p_j{r}_j-1\equiv r_j-1(\mathrm{mod}{p}_j-1)$ and the order of $b$ modulo $p_j$ divides $p_j-1$, this is equivalent to ${\mathrm{ord}}_{p_j}(b)\mid r_j-1$ for every $j$.

For each prime $k\ge 5$, choose a prime divisor $p$ of $2^k-1$ and a prime divisor $q\ne 3$ of $2^k+1$. Their orders are $k$ and $2k$, respectively, so $p\equiv 1(\mathrm{mod}k)$, $q\equiv 1(\mathrm{mod}2k)$, and the criterion in part (c) shows $pq$ is a base-two pseudoprime. The supplied gcd fact makes examples from distinct prime $k$ distinct, so there are infinitely many.