# 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](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/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](https://doi.org/10.1090/S0002-9904-1932-05521-5), Bull. Amer. Math. Soc. **38** (1932), 745–751.
2. P. Burcsi, S. Czirbusz and G. Farkas, [Computational investigation of Lehmer's totient problem](https://doi.org/10.71352/ac.35.043), 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](https://doi.org/10.1142/S1793042119500830), Int. J. Number Theory **15** (2019), 1463–1468.

## Source

Imported from [Formal Conjectures Wikipedia/LehmerTotient](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/Wikipedia/LehmerTotient.lean), 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.