In determining whether an odd integer is prime or composite, the author of this blog likes to first look for small prime factors of . If none is found, then calculate the congruence . If this result is not congruent to 1 modulo , this gives a proof that is a composite number. If the result is congruent to 1, then this gives some evidence that is prime. To confirm, apply a formal primality test on the number (e.g. using the Miller-Rabin test). The question we like to ponder in this post is this. Given the result , as evidence for the primality of the number , how strong is it? Could we just use the congruence as a primality test? In this post, we look at these questions from two perspectives, leading to two answers that are both valid in some sense. The discussion is conducted through examining the notions of probable primes and pseudoprimes, both of which are concepts that are related to Fermat’s little theorem. Thus the notions of probable primes and pseudoprimes are related to the Fermat primality test.
Fermat’s little theorem states that if is a prime number, then the following congruence
is always true for any integer that is relatively prime to . A positive integer is said to be a probable prime to the base if the congruence relation (1) holds. Obviously any prime number is a probable prime to all bases that are relatively prime to it (this is another way of stating Fermat’s little theorem). A probable prime does not have to be prime. If is a probable prime to base and if happens not to be prime, then is said to be a pseudoprime to base .
As indicated at the beginning, computing the congruence (1) for just one base is a quick and dirty way of checking probable primality of . Using base 2 as a starting point, if is not congruent to 1 mod , we know is composite for sure. If is congruent to 1 mod , then we can calculate the congruence for several more bases. The following question is similar to the questions at the beginning:
When the congruence (1) is satisfied for one base , is that enough evidence to conclude that is prime?
We look at this question from two angles. One is to answer in terms of an absolute mathematical proof. One is to look at it probabilistically.
The view point of an absolute mathematical proof
In terms of an absolute mathematical proof, the answer to the above question is no. There are probable primes that are composite (i.e. there are pseudoprimes). For example, the integer 341 is a probable prime to base 2 since . But 341 is composite with factors 11 and 31. So 341 is a pseudoprime to the base 2. In fact, 341 is the least integer that is a pseudoprime to base 2. However, 341 is not a pseudoprime to the base 3 since .
Now let be 1105, which obviously is composite since it ends in the digit 5. The number 1105 is a probable prime to both base 2 and base 3, since we have and . In fact, 1105 is the least integer that is a pseudoprime to both base 2 and base 3.
Furthermore, given a base , there are infinitely many pseudoprimes to base . We prove the following theorem.
Let be any integer with . Then there are infinitely many pseudoprimes to base .
Let be an odd prime number such that does not divide and such that does not divide . We define a composite integer such that . We will see that the numbers are distinct for distinct primes . Clearly there are infinitely many odd primes that do not divide both and . The theorem will be established once we provide the details for these claims.
Fix an odd prime such that does not divide and such that does not divide . Define as follows:
The number is composite since it can be expressed as follows:
Note that both factors in the above expression are integers. This is because the numerators can be expressed as:
Furthermore, the number is an odd integer. Note that is the product of the following two numbers and :
Both and are odd numbers. If is even, it is clear that both and are odd. If is odd, each of and is sum of even number of odd numbers plus 1, thus an odd number. Since is the product of two odd numbers, it is an odd number.
Now we need to show that . From the definition of the number (see (*) above), we can derive the following:
The term in the middle of the right hand side is divisible by because of Fermat’s little theorem. Therefore divides . Since does not divide , must divide . Since is odd, must be even. Consequently divides .
From the definition of the number ,we have . This is the same as saying . Since divides , we have too.
It is clear that the numbers are different for different . Since there are infinitely many odd primes that do not divide both and , the theorem is established.
It is interesting that the proof of Theorem 1 is a constructive one. The formula (*) gives us a way to generate pseudoprime to base . For base 2, the first few pseudoprimes from this formula are 341, 5461, 1398101, 22369621. For base 3, the first few pseudoprimes are 91, 7381, 597871, 3922632451. However, the formula (*) does not generate all pseudoprimes for a given base. For example, 561 is a pseudoprime base 2 that is not generated by the formula. There are 19 pseudoprimes base 3 in between 91 and 7381 that are not captured by this formula. For the reason, the formula (*) is useful for proving theorem rather than for computing pseudoprimes.
So from a mathematical standpoint, computing the congruence (1) for one base is not sufficient evidence for primality. There are simply two many counterexamples, in fact infinitely many. So in deciding whether an integer is prime or not, knowing that it is a probable prime to one base is definitely not a proof to the primality of . But this is not the end of the story. There is another view.
The probabilistic view
By Theorem 1, there are infinitely many pseudoprimes to base . So showing that an integer is a probable prime to one base is no proof that is prime. For a given base, even though there are infinitely many pseudoprimes to that base, we will see below that below a given threshold and for a given base, most probable primes are primes and only a minuscule fraction of the probable primes are composite.
Take base 2 as an example. Of all the probable primes base 2 that are less than , how many are primes and how many are composite? According to , there are 21853 pseudoprimes base 2 that are less than . According to the prime number theorem, the number of prime numbers less than is approximately . Therefore there are approximately many primes under . This example illustrates that most probable primes base 2 under are primes and that very few of them are pseudoprimes base 2.
Sticking with base 2, the author of  showed that the number of pseudoprimes to base 2 under is less than
The above bound on pseudoprimes base 2 grows much slower than the quantity , which is taken as the estimate on the number of primes less than . This fact suggests that most probable primes are primes.
Thus the result says a lot. It is not a proof that is prime. But it gives very strong evidence that is likely a prime, especially if the number being tested is a randomly chosen number. This strong evidence can be further corroborated by repeating the calculation of the congruence (1) for a large number of bases, preferably randomly chosen. In the experience of the author of this blog, getting is often a turning point in a search for prime numbers. In primality testing of random numbers , the author has yet come across an instance where is true and the number turns out to be composite.
More on pseudoprimes
The Fermat primality test is to use the congruence relation (1) above to check for the primality or the compositeness of a number. If a number is prime, the Fermat test will always detect its primality. For the Fermat test to be a good test, it needs to be able to detect the compositeness of pseudoprimes.
As discussed in the section on “The probabilistic view”, the probable primes to a given base is the union of two disjoint subsets – the primes and the pseudoprimes to that base. The following is another way to state this fact.
Furthermore, most of the probable primes below a threshold are primes. Thus if we know that a randomly selected number is a probable prime to a given base, it is likely a prime number.
As discussed above, the composite number 341 is a pseudoprime to base 2 but not to base 3. The integer 2047 is a composite numbers since 23 and 89 are its factors. With , the number 2047 is a pseudoprime to the base 2. On the hand, , the number 2047 is not a pseudoprime to the base 3. For the number 1373653, look at the following three congruences:
The above three congruences show that the number 1373653 is a pseudoprime to both bases 2 and 3 but is not a pseudoprime to the base 5. Here’s a larger example. For the number 25326001, look at the following four congruences:
The above four congruences show that the number 25326001 is a pseudoprime to bases 2, 3 and 5 but is not a pseudoprime to the base 7.
In primality testing, the pseudoprimes are the trouble makers. These are the composite numbers that exhibits some prime-like quality. So it may be easy to confuse them with prime numbers. The above examples of pseudoprimes (341, 2047, 1373653, 25326001) happen to be not pseudoprimes to some other bases. For this kind of pseudoprimes, the Fermat test will identify them as composite (if the tester is willing to choose enough bases for testing).
What is troubling about the Fermat test is that there are numbers that are psuedoprimes to all bases that are relatively prime to . These numbers are called Carmichael numbers. For such numbers, the Fermat test will be wrong virtually 100% of the time!
Consider the number 294409.
One might think that the above congruences are strong evidence for primality. In fact, this is a Carmichael number. The factors of 294409 are 37, 73 and 109. The number 294409 is a pseudoprime to all the bases that are relatively prime to 294409. The only way the Fermat test can detect the compositeness of this number is to stumble upon one of its factors. For example, using base 37, we have
For a large Carmichael number (say one with hundreds of digits), it will be hard to randomly stumble on a factor. So there will be virtually a 100% chance that the Fermat test will declare a large Carmichael number as prime if the Fermat test is used. Fortunately Carmichael numbers are rare (see here). If the number being tested is randomly chosen, it will not be likely a Carmichael number. So for the most part, the Fermat test will work well. As discussed above, having the congruence relationship (1) for just one base is quite strong evidence for primality.
- Pomerance C., On the distribution of pseudoprimes, Math. Comp., Volume 37, 587-593, 1981.
- Pomerance C., Selfridge J. L., Wagstaff, S. S., The pseudoprimes to , Math. Comp., Volume 35, 1003-1026, 1980.