Carmichael number

While Fermat's Little Theorem provides an exellent test for determining the primality of a number, some numbers pass this test when compared to all numbers smaller than and relatively prime to them, but are not prime. These Carmichael numbers are extremely rare. The third one is 1729. Prime-generation can be sped up fantastically by using a pregenerated list of Carmichael numbers.

A Carmichael number is defined as a composite number n with the property that:

aⁿ ≡ a (mod n) for every integer a such that 1 ≤ a ≤ n

Thus, it is a composite number that has no witness for compositeness. As such, when testing for primality by applying Fermat's Little Theorem, Carmichael numbers are indistinguishable from prime numbers.

Every Carmichael number is odd and a product of distinct prime numbers.

561, 1105, 1729, 2465, 2821, 6601, 8911 is a complete list of all Carmichael numbers up to 10000.

To check if a certain number is a Carmichael number, simply look at its prime decomposition and check against Korselt's Criterion for Carmichael Numbers.

(Named in honor of R. D. Carmichael, who noted fifteen such numbers in 1910.)