Pseudoprimes are rare. Strong pseudoprimes are rarer still. According to , there are 21853 pseudoprimes to base 2 and 4842 strong pseudoprimes to base 2 below . 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.
For a given base , there are infinitely many strong pseudoprimes to base .
For a proof, see Theorem 1 in . We give a simpler proof that there exist infinitely many strong pseudoprimes to base 2.
There are infinitely many strong pseudoprimes to base 2.
Proof of Theorem 1a
We make the following claim.
Let be a pseudoprime to base 2. Then 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 . Once the above claim is established, we have a proof that there are infinitely many strong pseudoprimes to base 2.
First of all, if is composite, the number is also composite. This follows from the following equalities.
Thus is composite. Note that . Let , which is an odd integer. Because is a pseudoprime to base 2, . Equivalently, for some integer . Furthermore, it is clear that .
It follows that . This means that 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 . In particular there are infinitely many pseudoprimes to base 2. It follows that the formula gives infinitely many strong pseudoprimes to base 2.
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 .
Even though 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 for other bases, note that where is the following 103-digit number.
Calculate and modulo . Look for the pattern and or the pattern pattern and . If either pattern appears, then is a strong pseudoprime to base . See the sequence labeled (1) in the previous post on strong pseudoprimes.
Verify that is not a strong pseudoprime to both bases 3 and 5.
- Pomerance C., Selfridge J. L., Wagstaff, S. S., The pseudoprimes to , Math. Comp., Volume 35, 1003-1026, 1980.
Revised July 4, 2015