This is an introduction to Carmichael numbers. We first discuss Carmichael numbers in the context of Fermat primality test and then discuss several basic properties. We also prove Korselt’s criterion, which gives a useful characterization of Carmichael numbers.
___________________________________________________________________________________________________________________
Fermat Primality Test
Fermat’s little theorem states that if is a prime number, then for any integer . Fermat primality test refers to the process of using Fermat little theorem to check the “prime vs. composite” status of an integer.
Suppose that we have a positive integer such that the “prime vs. composite” status is not known. If we can find an integer such that , then we know for certain that the modulus is composite (or not prime). For example, let . Note that . So we know right away that is not prime, even though we do not know what its prime factors are just from applying this test.
Given a positive integer , whenever , we say that is a Fermat witness for (the compositeness of) the integer . Thus is a Fermat witness for .
What if we try one value of and find that is not a witness for (the compositeness of) ? Then the test is inconclusive. The best we can say is that is probably prime. It makes sense to try more values of . If all the values of we try are not witnesses for (i.e. for all the values of we try), then it “seems likely” that is prime. But if we actually declare that is prime, the decision could be wrong!
Take . For several randomly chosen values of , we have the following calculations:
The above calculations could certainly be taken as encouraging signs that is prime. With more values of , we also find that . However, if we declare that is prime, it turns out to be a wrong conclusion.
In reality, is composite with . Furthermore for any integer . So there are no witnesses for . Any composite positive integer that has no Fermat witnesses is called a Carmichael number, in honor of Robert Carmichael who in 1910 found the smallest such number, which is 561.
Fermat primality test is always correct if the conclusion is that the integer being tested is a composite number (assuming there is no computational error). If the test says the number is composite, then it must be a composite number. In other words, there are no false negatives in using Fermat primality test as described above.
On the other hand, there can be false positives as a result of using Fermat primality test. If the conclusion is that the integer being tested is a prime number, it is possible that the conclusion is wrong. For a wrong conclusion, it could be that there exists a witness for the number being tested and that we have missed it. Or it could be that the number being tested is a Carmichael number. Though Carmichael numbers are rare but there are infinitely many of them. So we cannot ignore them entirely. For these reasons, Fermat primality test as described above is often not used. Instead, other extensions of the Fermat primality test are used.
___________________________________________________________________________________________________________________
Carmichael Numbers
As indicated above, a Carmichael number is a positive composite integer that has no Fermat witnesses. Specifically, it is a positive composite integer that satisfies the conclusion of Fermat’s little theorem. In other words, a Carmichael number is a positive composite integer such that for any integer .
Carmichael numbers are rare. A recent search found that there are Carmichael numbers between and , about one in 50 trillion numbers (documented in this Wikipedia entry on Carmichael numbers). However it was proven by Alford, Granville and Pomerance in 1994 that there are infinitely many Carmichael numbers (paper).
The smallest Carmichael number is . A small listing of Carmichael numbers can be found in this link, where the example of is found.
Carmichael numbers must be odd integers. To see this, suppose is a Carmichael number and is even. Let . By condition (1) of Theorem 1, we have . On the other hand, . Thus . Thus we have . It must be the case that , contradicting the fact that is a composite number. So any Carmichael must be odd.
The following theorem provides more insight about Carmichael numbers. A positive integer is squarefree if its prime decomposition contains no repeated prime factors. In other words, the integer is squarefree means that if is the prime factorization of , then all exponents .
-
Theorem 1 (Korselt’s Criterion)
- The condition holds for any integer .
- The condition holds for any integer that is relatively prime to .
- The integer is squarefree and for any prime divisor of .
-
Let be a positive composite integer. Then the following conditions are equivalent.
Proof of Theorem 1
Suppose that is relatively prime to the modulus . Then let be the multiplicative inverse of modulo , i.e., . By (1), we have . Multiply both sides by the multiplicative inverse , we have .
Let be the prime factorization of where for and each exponent . Since must be odd, each must be an odd prime.
We first show that each , thus showing that is squarefree. To this end, for each , let be a primitive root modulo (see Theorem 4 in the post Primitive roots of powers of odd primes). Consider the following system of linear congruence equations:
Since the moduli are pairwise relatively prime, this system must have a solution according to the Chinese Remainder Theorem (a proof is found here). Let one such solution. For each , since is a primitive root modulo , is relatively prime to . Since , is relatively prime to for each . Consequently, is relatively prime to . By assumption (2), we have .
Now fix a with . We show that . Since , . Since , we have . Note that the order of modulo is . Thus we have . If , then , which would mean that . So it must be the case that . It then follows that .
Suppose that is a product of distinct prime numbers such that for each , .
Let be any integer. First we show that for all . It then follows that .
Now fix a with . First consider the case that and are relatively prime. According to Fermat’s little theorem, . Since , . By the Chinese Remainder Theorem, it follows that and .
Examples
With Korselt’s criterion, it is easy to verify Carmichael numbers as long as the numbers are factored. For example, the smallest Carmichael number is . The number is obviously squarefree. furthermore is divisible by , and .
The number is discussed above. We can also verify that this is a Carmichael number: , and .
Here’s three more Carmichael numbers (found here):
We end the post by pointing out one more property of Carmichael numbers, that Carmichael numbers must have at least three distinct prime factors. To see this, suppose that is a Carmichael number with two distinct prime factors and . We can express as follows:
Since is Carmichael, . So for some integer . Plugging this into the above equation, we see that . By symmetry, we can also show that . Thus , a contradiction. So any Carmichael must have at least three prime factors.
___________________________________________________________________________________________________________________
I am currently taking computational number theory and have been working with Carmichael numbers recently! Very fun!
Pingback: Counting Fermat witnesses | Exploring Number Theory
Pingback: A Good Will Hunting Story from China | Math in the Spotlight