A Note on Erdős Problem #479

This repository contains an expository note on Erdős Problem #479 (https://www.erdosproblems.com/479) concerning the congruence

$$ 2^n \equiv k \pmod n. $$

For an integer $k$, define $A(k)$ = { $n \ge 1 : 2^n \equiv k \pmod n$ }.

Graham conjectured that for every $k \neq 1$, the set $A(k)$ is infinite. This is listed as Problem #479 on Bloom’s Erdős Problems website.

---

Known results

The following sets are known to be infinite:

• $A(0)$;
• $A(2)$;
• $A(-1)$ (Novák numbers);
• $A(-2)$.

For all other integers $k$, including many positive values such as $k=3,5,6$, the infinitude of $A(k)$ remains open.

---

The case $k = 2^i$

Erdős and Graham attribute the statement that $A(2^i)$ is infinite for every $i \ge 1$ to an unpublished manuscript of Graham–Lehmer–Lehmer.
However, no published proof appears to exist, nor does the manuscript appear in the bibliographies of Graham or D.~H.~Lehmer.

Contribution of this note

• in Section 2 we survey the existing results and record those integers $k$ for which $A(k)$ is currently known to be infinite;
• and, for completeness, in Section 3 we give an explicit proof of the infinitude of $A(2^i)$, using Dirichlet’s theorem on primes in arithmetic progressions.

Files

• A_note_on_Erdos_Problem_479.pdf — the main expository document
• A_note_on_Erdos_Problem_479.tex — LaTeX source

---

Related links

• Erdős Problem #479: https://www.erdosproblems.com/479
• OEIS “2^n (mod n)” page: https://oeis.org/wiki/2%5En_mod_n
• OEIS entry for $A(8)$: https://oeis.org/A015922

---

Citation

If you wish to cite this note, use:

Quanyu Tang, A Note on Erdős Problem #479: Infinitude of the Sets A(2^i) and Related Results, December 2, 2025.
GitHub: https://github.com/QuanyuTang/Erdos-Problem-479-Note