Lehmer's totient problem: is there a composite n with φ(n) dividing n − 1?
Difficulty 72: ninety years old with no line of attack beyond narrowing the shape of a hypothetical solution (Carmichael, squarefree, at least 14 prime factors), comparable to the Hadamard conjecture (70.5) and below Lindelöf (74), where at least the exponent keeps moving. A single large example could settle it, which keeps it below the Landau-type problems (84 and up). Application value 4: pseudoprime-type conditions matter to primality testing, but no practice depends on the answer. Leverage 10: essentially stand-alone.
The problem
Is there a non-prime number n for which the count of numbers coprime to n divides n minus 1?
- 1For primes, the count equals n minus 1
- 2Does a composite number share this?
- 3An example needs 14+ odd prime factors
- 4None known, none ruled out
Euler's totient. For a positive integer , counts the numbers from to that share no factor with other than 1 (they are to ). For example : the numbers 1, 3, 7, 9. If is prime, every number from 1 to is coprime to it, so , and in particular divides .
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Harmonic analysisTheory
- Step 3
- Then
- Lehmer's totient problem: is there a composite n with φ(n) dividing n − 1?The problem
State of the art
No composite solution is known. Lehmer (1932) showed a solution must be odd, squarefree, have at least 7 distinct prime factors and be a Carmichael number. Cohen and Hagis (1980) raised the prime-factor count to at least 14. Hagis (1988) showed that if divides a solution then it exceeds and has at least 298,848 prime factors; Burcsi, Czirbusz and Farkas (2011, Ann. Univ. Sci. Budapest. Sect. Comput. 35) raised this to more than and at least 40 million prime factors. Luca and Pomerance (2011) bound the number of solutions up to by roughly . Because solutions are rare or absent and any search must reach enormous sizes, neither computation nor current theory settles it.
Realistic applications
None. It is a clean test of what a congruence-type condition can say about primality, close in spirit to the primality tests (Fermat, Carmichael) that underlie cryptographic key generation, but no practice depends on the answer.
What counts as solved
Either a Lean proof of lehmer_totient (an explicit composite with , checkable by the kernel) or a Lean proof of its negation, i.e. that forces prime.
How it gets verified
Lean proofA formal proof checked by Lean 4 / Mathlib.
Statement: LehmerTotient.lehmer_totient in formal-conjectures: ∃ n > 1, ¬Prime n ∧ Nat.totient n ∣ n - 1. Mathlib has Nat.totient with a large API (Data.Nat.Totient), so no new definitions are needed. A positive answer is a certificate: an explicit plus its factorization, which Lean can verify (Nat.totient of a product of distinct primes is a product of , so the check reduces to big-integer arithmetic). A negative answer needs a genuine proof. Judge acceptance with Comparator against the pinned statement.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
A proof of nonexistence needs new structure theory; a counterexample would be found by a search constrained by the known shape (odd, squarefree, Carmichael, many primes).
Bottlenecks
ranked by votes- #1TheoryNo structural obstruction beyond Carmichael shape
Known results restrict a solution (odd, squarefree, at least 14 prime factors, Carmichael) but give no route to excluding all of them.
Community grades
Sign in to add your own grade.
Connected problems
- This problem is related to The Agoh–Giuga conjecture: a congruence that detects primesBoth ask whether a congruence characterizes primes, and any counterexample to either would have to be a Carmichael number.
Progress
- Jan 1, 2011Counting bound and the 3 | n casesource
Luca and Pomerance bound the number of solutions; Burcsi, Czirbusz and Farkas push the 3 | n case to enormous size (year only known).
- Jan 1, 1980At least 14 prime factorssource
Cohen and Hagis raise the bound on distinct prime factors (year only known).
- Jan 1, 1932Problem posed with first constraintssource
Lehmer shows a solution must be odd, squarefree, a Carmichael number and have at least 7 prime factors.