A Carmichael number is an odd composite number 
which satisfies Fermat's little theorem
 |
(1)
|
for every choice of 
satisfying 
(i.e., 
and 
are relatively prime)
with 
.
A Carmichael number is therefore a pseudoprime to
any base. Carmichael numbers therefore cannot be found to be composite
using Fermat's little theorem. However,
if 
,
the congruence of Fermat's little theorem
is nonzero, thus identifying a Carmichael number 
as composite.
Carmichael numbers are sometimes called "absolute pseudoprimes" and also satisfy Korselt's criterion. R. D. Carmichael first noted the existence of such numbers in 1910, computed 15 examples, and conjectured that there were infinitely many. In 1956, Erdős sketched a technique for constructing large Carmichael numbers (Hoffman 1998, p. 183), and a proof was given by Alford et al. (1994).
Any solution to Lehmer's totient problem must be a Carmichael number.
The first few Carmichael numbers are 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, ... (OEIS A002997). The number
of Carmichael numbers less than 
, 
, ... are 0, 1, 7, 16, 43, 105, ... (OEIS A055553;
Pinch 1993). The smallest Carmichael numbers having 3, 4, ... factors are 
, 
, 825265, 321197185, ... (OEIS
A006931).
Carmichael numbers have at least three prime factors. For Carmichael numbers with exactly three prime factors, once one of the primes
has been specified, there are only a finite number of Carmichael numbers which can
be constructed. Indeed, for Carmichael numbers with 
prime factors, there are only a finite number with the least
specified.
Numbers of the form 
are Carmichael numbers if each of the factors
is prime (Korselt 1899, Ore 1988, Guy 1994). This
can be seen since for
 |
(2)
|
is a multiple of 
and the least common multiple of 
, 
, and 
is 
, so 
modulo each of the primes 
, 
, and 
, hence 
modulo their product. The first few such Carmichael
numbers correspond to 
, 6, 35, 45, 51, 55, 56, ... (OEIS A046025)
and are 1729, 294409, 56052361, 118901521, ... (OEIS A033502).
Let 
denote the number of Carmichael numbers less than 
. Then, for all sufficiently large 
,
 |
(3)
|
(Alford et al. 1994), which proves that there are infinitely many Carmichael numbers. The upper bound
 |
(4)
|
has also been proved (R. G. E. Pinch).
The Carmichael numbers have the following properties:
1. If a prime 
divides the Carmichael number 
, then 
implies that 
.
2. Every Carmichael number is squarefree.
3. An odd composite squarefree number 
is a Carmichael number iff 
divides the denominator of
the Bernoulli number 
.
The largest known Carmichael numbers having a given number of factors are summarized in the following table (updated from Dubner 1989, 1998).
| factors | digits | discoverer |
| 3 | 60351 | Broadhurst (2002) |
| 4 | 29094 | Broadhurst 2003 (Broadhurst 2015b) |
| 5 | 1015 | Caldwell and Dubner |
| 6 | 19140 | Broadhurst 2003 (Broadhurst 2015a) |
." Math. Comput. 61, 381-391, 1993a.Pinch,
R. G. E. "Some Primality Testing Algorithms." Not. Amer. Math.
Soc. 40, 1203-1210, 1993b.Pinch, R. G. E. 
."
Math. Comput. 35, 1003-1026, 1980.Ribenboim, P.