Prove that there are infinitely many base 2-pseudoprimes.
If $m$ is a base-2 pseudoprime, then
- $m$ is a composite
- $2^{m-1} \equiv 1 \pmod m$ where $\gcd(m,2)=1$
Let's construct $n$ as
$$n=2^m-1$$
and establish that it is base 2 pseudoprime. To do this we must show
- $n$ is composite
- $2^{n-1} \equiv 1 \pmod n$
Since $m$ is given as composite. we can write it as $m=ab$. The difference of powers identity gives us
$$ n = 2^m-1 = 2^{ab}-1 = (2^a-1) \biggl (2^{a(b-1)}+ 2^{a(b-2)} + \ldots + 2^a + 1 \biggr ) $$
And so $n$ is composite too.
We now consider $2^{n-1} \pmod n$.
We note that $2^{m-1} \equiv 1 \pmod m$ implies $2^m \equiv 2 \pmod m$, or $2^m-2 = km$ for some integer $k$. We also note that $2^m \equiv 1 \pmod n$.
$$ \begin{align} 2^{n-1} & \equiv 2^{2^m-2} \pmod n \\ \\ & \equiv 2^{km} \pmod n \\ \\ & \equiv (2^m)^k \pmod n \\ \\ & \equiv (1)^k \pmod n \\ \\ & \equiv 1 \pmod n \end{align} $$
We've shown $2^{n-1} \equiv 1 \pmod n$.
And so $n=2^m-1$ is also a pseudoprime.
If $m$ is a base 2 pseudoprime, we can always construct another base 2 pseudoprime $n=2^m-1$. Since $n>m$ for $m>1$, we can repeat the process endlessly, and generate endless base 2 pseudoprimes. To complete the argument, we need to show that a pseudoprime greater than 1 exists, and we have already seen 341 is a base 2 pseudoprime.
Note: The author's solution males use of Proposition (4.13) that if $n$ is a base 2 pseudoprime then $2^n-1$ is also a base 2 pseudoprime. This makes the proof much shorter.