We show in the previous post that is a strong pseudoprime to base 2 whenever 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.
Let be a prime number that is larger than 5. Then the following number is a strong pseudoprime to base 2.
Proof of Theorem 1
First step is to show that is a composite number. Note that . Then . This means that is divisible by 5. it follows that is an integer. Furthermore, the following product shows that is composite.
One of the above factors is divisible by 5. It is then clear that is composite.
On the other hand, the above factorization of implies that . Furthermore, for any odd integer , we have .
Next the following computes :
where . Since is prime, we have . This means that for some integer . Since 5 divides and is a prime larger than 5, 5 must divides . Thus where . Since is odd, is odd too. Based on one earlier observation, . It follows that is a strong pseudoprime to base 2.
The first several values of are:
The formula captures more strong pseudoprimes than . There are still many strong pseudoprimes that are missing. For example, according to , there are 4842 strong pseudoprimes to base 2 that are less than . The formula captures only 4 of these strong pseudoprimes. However, it is still valuable to have the formula . 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, is the first one on the list that is larger than . Then is an upper bound on the least strong pseudoprime base 2 that is larger than .
It is rare to find strong pseudoprimes to multiple bases. For example, according to , there are only 13 strong pseudoprimes to all of the bases 2, 3 and 5 that are less than . Are there any strong pseudoprimes given by the formula that are also strong pseudoprimes to other bases? What if we just look for pseudoprimes to other bases?
- Pomerance C., Selfridge J. L., Wagstaff, S. S., The pseudoprimes to , Math. Comp., Volume 35, 1003-1026, 1980.