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
every base relatively prime to it. For such bases,
Fermat's little theorem does not identify
a Carmichael number as composite. If 
, then 
is nonzero modulo 
, thus identifying 
as a composite number.
Carmichael numbers are sometimes called "absolute pseudoprimes" and also satisfy Korselt's criterion. Carmichael (1910, pp. 237-238) gave four examples of such numbers. Carmichael (1912, pp. 26-27) listed 15 examples and suggested that there are infinitely many. Hoffman (1998, p. 183) reports that Erdős sketched a technique for constructing large Carmichael numbers in 1956. Alford et al. (1994) proved that there are infinitely many Carmichael numbers.
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 1993a). 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.
For a positive integer 
, numbers of the form 
are Carmichael numbers if each of the factors is prime (Chernick
1939, Ore 1988, Guy 1994). This can be seen since for
 |
(2)
|
is a multiple of 
and the least common multiple of 
, 
, and 
is 
, so for 
relatively prime to 
, 
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. For each fixed 
, Pomerance et al. (1980, p. 1013) proved
the upper bound
 |
(4)
|
for all sufficiently large 
depending on 
.
Larsen (2023) proved Bertrand's postulate for Carmichael numbers, which guarantees a Carmichael number between
and 
for every sufficiently large 
and gives the stronger short-interval
bound stated there.
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 
.
Another characterization is obtained by writing the Bernoulli number 
in lowest terms and defining 
to be the denominator in
lowest terms of 
.
The values of 
for 
,
2, ... begin 1, 1, 1, 16, 1, 36, 1, 64, 27, 100, ... (OEIS A309132).
For composite 
, the number 
is squarefree iff 
is a Carmichael number (Adamczewski 2026).
An AI-generated proof formally verified in Lean reduces the result, by analysis at
each prime, to Korselt's
criterion using the von Staudt-Clausen
theorem.
Historical reports of large Carmichael numbers with specified numbers of prime factors are summarized in the following table.
| factors | digits | discoverer |
| 3 | 60351 | Broadhurst (2002) |
| 4 | 29094 | Broadhurst 2003 (Broadhurst 2015b) |
| 5 | 1015 | Dubner (1998) |
| 6 | 19140 | Broadhurst 2003 (Broadhurst 2015a) |
Which Satisfy the Fermat Congruence 
mod 
." Amer. Math. Monthly 19, 22-27, 1912.
." 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.