Exercise 2.4.19* (There are infinitely many strong pseudoprimes to the base $a$)

Proof.

a)

We suppose that $k\ge 2$ (congruences modulo 1 are useless). In this case, $m=2^k-1=4\cdot 2^{k-2}-1=4K-1$, where $K=2^{k-2}$ is an integer. Then $d=(m-1)∕2=2K-1$ is odd.

Moreover, $2^{k-1}\equiv 1(\mathit{mod}k)$, so $2^{k-1}=1+\mathit{\lambda k}$ for some integer $\lambda$. Then

$$\begin{array}{llll}\hfill 2^d& =2^{\frac{m-1}{2}}& \hfill & \\ \hfill & =2^{2^{k-1}-1}& \hfill & \\ \hfill & =2^{\mathit{\lambda k}}& \hfill & \\ \hfill & ={\left(2^k\right)}^{\lambda }& \hfill & \\ \hfill & \equiv 1(\mathit{mod}m),& \hfill & \end{array}$$

since $2^k=m+1\equiv 1(\mathit{mod}m)$. This shows that

$$2^d\equiv 1(\mathit{mod}m).$$

b)

If $k$ is composite, by definition $k=\mathit{ab}$, where $1<a<k$. Then $$\begin{array}{llll}\hfill m& =2^{\mathit{ab}}-1& \hfill & \\ \hfill & =(2^a-1)\underset{i=0}{\overset{b-1}{\sum }}{2}^{\mathit{ia}},& \hfill & \end{array}$$

where

$$1<2^1<2^a<2^k,$$

Thus $1<2^a-1<2^k-1$, where $2^a-1\mid m$. This shows that $m$ is composite.

c)

If $k$ is a pseudoprime base $2$, then by definition $k\ge 2$ is composite and $2^{k-1}\equiv 1(\mathit{mod}k)$.

By part (b), $m$ is composite, and by part (a), $m=2d$, where $d$ is odd, and $2^d\equiv 1(\mathit{mod}m)$. By definition (see algorithm p. 78, step 2), $m$ is a strong pseudoprime to the base $2$, i.e. $m$ is a $\mathrm{spsp}(2)$.

If $k$ is a pseudoprime base $2$, then $m=2^k-1$ is a $\mathrm{spsp}(2)$.

d)

If we know that there are infinitely pseudoprimes base $2$ (see below), noting that we have different values of $m$ for different values of $k$ (the map $k\mapsto m=2^k-1$ is injective), there are infinitely many numbers of the class $\mathrm{spsp}(2)$.

e)

Here we recall the proof that there are infinitely many pseudoprimes $m$ to the base $a$ (see Hardy & Wright p. 72 : we give here a slightly modified proof).

Let $a>1$, and $p$ be any odd prime such that $p\nmid a^2-1$.

$$m=\frac{a^{2p}-1}{a^2-1}=\left(\frac{a^p-1}{a-1}\right)\left(\frac{a^p+1}{a+1}\right).$$

Since $p$ is odd( for the third equality),

$$\frac{a^{2p}-1}{a^2-1}=\underset{i=0}{\overset{p-1}{\sum }}{a}^{2i},\frac{a^p-1}{a-1}=\underset{i=0}{\overset{p-1}{\sum }}{a}^i,\frac{a^p+1}{a+1}=\underset{i=0}{\overset{p-1}{\sum }}{(-1)}^i{a}^i$$

are integers. Moreover, $\frac{a^p-1}{a-1}>1$ and $\frac{a^p+1}{a+1}>1$ (because $a>1$), thus $m$ is composite.

Now we show that $2p\mid m-1$

• $m-1=\frac{a^{2p}-a^2}{a^2-1}$. By Fermat theorem, $p\mid a^p-a\mid a^{2p}-a^2=(a^p-a)(a^p+a)$. Hence

  $$p\mid (a^2-1)(m-1),\text{where }p\wedge (a^2-1)=1,$$

  hence

  $$p\mid m-1.$$

• $m-1=a^{2(p-1)}+a^{2(p-2)}+\cdots +a^2$. If $a$ is even, then all terms in this sum are even, so $m-1$ is even. If $a$ is odd, $m-1$ is the sum of $p-1$ odd terms, where $p-1$ is even, thus $m-1$ is even. In both cases,

  $$2\mid m-1.$$

• Since $2\mid m-1$ and $p\mid m-1$, where $p$ is odd, we obtain

  $$2p\mid m-1.$$

Since $(a^2-1)m=a^{2p}-1$, we have

$$a^{2p}\equiv 1(\mathit{mod}m).$$

We know that $2p\mid m-1$, so $m-1=2\mathit{\lambda p}$ for some integer $\lambda$.

Then $a^{m-1}={\left(a^{2p}\right)}^{\lambda }\equiv 1(\mathit{mod}m)$:

$$a^{m-1}\equiv 1(\mathit{mod}m).$$

So the composite $m$ is a pseudoprime to the base $a$.

There are infinitely many primes such that $p\nmid a^2-1$, and the correspondance $p\mapsto m=\frac{a^{2p}-1}{a^2-1}={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=0}^{p-1}{a}^{2i}$ is one-to-one (strictly increasing). Therefore there are infinitely many pseudoprimes to the base $a>1$ (in particular to the base $2$).

By part (d), there are infinitely many numbers of the class $\mathrm{spsp}(2)$.