There is a very strong theorem in the paper  that has impactful theoretical results. For example, Theorem 1 in  implies that for any given finite set of bases, there are infinitely many Carmichael numbers that are strong pseudoprimes to all the bases in the given finite set. Another implication of Theorem 1 of  is that there are infinitely many Carmichael numbers that have no small prime factors.
Given an odd number whose “prime versus composite” status is not known, set where and is odd. The number is said to be a probable prime to base if the conclusion of Fermat’s little theorem holds, i.e., . A probable prime to base could be prime or could be composite. If the latter, it is said to be a pseudoprime to base .
The number is said to be a strong probable prime to base if or there exists some such that . In other words, the number is a strong probable prime to base if in the following sequence
the first term is a 1 or there exists a -1 followed by a 1. A strong probable prime to base could be prime or could be composite. If the latter, it is said to be a strong pseudoprime to base .
According to , there are only 4842 strong pseudoprimes to base 2 below . Only 13 of these 4842 numbers are strong pseudoprimes to the bases 2, 3 and 5. The paper  has a listing of all strong pseudoprimes to the bases 2, 3 and 5 that are below . This listing has only 101 numbers. Only 9 these 101 numbers are strong pseudoprimes to bases 2, 3, 5 and 7. So there are indications that strong pseudoprimes are rare and that strong pseudoprimes to several bases are even rarer.
However, there are infinitely many strong pseudoprimes to a given base. In particular, there are infinitely many strong pseudoprimes to base 2 (two proofs are given in this previous post and in this previous post). According to what is said at the beginning of the post, there are infinitely many Carmichael numbers that are strong pseudoprimes to all the first trillion prime bases! Furthermore, for these Carmichael numbers, any prime factors must be larger than the first trillion primes bases! It makes sense to examine this theorem so that we can further understand the implied results. The theorem is obviously a deep theoretical result, established by heavy duty machinery (theoretically speaking).
Fermat’s little theorem implies that if happens to be a prime number, then is a probable prime to all bases that are relatively prime to . It is easy to see that if is a prime number, then is a strong probable prime to all bases that are relatively prime to . Equivalently, if is not a strong probable prime to some base , then is proved to be composite. Such a base is said to be a witness for the compositeness of . So a witness is a base, when used in the calculation for (1), will prove the compositeness of a number. Here’s one reason that the concept of strong pseudoprime is better than the concept of pseudoprime. If is composite, there is at least one base that is a witness for (see this previous post).
A Carmichael number is a composite number such that it is a pseudoprime to all the bases relatively prime to . Thus the Fermat test will never detect the compositeness of Carmichael numbers. On the other hand, the strong probable prime test (the Miller-Rabin test) will likely to give the correct result on Carmichael numbers.
Let be an odd positive composite number. Let denote the smallest witness for the compositeness of . Since any composite number has at least one witness, there is a least one. So is well defined. It is clear that if and only if is a strong pseudoprime to all bases . So any composite number that has a large least witness is a strong pseudoprime to many bases. The following is the statement of Theorem 1 of .
There are infinitely many Carmichael numbers such that
Furthermore, whenever is sufficiently large, the number of such below is at least
We show how Theorem 2 is derived from Theorem 1.
Given a finite set of bases, there are infinitely many Carmichael numbers that are strong pseudoprimes to all the bases in the finite set.
Proof of Theorem 2
Consider the function defined in the right-hand side of the inequality (2) in the statement of Theorem 1. The key facts about this function are that:
- The function is an increasing function for sufficiently large .
- The function is increasing without bound, i.e., for each sufficiently large , there exists an such that .
We use these two facts to derive the intended results. These two key facts will be discussed at the end. By Theorem 1, there exist Carmichael numbers
such that (2) holds for each term in the sequence, i.e., for each . Based on the key facts, the following sequence is increasing without bound.
Let be a finite set of positive integers . Choose some such that for each , is greater than all elements of . Let be the maximum of all the integers in the finite set . Now it is clear that for each , and that . It follows that for each of the following infinitely many Carmichael numbers
the least witness is greater than . Thus all these Carmichael numbers are strong psuedoprimes to all bases , hence to all the bases in the finite set .
To see that the function is increasing pass some sufficiently large , take the derivative of .
The above derivative is positive if and only if the following is true:
This last inequality always holds for sufficiently large . Thus for sufficiently large , the derivative of is positive, meaning that is increasing.
To see that increases without bound, fix a sufficiently large . Choose an integer large enough such that and . Let where . We have the following.
The above derivation shows that the function increases without bound.
Theorem 2 implies the following theorem. For the infinitely many Carmichael numbers that are strong pseudoprimes to all the bases below a bound, no prime numbers within the bound can be a factor for these Carmichael numbers.
There are infinitely many Carmichael numbers that have no small prime factors.
The Carmichael numbers that are claimed to exist by Theorem 3 will likely not be detected as composite by factoring. For example, consider a Carmichael number that is a strong pseudoprime to all the prime bases below . Its compositeness will likely not be detected by factoring based on the current computing technology and on the current factoring algorithms. This is another reason that the strong probable prime test (the Miller-Rabin test) is better than the Fermat test. The latter will declare the Carmichael number in question as prime while the former will likely be correct.
Consider the following 397-digit number.
The above is a 397-digit Carmichael number found in . It is a strong pseudoprime to all the prime bases up to 300. According to Theorem 2, there are infinitely many other Carmichael numbers that are strong pseudoprimes to all the prime bases below 300. The number is generated using the following formula.
- Alford W., Granville A., and Pomerance C., On the difficulty of finding reliable witnesses, L. Adleman and M.-D. Huang, editors, Algorithmic Number Theory: Proc. ANTS-I, Ithaca, NY, volume 877 of Lecture Notes in Computer Science, pages 1–16. Springer–Verlag, 1994.
- Alford W., Granville A., and Pomerance C., There are infinitely many Carmichael numbers, Ann. of Math. 139, 703-722, 1994.
- Arnault F., Constructing Carmichael numbers which are pseudoprimes to several bases, J. Symbolic Computation, 20, 151-161, 1995.
- Jaeschke G., On strong pseudoprimes to several bases, Math. Comp., Volume 61, No. 204, 915-926, 1993.
- Jiang Yupeng, Deng Yingpu, Strong pseudoprimes to the first 9 prime bases, arXiv:1207.0063v1 [math.NT], June 30, 2012.
- Pomerance C., Selfridge J. L., Wagstaff, S. S., The pseudoprimes to , Math. Comp., Volume 35, 1003-1026, 1980.