# A formula for generating strong pseudoprimes

We show in the previous post that $2^n-1$ is a strong pseudoprime to base 2 whenever $n$ is a pseudoprime to base 2. This formula establishes that there are infinitely many strong pseudoprime to base 2. Since the smallest pseudoprime to base 2 is 341, the smallest possible strong pseudoprime given by this formula is a 103-digit number. In this post, we discuss another formula that will generate some of the smaller strong pseudoprimes to base 2. We prove the following theorem.

Theorem 1
Let $p$ be a prime number that is larger than 5. Then the following number is a strong pseudoprime to base 2.

$\displaystyle M_p=\frac{4^p+1}{5}$

Proof of Theorem 1
First step is to show that $M_p$ is a composite number. Note that $4 \equiv -1 \ (\text{mod} \ 5)$. Then $4^p \equiv (-1)^p \equiv -1 \ (\text{mod} \ 5)$. This means that $4^p+1$ is divisible by 5. it follows that $M_p$ is an integer. Furthermore, the following product shows that $4^p+1$ is composite.

$\displaystyle 4^p+1=(2^p-2^{\frac{p+1}{2}}+1) \cdot (2^p+2^{\frac{p+1}{2}}+1)$

One of the above factors is divisible by 5. It is then clear that $M_p$ is composite.

On the other hand, the above factorization of $4^p+1$ implies that $2^{2p} \equiv -1 \ (\text{mod} \ M_p)$. Furthermore, for any odd integer $t$, we have $2^{2 \cdot p \cdot t} \equiv -1 \ (\text{mod} \ M_p)$.

Next the following computes $M_p-1$:

$\displaystyle M_p-1=\frac{4^p+1}{5}-1=\frac{4^p-4}{5}=4 \cdot \frac{4^{p-1}-1}{5}=2^2 \cdot q$

where $\displaystyle q=\frac{4^{p-1}-1}{5}$. Since $p$ is prime, we have $4^{p-1} \equiv 1 \ (\text{mod} \ p)$. This means that $4^{p-1}-1=p \cdot k$ for some integer $k$. Since 5 divides $p \cdot k$ and $p$ is a prime larger than 5, 5 must divides $k$. Thus $q=p \cdot t$ where $k=5t$. Since $q$ is odd, $t$ is odd too. Based on one earlier observation, $\displaystyle 2^{2 \cdot q} \equiv 2^{2 \cdot p \cdot t} \equiv -1 \ (\text{mod} \ M_p)$. It follows that $M_p$ is a strong pseudoprime to base 2. $\blacksquare$

___________________________________________________________________

Examples

The first several values of $M_p$ are:

$M_{7}=$ 3277

$M_{11}=$ 838861

$M_{13}=$ 13421773

$M_{17}=$ 3435973837

$M_{19}=$ 54975581389

$M_{23}=$ 14073748835533

$M_{29}=$ 57646075230342349

The formula $M_p$ captures more strong pseudoprimes than $2^n-1$. There are still many strong pseudoprimes that are missing. For example, according to [1], there are 4842 strong pseudoprimes to base 2 that are less than $25 \cdot 10^9$. The formula $M_p$ captures only 4 of these strong pseudoprimes. However, it is still valuable to have the formula $M_p$. It gives a concrete proof that there exist infinitely many strong pseudoprimes to base 2. Strong pseudoprimes are rare. It is valuable to have an explicit formula to generate examples of strong pseudoprimes. For example, $M_{19}$ is the first one on the list that is larger than $25 \cdot 10^9$. Then $M_{19}$ is an upper bound on the least strong pseudoprime base 2 that is larger than $25 \cdot 10^9$.

___________________________________________________________________

Question

It is rare to find strong pseudoprimes to multiple bases. For example, according to [1], there are only 13 strong pseudoprimes to all of the bases 2, 3 and 5 that are less than $25 \cdot 10^9$. Are there any strong pseudoprimes given by the formula $M_p$ that are also strong pseudoprimes to other bases? What if we just look for pseudoprimes to other bases?

___________________________________________________________________

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 \ \text{Dan Ma}$