Carmichael number

Discovery

The first seven Carmichael numbers, from 561 to 8911, were all found by the Czech mathematician Václav Šimerka in 1885 (thus preceding not just Carmichael but also Korselt, although Šimerka did not find anything like Korselt's criterion). His work, published in Czech scientific journal Časopis pro pěstování matematiky a fysiky, however, remained unnoticed.

Korselt was the first who observed the basic properties of Carmichael numbers, but he did not give any examples.

That 561 is a Carmichael number can be seen with Korselt's criterion. The first seven Carmichael numbers are (sequence A002997 in the OEIS):

${\displaystyle 561=3\cdot 11\cdot 17(2\mid 560;10\mid 560;16\mid 560)}$

${\displaystyle 1105=5\cdot 13\cdot 17(4\mid 1104;12\mid 1104;16\mid 1104)}$

${\displaystyle 1729=7\cdot 13\cdot 19(6\mid 1728;12\mid 1728;18\mid 1728)}$

${\displaystyle 2465=5\cdot 17\cdot 29(4\mid 2464;16\mid 2464;28\mid 2464)}$

${\displaystyle 2821=7\cdot 13\cdot 31(6\mid 2820;12\mid 2820;30\mid 2820)}$

${\displaystyle 6601=7\cdot 23\cdot 41(6\mid 6600;22\mid 6600;40\mid 6600)}$

${\displaystyle 8911=7\cdot 19\cdot 67(6\mid 8910;18\mid 8910;66\mid 8910).}$

In 1910, Carmichael himself also published the smallest such number, 561, and the numbers were later named after him.

Jack Chernick proved a theorem in 1939 which can be used to construct a subset of Carmichael numbers. The number ${\displaystyle (6k+1)(12k+1)(18k+1)}$ is a Carmichael number if its three factors are all prime. Whether this formula produces an infinite quantity of Carmichael numbers is an open question (though it is implied by Dickson's conjecture).

Paul Erdős heuristically argued there should be infinitely many Carmichael numbers. In 1994, W. R. (Red) Alford, Andrew Granville and Carl Pomerance used a bound on Olson's constant to show that there really do exist infinitely many Carmichael numbers. Specifically, they showed that for sufficiently large ⁠${\displaystyle n}$⁠, there are at least ${\displaystyle n^{2/7}}$ Carmichael numbers less than ⁠${\displaystyle n}$⁠.

Thomas Wright proved that if ${\displaystyle a}$ and ${\displaystyle m}$ are relatively prime, then there are infinitely many Carmichael numbers in the arithmetic progression ⁠${\displaystyle a+k\cdot m}$⁠, where ⁠${\displaystyle k=1,2,\dots }$⁠. In 2025, it was shown that any arithmetic progression contains either infinitely many Carmichael numbers or none at all.

It is also known that for any sufficiently large ${\displaystyle N}$, there are infinitely many Carmichael numbers with exactly ${\displaystyle N}$ prime divisors.

In 1992, Löh and Niebuhr found some very large Carmichael numbers, including one with 1101518 factors and over 16 million digits. This has been improved to 10333229505 prime factors and 295486761787 digits, so the largest known Carmichael number is much greater than the largest known prime.

Properties

Factorizations

Carmichael numbers have at least three prime factors. The first Carmichael numbers with ${\displaystyle k=3,4,5,\dots }$ prime factors are (sequence A006931 in the OEIS):

The first Carmichael numbers with 4 prime factors are (sequence A074379 in the OEIS):

The second Carmichael number (1105) can be expressed as the sum of two squares in more ways than any smaller number. The third Carmichael number (1729) is the Hardy-Ramanujan Number: the smallest number that can be expressed as the sum of two cubes (of positive numbers) in two different ways.

Distribution

Let ${\displaystyle C(X)}$ denote the number of Carmichael numbers less than or equal to ⁠${\displaystyle X}$⁠. The distribution of Carmichael numbers by powers of 10 (sequence A055553 in the OEIS):

In 1953, Knödel proved the upper bound for some constant ⁠${\displaystyle k_1}$⁠:

${\displaystyle C(X)<X\exp \left(-k_1{\left(\log X\log \log X\right)}^{\frac{1}{2}}\right)}$

In 1956, Erdős improved this by showing that for some constant ⁠${\displaystyle k_2}$⁠ it holds that

${\displaystyle C(X)<X\exp \left(\frac{-k_2\log X\log \log \log X}{\log \log X}\right)}$

He further gave a heuristic argument suggesting that this upper bound should be close to the true growth rate of ⁠${\displaystyle C(X)}$⁠.

In the other direction, Alford, Granville and Pomerance proved in 1994 that for sufficiently large ${\displaystyle X}$,

${\displaystyle C(X)>X^{2/7}.}$

In 2005, this bound was further improved by Harman to

${\displaystyle C(X)>X^{0.332},}$

who subsequently improved the exponent to ${\displaystyle 0.33336704>1/3}$.

Regarding the asymptotic distribution of Carmichael numbers, there have been several conjectures. In 1956, Erdős conjectured that there were ${\displaystyle X^{1-o(1)}}$ Carmichael numbers for X sufficiently large. In 1981, Pomerance sharpened Erdős' heuristic arguments to conjecture that there are at least

${\displaystyle X\cdot L(X{)}^{-1+o(1)}}$

Carmichael numbers up to ⁠${\displaystyle X}$⁠, where ⁠${\displaystyle L(x)=\exp \left(\frac{\log x\log \log \log x}{\log \log x}\right)}$⁠.

However, inside current computational ranges (such as the count of Carmichael numbers performed by Goutier (sequence A055553 in the OEIS) up to ${\displaystyle {10}^{22}}$), these conjectures are not yet borne out by the data; empirically, the exponent is ${\displaystyle C(X)\approx X^{0.35}}$ for the highest available count (${\displaystyle C(X)=\text{49,679,870}}$ for ${\displaystyle X={10}^{22}}$).

In 2021, Daniel Larsen proved an analogue of Bertrand's postulate for Carmichael numbers first conjectured by Alford, Granville, and Pomerance in 1994. Using techniques developed by Yitang Zhang and James Maynard to establish results concerning small gaps between primes, his work yielded the much stronger statement that, for any ${\displaystyle \delta >0}$ and sufficiently large ${\displaystyle x}$ (in terms of ⁠${\displaystyle \delta }$⁠), there will always be at least

${\displaystyle \exp \left(\frac{\log x}{(\log \log x{)}^{2+\delta }}\right)}$

Carmichael numbers between ${\displaystyle x}$ and

${\displaystyle x+\frac{x}{(\log x{)}^{\frac{1}{2+\delta }}}.}$

Generalizations

The notion of Carmichael number generalizes to a Carmichael ideal in any number field ⁠${\displaystyle K}$⁠. For any nonzero prime ideal ${\displaystyle \mathfrak{p}}$ in ⁠${\displaystyle {\mathcal{O}}_K}$⁠, we have ${\displaystyle {\alpha }^{\mathrm{N}(\mathfrak{p})}\equiv \alpha mod\mathfrak{p}}$ for all ${\displaystyle \alpha }$ in ⁠${\displaystyle {\mathcal{O}}_K}$⁠, where ${\displaystyle \mathrm{N}(\mathfrak{p})}$ is the norm of the ideal ⁠${\displaystyle \mathfrak{p}}$⁠. (This generalizes Fermat's little theorem, that ${\displaystyle m^p\equiv mmodp}$ for all integers ⁠${\displaystyle m}$⁠ when ⁠${\displaystyle p}$⁠ is prime.) Call a nonzero ideal ${\displaystyle \mathfrak{a}}$ in ${\displaystyle {\mathcal{O}}_K}$ Carmichael if it is not a prime ideal and ${\displaystyle {\alpha }^{\mathrm{N}(\mathfrak{a})}\equiv \alpha mod\mathfrak{a}}$ for all ⁠${\displaystyle \alpha \in {\mathcal{O}}_K}$⁠, where ${\displaystyle \mathrm{N}(\mathfrak{a})}$ is the norm of the ideal ⁠${\displaystyle \mathfrak{a}}$⁠. When ⁠${\displaystyle K}$⁠ is ⁠${\displaystyle \mathbf{Q}}$⁠, the ideal ${\displaystyle \mathfrak{a}}$ is principal, and if we let ⁠${\displaystyle a}$⁠ be its positive generator then the ideal ${\displaystyle \mathfrak{a}=(a)}$ is Carmichael exactly when ⁠${\displaystyle a}$⁠ is a Carmichael number in the usual sense.

When ⁠${\displaystyle K}$⁠ is larger than the rationals it is easy to write down Carmichael ideals in ⁠${\displaystyle {\mathcal{O}}_K}$⁠: for any prime number ⁠${\displaystyle p}$⁠ that splits completely in ⁠${\displaystyle K}$⁠, the principal ideal ${\displaystyle p{\mathcal{O}}_K}$ is a Carmichael ideal. Since infinitely many prime numbers split completely in any number field, there are infinitely many Carmichael ideals in ⁠${\displaystyle {\mathcal{O}}_K}$⁠. For example, if ⁠${\displaystyle p}$⁠ is any prime number that is 1 mod 4, the ideal ⁠${\displaystyle (p)}$⁠ in the Gaussian integers ${\displaystyle \mathbb{Z}[i]}$ is a Carmichael ideal.

Both prime and Carmichael numbers satisfy the following equality:

${\displaystyle gcd\left(\sum _{x=1}^{n-1}{x}^{n-1},n\right)=1.}$

Lucas–Carmichael number

A positive composite integer ${\displaystyle n}$ is a Lucas–Carmichael number if and only if ${\displaystyle n}$ is square-free, and for all prime divisors ${\displaystyle p}$ of ⁠${\displaystyle n}$⁠, it is true that ⁠${\displaystyle p+1\mid n+1}$⁠. The first Lucas–Carmichael numbers are:

399, 935, 2015, 2915, 4991, 5719, 7055, 8855, 12719, 18095, 20705, 20999, 22847, 29315, 31535, 46079, 51359, 60059, 63503, 67199, 73535, 76751, 80189, 81719, 88559, 90287, ... (sequence A006972 in the OEIS)

Quasi–Carmichael number

Quasi–Carmichael numbers are square-free composite numbers ⁠${\displaystyle n}$⁠ with the property that for every prime factor ⁠${\displaystyle p}$⁠ of ⁠${\displaystyle n}$⁠, ⁠${\displaystyle p+b}$⁠ divides ⁠${\displaystyle n+b}$⁠ positively with ⁠${\displaystyle b}$⁠ being any integer besides 0. If ⁠${\displaystyle b=-1}$⁠, these are Carmichael numbers, and if ⁠${\displaystyle b=1}$⁠, these are Lucas–Carmichael numbers. The first Quasi–Carmichael numbers are:

35, 77, 143, 165, 187, 209, 221, 231, 247, 273, 299, 323, 357, 391, 399, 437, 493, 527, 561, 589, 598, 713, 715, 899, 935, 943, 989, 1015, 1073, 1105, 1147, 1189, 1247, 1271, 1295, 1333, 1517, 1537, 1547, 1591, 1595, 1705, 1729, ... (sequence A257750 in the OEIS)

Knödel number

An ${\displaystyle n}$-Knödel number for a given positive integer ${\displaystyle n}$ is a composite number ${\displaystyle m}$ with the property that each ⁠${\displaystyle i<m}$⁠ coprime to ${\displaystyle m}$ satisfies ⁠${\displaystyle i^{m-n}\equiv 1(\mathrm{mod}m)}$⁠. The ⁠${\displaystyle n=1}$⁠ case are Carmichael numbers.

Higher-order Carmichael numbers

Carmichael numbers can be generalized using concepts of abstract algebra.

Based on generalized Korselt's criterion, Carmichael number of order ${\displaystyle m}$ can be defined as square-free composite integer ${\displaystyle n}$, such that for every prime divisor ${\displaystyle p}$ of ${\displaystyle n}$ and any ${\displaystyle r\le m}$, there is a positive integer ${\displaystyle i}$ such that ${\displaystyle n\equiv p^i\mathrm{mod}(p^r-1)}$.

The above definition can be restated as: a square-free composite positive integer ${\displaystyle n}$ is Carmichael number of order ${\displaystyle m}$ if and only if the ${\displaystyle n}$th-power-raising function ${\displaystyle p_n}$ is an endomorphism on every ${\displaystyle (\mathbb{Z}/n\mathbb{Z})}$-algebra that can be generated as ${\displaystyle (\mathbb{Z}/n\mathbb{Z})}$-module by ${\displaystyle m}$ elements. For ${\displaystyle m=1}$, it states that ${\displaystyle p_n}$ from the ring ${\displaystyle \mathbb{Z}/n\mathbb{Z}}$ of integers modulo ${\displaystyle n}$ to itself is the identity function. The identity is the only ${\displaystyle (\mathbb{Z}/n\mathbb{Z})}$-algebra endomorphism on ${\displaystyle \mathbb{Z}/n\mathbb{Z}}$ so we can restate the definition as asking that ${\displaystyle p_n}$be an algebra endomorphism of ${\displaystyle (\mathbb{Z}/n\mathbb{Z})}$. As above, ${\displaystyle p_n}$satisfies the same property whenever ${\displaystyle n}$ is prime. Carmichael numbers of order ${\displaystyle m=1}$ are just the ordinary Carmichael numbers.

The ${\displaystyle n}$th-power-raising function ${\displaystyle p_n}$ is also defined on any ${\displaystyle (\mathbb{Z}/n\mathbb{Z})}$-algebra ${\displaystyle \mathbf{A}}$. A theorem states that ${\displaystyle n}$ is prime if and only if all such functions ${\displaystyle p_n}$ are algebra endomorphisms.

An order-2 Carmichael number

According to Howe, ${\displaystyle 17\cdot 31\cdot 41\cdot 43\cdot 89\cdot 97\cdot 167\cdot 331=\text{443,372,888,629,441}}$ is a Carmichael number of order 2.

Properties

Korselt's criterion can be generalized to higher-order Carmichael numbers, as shown by Howe.

A heuristic argument, given in the same paper, appears to suggest that there are infinitely many Carmichael numbers of order ${\displaystyle m}$, for any ${\displaystyle m}$. However, not a single Carmichael number of order 3 or above is known.