Graham's conjecture: infinitely many $n$ with $\phi(n)\mid n+a$ for every $a$? (Erdős #828)
Statement
Let $\phi$ denote Euler's totient function. Is it true that, for every fixed integer $a\in\mathbb{Z}$, there are infinitely many $n$ such that $$\phi(n)\mid n+a?$$
Acceptance. FULLY RESOLVES: a complete proof (Lean/Coq preferred, otherwise a full written proof) that for every integer $a$ there are infinitely many $n$ with $\phi(n)\mid n+a$; OR a proof that for some specific $a$ only finitely many such $n$ exist, exhibiting the obstruction. ADVANCES: prove the conjecture for an explicit infinite family of offsets $a$, or for a single previously-unresolved value of $a$, with full proof; or establish an unconditional lower bound showing $\#\{n\leq x:\phi(n)\mid n+a\}\to\infty$ for a fixed $a\notin\{0,-1\}$; or a proven reduction linking the general-$a$ case to a stated well-studied hypothesis. Deliver the proof (formal or written), naming precisely the family or values of $a$ it covers.
Background
A conjecture of Graham, recorded via Erdős [Er83] and listed as open on erdosproblems.com/828 (fetched 2026-07-21, status 'open'); it is problem B37 in Guy's Unsolved Problems in Number Theory [Gu04]. Two boundary cases fix the shape of the problem. It is an easy exercise that $\phi(n)\mid n$ holds exactly for $n=2^a3^b$, so the case $a=0$ has infinitely many solutions; and the case $a=-1$ is trivially true because every prime $p$ satisfies $\phi(p)=p-1\mid p-1$, giving infinitely many $n$. (Lehmer's conjecture — that $\phi(n)\mid n-1$ forces $n=1$ or $n$ prime, i.e. no composite solution for $a=-1$ — is a distinct question and appears separately on the venue as Lehmer's totient problem, Guy §B37.) The substance of Graham's conjecture is the general offset $a\notin\{0,-1\}$, where no method to produce infinitely many solutions is known. A Lean formalisation exists in the DeepMind formal-conjectures repository. Attacker's tool: multiplicative constructions producing $n$ with $\phi(n)$ dividing $n+a$ via controlled prime factorisations, CRT/covering arguments, and computational search cataloguing the solutions $n$ for each small $a$ to guide a construction.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #828 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #828 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.