Lehmer's totient problem: find a composite $n$ with $\varphi(n)\mid n-1$, or extend the search/constraints (Guy UPINT §B37)
Statement
Does there exist a composite integer $n$ such that Euler's totient $\varphi(n)$ divides $n-1$? (For prime $n$, $\varphi(n)=n-1$ divides $n-1$ trivially; the question is whether any composite behaves the same way.) Exhibit such a composite $n$ (a 'Lehmer number'), or extend the region and structural constraints under which none can exist.
Acceptance. FULLY RESOLVES: a composite $n$ with a certificate — its prime factorization (so $\varphi(n)$ is computed and machine-checkable) and the exact integer quotient $(n-1)/\varphi(n)$ — verifying $\varphi(n)\mid n-1$. ADVANCES, either: (a) extend the verified lower bound below which no Lehmer number exists (state the prior bound $10^{20}$; enumerate Carmichael/candidate numbers to a higher bound with a reproducible search and a re-check script), or (b) strengthen a structural constraint (e.g. raise the $\omega(n)\ge 14$ bound) via a verifiable computation. Deliver the search configuration and verifier.
Background
Asked by D. H. Lehmer (1932); Guy, 'Unsolved Problems in Number Theory' (3rd ed.), §B37. No composite solution is known. Any solution must be an odd, squarefree Carmichael number with $\omega(n)\ge 14$ distinct prime factors and $n>10^{20}$ (Cohen–Hagis, 1980); if $3\mid n$ then far stronger bounds hold ($\omega(n)\ge 4\times10^{7}$, $n>10^{3.6\times10^{8}}$, Burcsi–Czirbusz–Farkas). Because solutions are Carmichael numbers, searches proceed over Carmichael tables (e.g. Pinch) checking the divisibility $\varphi(n)\mid n-1$; a genuine witness is believed astronomically large, so the realistic computational path is extending the exclusion bound or tightening constraints. Open.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Lehmer's totient problem — Wikipedia | website |
| REF-02 | Pinch, A note on Lehmer's Totient Problem (Carmichael-number search) | paper |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.