Lehmer's totient problem

For a prime $p$, Euler's totient $\varphi(p) = p - 1$ divides $p - 1$. Lehmer asked in 1932 whether this can ever happen for a composite number. No example is known, and any example would have to be odd, squarefree, enormous and built from many primes; a single example would be checkable instantly.

Problem

Euler's totient $\varphi(n)$ counts the integers $1 \le m \le n$ with $\gcd(m, n) = 1$. If $n$ is prime then $\varphi(n) = n - 1$, so $\varphi(n)$ divides $n - 1$.

Is there a composite number $n > 1$ such that $\varphi(n)$ divides $n - 1$?

Background

D. H. Lehmer posed the question in 1932 and conjectured that no such $n$ exists, so that the divisibility $\varphi(n) \mid n - 1$ would characterise the primes. A composite solution would have to be a Carmichael number: since the exponent of the multiplicative group modulo $n$ divides $\varphi(n)$, it would divide $n - 1$, so $a^{n-1} \equiv 1 \pmod n$ for every $a$ coprime to $n$. The problem therefore sits close to the theory of Fermat pseudoprimes and primality testing.

What is known

• Lehmer (1932): a composite solution must be odd and squarefree, with at least seven distinct prime factors.
• Cohen and Hagis (1980): a solution has at least 14 distinct prime factors.
• Burcsi, Czirbusz and Farkas (2011), by computation: if $3$ divides a solution $n$, then $n > 10^{360000000}$ and $n$ has at least $40000000$ distinct prime factors.
• Burek and Żmija (2019): an upper bound for any solution in terms of its number of distinct prime factors.

What would count as progress

• A composite $n$ with $\varphi(n) \mid n - 1$. Given its factorisation, this is checked in moments.
• Stronger lower bounds on the number of prime factors, or on the size, of a solution, with the computations published so that they can be rerun.
• Bounds on the number of solutions up to $x$, or proofs that no solution lies in natural families such as products of primes of a special form.
• A formal proof, or disproof, of the Lean statement lehmer_totient in Wikipedia/LehmerTotient.lean. Formalising the classical restrictions (odd, squarefree, at least seven prime factors) would also be useful.

References

1. D. H. Lehmer, On Euler's totient function, Bull. Amer. Math. Soc. 38 (1932), 745–751.
2. P. Burcsi, S. Czirbusz and G. Farkas, Computational investigation of Lehmer's totient problem, Ann. Univ. Sci. Budapest. Sect. Comput. 35 (2011), 43–49.
3. D. Burek and B. Żmija, A new upper bound for numbers with the Lehmer property and its application to repunit numbers, Int. J. Number Theory 15 (2019), 1463–1468.

Source

Imported from Formal Conjectures Wikipedia/LehmerTotient, curated by Google DeepMind and contributors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.