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 1021 (approximately one in 50 billion numbers). This makes tests based on Fermat's Little Theorem slightly risky compared to others such as the Solovay-Strassen primality test.
Read more about this topic: Carmichael Number