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.
One way to construct Carmichael numbers is to fix a positive even number
and form products of distinct primes
for which
divides
and
does not divide
. Any composite
product
with
satisfies Korselt's criterion. Zhang (2011)
counted these products when
is the product of the first
primes. For example, he found
for
. Zhang (2015) studied the counts for other choices
of
.
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) |
Randrianantenaina and Uncu (2026) proved that 1729 is the only Carmichael number of the form , where
is prime and
is an integer. It occurs
for
and
.
Let
denote the smallest Carmichael number with exactly
prime factors. Webster and
Webster (2026) report computing
for every
by exhaustive searches. Their algorithm
enumerates a partial product
of prime factors and, once
, recovers all remaining factors from
at most one possible cofactor, where
is the search bound and
is the Carmichael
function. Under the hypothesis
, its expected
running time is
, where
is the
th prime number,
is the Chebyshev
function, and
is big-O notation. The reported exact values come
from finite exhaustive searches and do not assume this asymptotic hypothesis. Webster
and Webster (2026) attribute the search implementation and much of the asymptotic
analysis and its proofs to Claude under their direction,
and state that they checked the analysis.
Every Carmichael number also satisfies
, where
is the totient function.
More generally, this condition characterizes the positive integers
for which every group of order
is cyclic. Webster and Webster (2026, Section 6) report
computing the least such integer
with exactly
prime factors for
, giving a comparison bound
for
. For
, 1, 2, ..., the values of
begin 1, 2, 15, 255, 5865, ... (OEIS A264907).
For
, they report that the prime
factors of
cannot be obtained by choosing a first prime and then repeatedly adjoining the least
larger prime that preserves
. Thus this greedy
construction need not produce
.