Solution
= Solution
For each prime $k\geq5$, choose a prime divisor $p$ of $2^k-1$ and a prime divisor $q\ne3$ of $2^k+1$. Their orders are $k$ and $2k$, respectively, so $p\equiv1\pmod k$, $q\equiv1\pmod{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.