Carmichael Numbers
Definition 1
An integer is called a Carmichael number if for all , it satisfies .
Theorem
Every Carmichael number is a product of distinct primes, except for .
Description
Carmichael numbers are composite numbers that pass the Fermat’s Little Theorem, meaning they appear to be prime. For example, is a composite number, but always holds.
Meanwhile, the Miller-Rabin primality test is available to catch such Carmichael numbers.
Proof
Let’s say is a Carmichael number.
Part 1. If we set , then because of , we have The above congruence holds only when is odd.
Part 2. Suppose is represented by for primes excluding . Let’s set and show that . Let’s denote the prime corresponding to as .
Since is a Carmichael number, we have , and must divide . Also, since one of the divisors of was , must divide . Thus, This implies that it is an integer, which is only possible when in the numerator makes .
■
Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition): p133. ↩︎