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



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.



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?



  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}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s