# There are infinitely many strong pseudoprimes

Pseudoprimes are rare. Strong pseudoprimes are rarer still. According to [1], there are 21853 pseudoprimes to base 2 and 4842 strong pseudoprimes to base 2 below $25 \cdot 10^9$. According to the prime number theorem, there are over 1 billion prime numbers in the same range. When testing a random number, knowing that it is a strong probable prime to just one base is strong evidence for primality. Even though most of the strong probable primes are prime, for a given base, there exist infinitely many strong pseudoprimes. This fact is captured in the following theorem.

Theorem 1
For a given base $a>1$, there are infinitely many strong pseudoprimes to base $a$.

For a proof, see Theorem 1 in [1]. We give a simpler proof that there exist infinitely many strong pseudoprimes to base 2.

Theorem 1a
There are infinitely many strong pseudoprimes to base 2.

Proof of Theorem 1a
We make the following claim.

Claim
Let $n$ be a pseudoprime to base 2. Then $N=2^n-1$ is a strong pseudoprime to base 2.

In a previous post on probable primes and pseudoprimes, we prove that there exist infinitely pseudoprimes to any base $a$. Once the above claim is established, we have a proof that there are infinitely many strong pseudoprimes to base 2.

First of all, if $n$ is composite, the number $2^n-1$ is also composite. This follows from the following equalities.

$\displaystyle 2^{ab}-1=(2^a-1) \cdot (1+2^a+2^{2a}+2^{3a}+ \cdots+2^{(b-1)a})$

$\displaystyle 2^{ab}-1=(2^b-1) \cdot (1+2^b+2^{2b}+2^{3b}+ \cdots+2^{(a-1)b})$

Thus $N=2^n-1$ is composite. Note that $N-1=2^n-2=2 \cdot (2^{n-1}-1)$. Let $q=2^{n-1}-1$, which is an odd integer. Because $n$ is a pseudoprime to base 2, $2^{n-1} \equiv 1 \ (\text{mod} \ n)$. Equivalently, $2^{n-1}-1=nj$ for some integer $j$. Furthermore, it is clear that $2^{n} \equiv 1 \ (\text{mod} \ 2^n-1)$.

It follows that $\displaystyle 2^q \equiv 2^{2^{n-1}-1} \equiv 2^{nj} \equiv 1^j \equiv 1 \ (\text{mod} \ N)$. This means that $N$ is a strong pseudoprime to base 2.

In the previous post probable primes and pseudoprimes, it is established that there are infinitely many pseudoprimes to any base $a$. In particular there are infinitely many pseudoprimes to base 2. It follows that the formula $2^n-1$ gives infinitely many strong pseudoprimes to base 2. $\blacksquare$

___________________________________________________________________

Example

Theorem 1a can be considered a formula for generating strong pseudoprimes to base 2. The input is a pseudoprime to base 2. Unfortunately the generated numbers get large very quickly and misses many strong pseudoprimes to base 2.

The smallest pseudoprime to base 2 is 341. The following is the 103-digit $N=2^{341}-1$.

$N=2^{341}-1=$
44794894843556084211148845611368885562432909944692
99069799978201927583742360321890761754986543214231551

Even though $N=2^{341}-1$ is a strong pseudoprime to base 2, it is not strong pseudoprime to bases 3 and 5. In fact, it is rare to find a strong pseudoprime to multiple bases. To determine the strong pseudoprimality of $N$ for other bases, note that $N-1=2 \cdot Q$ where $Q$ is the following 103-digit number.

$Q=$
22397447421778042105574422805684442781216454972346
49534899989100963791871180160945380877493271607115775

Calculate $a^Q$ and $a^{2Q}$ modulo $N$. Look for the pattern $a^Q=1$ and $a^{2Q}=1$ or the pattern pattern $a^Q=-1$ and $a^{2Q}=1$. If either pattern appears, then $N$ is a strong pseudoprime to base $a$. See the sequence labeled (1) in the previous post on strong pseudoprimes.

___________________________________________________________________

Exercise

Verify that $N=2^{341}-1$ is not a strong pseudoprime to both bases 3 and 5.

___________________________________________________________________

Reference

1. Pomerance C., Selfridge J. L., Wagstaff, S. S., The pseudoprimes to $25 \cdot 10^9$, Math. Comp., Volume 35, 1003-1026, 1980.

___________________________________________________________________
$\copyright \ \ 2014-2015 \ \text{Dan Ma}$
Revised July 4, 2015