Worlds of David Darling
Encyclopedia of Science
Home > Encyclopedia of Science

Carmichael number

Also known as an absolute pseudoprime, a number n that is a Fermat pseudoprime to any base, i.e., it divides (an - a) for any a. Another way of saying this is that a Carmichael number is actually a composite number even though Fermat's little theorem suggests it is probably a prime number. (Fermat's little theorem says that if P is a prime number then for any number a, (aP - a) must be divisible by P. Carmichael numbers satisfy this condition to any base despite being composite.)

There are only seven Carmichael numbers under 10,000 – 561, 1105, 1729, 2465, 2821, 6601, and 8911 – and less than a quarter of a million of them under 1016. Nevertheless, in 1994 it was proved that there are infinitely many of them. All Carmichael numbers are the product of at least three distinct primes, for example, 561 = 3 11 17.

Related category