Graham's conjecture: for every $k\neq 1$, infinitely many $n$ with $2^n\equiv k\pmod{n}$? (Erdős #479)
Statement
Graham's conjecture. Is it true that for every integer $k\neq 1$ there are infinitely many positive integers $n$ with $2^n\equiv k\pmod{n}$? The restriction $k\neq 1$ is necessary, since $2^n\not\equiv 1\pmod{n}$ for every $n>1$.
Acceptance. FULLY RESOLVES (proof-shaped): a complete proof — machine-checkable (Lean/Coq) preferred, else fully written — that for every $k\neq 1$ there are infinitely many $n$ with $2^n\equiv k\pmod{n}$; or a disproof exhibiting some $k\neq 1$ with only finitely many such $n$ (with a proof of finiteness). ADVANCES: a proof of infinitude for a new explicit class of $k$ beyond the known $k=2^i$ and $k=-1$ (e.g. all $k$ in a stated residue family, or a specific value such as $k=3$), with proof; or a reproducible computation extending OEIS A036236 — the least $n$ with $2^n\equiv k\pmod{n}$ — to new values of $k$, or producing additional solutions $n$ for a fixed hard $k$, with the program and certified outputs. Deliver the proof, or the search code plus certified witnesses.
Background
A conjecture of Graham, recorded by Erdős–Graham [ErGr80, p.96]; listed as open on erdosproblems.com/479 (fetched 2026-07-21, status 'open'). It is elementary that $2^n\not\equiv 1\pmod{n}$ for $n>1$, so $k=1$ must be excluded. Erdős and Graham report that Graham, D. H. Lehmer and E. Lehmer proved the conjecture for $k=2^i$ ($i\geq 1$) and for $k=-1$, though the original paper cannot be located; Q. Tang has since written a short note supplying a proof of these cases. The general case is open. As an indication of the difficulty, for $k=3$ the smallest $n$ with $2^n\equiv 3\pmod{n}$ is $n=4\,700\,063\,497$. The least such $n$ for each $k$ is OEIS A036236 (with related sequences A015919, A050259, A015921, A006521, A006517, A015940). The problem is formalized in Lean. No prize. Attacker's tool: for a fixed $k$, large-scale modular-exponentiation search for solutions $n$ (extending A036236), and structural constructions producing infinite families of $n$ (e.g. via the multiplicative order of $2$ modulo prime powers) aimed at proving infinitude for new residues $k$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #479 (T. F. Bloom) | website |
| REF-02 | OEIS A036236 — least n with 2^n ≡ k (mod n) | website |
| REF-03 | Q. Tang, A note on Erdős Problem 479 | paper |
| REF-04 | Lean formalisation of Erdős #479 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.