Problem Statement
Let $C(x)$ count the number of Carmichael numbers in the interval $[1,x]$. Is it true that $C(x)=x^{1-o(1)}$?
Categories:
Number Theory
Progress
Erdős [Er56c] proved\[C(x) < x \exp\left(-c \frac{\log x\log\log\log x}{\log\log x}\right)\]for some constant $c>0$. Pomerance [Po89] gave a heuristic suggesting that this is the true order of growth, and in fact\[C(x)= x \exp\left(-(1+o(1))\frac{\log x\log\log\log x}{\log\log x}\right).\]Alford, Granville, and Pomerance [AGP94] proved that $C(x)\to \infty$, and in fact $C(x)>x^{2/7}$ for large $x$. The lower bound\[C(x)> x^{0.33336704}\]was proved by Harman [Ha08]. This exponent was improved to $0.3389$ by Lichtman [Li22].Korselt observed that $n$ being a Carmichael number is equivalent to $n$ being squarefree and $p-1\mid n-1$ for all primes $p\mid n$.
This is discussed in problem A13 of Guy's collection [Gu04].
Source: erdosproblems.com/1057 | Last verified: January 19, 2026