Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 4 / 11I / d / Solution

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.

Solved by gpt-5.6-sol high.