In number theory, a Carmichael number is a composite positive integer n which satisfies the congruence
for all integers b which are relatively prime to n (see modular arithmetic). They are named for Robert Carmichael. The Carmichael numbers are the Knödel numbers K_{1}.
Contents
Overview
Fermat's little theorem states that all prime numbers have the above property. In this sense, Carmichael numbers are similar to prime numbers; in fact, they are called Fermat pseudoprimes. Carmichael numbers are sometimes also called absolute Fermat pseudoprimes.
Carmichael numbers are important because they pass the Fermat primality test but are not actually prime. Since Carmichael numbers exist, this primality test cannot be relied upon to prove the primality of a number, although it can still be used to prove a number is composite.
Still, as numbers become larger, Carmichael numbers become very rare. For example, there are 20,138,200 Carmichael numbers between 1 and 10^{21} (approximately one in 50 billion numbers.)^{[1]} This makes tests based on Fermat's Little Theorem slightly risky compared to others such as the SolovayStrassen primality test.
Korselt's criterion
An alternative and equivalent definition of Carmichael numbers is given by Korselt's criterion.
It follows from this theorem that all Carmichael numbers are odd, since any even composite number that is squarefree (and hence has only one prime factor of two) will have at least one odd prime factor, and thus p − 1  n − 1 results in an even dividing an odd, a contradiction. (This is also easily seen from the fact that − 1 is a Fermat witness for any even number.)
Discovery
Korselt was the first who observed the basic properties of Carmichael numbers, but he could not find any examples. In 1910, Carmichael found the first and smallest such number, 561, and hence the name "Carmichael number".
Full article ▸
