 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.