Erdős problem #479 — wave 9m

Access/research date: 2026-07-28 UTC.

Claim labels used below:

• (a) elementary-rigorous: proved here from elementary facts.
• (b) rigorous modulo named theorem: the dependency is named.
• (c) plausible/structural-unverified: heuristic or a research direction, not a theorem.
• (d) computational-only: established only by the stated finite computation or source inspection.

0. Mandatory live-page gate

(d, live-page inspection) I fetched the live problem page and its discussion thread through the Bright Data browser path, rather than through datacenter curl.

The verbatim statement on the live page is:

Is it true that, for all \(k\neq 1\), there are infinitely many \(n\) such that \(2^n\equiv k\pmod{n}\)?

The page says OPEN, was last edited 03 December 2025, shows 0 claimed proofs, and has the following markers:

• Interested in collaborating: None
• Currently working on this problem: None
• I am working on formalising the results: None
• Likes this problem: Quanyu_Tang

Thus the mandatory stop condition did not trigger.

(d, live-page inspection) The page's listed mathematical context is:

• this is a conjecture of Graham;
• \(2^n\not\equiv1\pmod n\) for \(n>1\);
• Erdős and Graham attribute the cases \(k=2^i\), \(i\geq1\), and \(k=-1\)

to Graham, D. H. Lehmer, and Emma Lehmer, but the page owner could not locate that manuscript;

• Quanyu Tang supplied a short note proving the power-of-two cases;
• the page states that the smallest nontrivial solution for \(k=3\) is

\(n=4700063497\);

• it points to OEIS A036236 for least representatives.

The three live comments were also read:

1. Quanyu Tang (2025-12-02) links his note, says it proves all

\(k=2^i\), and reports that the cases currently known to be infinite are \[ k\in\{0,-1,-2,2^i:i\geq1\}. \] He says every other fixed \(k\) remains open.

1. Tang (2025-12-03) discusses his table of 38 associated OEIS sequences.
2. Terence Tao (2025-12-03) says that listing all 38 would distort the

database and that he selected the sequences for \(k=-3,-2,-1,2,3,4\) as representatives.

Comments on the site are explicitly marked unverified by the site. I used them as search leads, not as proofs.

1. Primary-source literature check

(d, source inspection) The following sources were opened and checked:

1. P. Erdős and R. L. Graham,

Old and New Problems and Results in Combinatorial Number Theory (1980), printed p. 96. The scan contains Graham's conjecture, the [Gr-Leh-Leh(xx)] attribution, and the Lehmer computation \(4700063497=19\cdot47\cdot5263229\). Its bibliography describes the 1971 Lehmer item as a personal communication; it does not supply a published Graham–Lehmer–Lehmer paper.

1. Quanyu Tang,

A Note on Erdős Problem #479: Infinitude of the Sets \(A(2^i)\) and Related Results, dated 2025-12-02, six pages. It explicitly calls the Graham–Lehmer–Lehmer item unpublished, surveys the cases \(\{0,-1,-2,2^i\}\), and gives a proof for all \(2^i\).

1. A. Kalmynin,

On Novák numbers, arXiv:1611.00417, later Sb. Math. 209 (2018), 491–502, DOI 10.1070/SM8848. The paper defines Novák numbers by \(n\mid2^n+1\), notes \(3^j\) as an elementary infinite subfamily, and proves much stronger counting results.

1. Mathematical Excalibur 14(2), Problem 323 (2009),

pp. 3–4. The printed solution proves the \(k=-2\) case by maintaining two simultaneous divisibilities and iterating \(n\mapsto2^n+2\).

1. A. Rotkiewicz,

On the congruence \(2^{n-2}\equiv1\pmod n\), Math. Comp. 43 (1984), 271–272. This is an older infinitude proof for \(k=4\), hence one of the power-of-two cases.

(b, Dirichlet's theorem) Tang's proof for \(k=2^i\) takes \(n=ip\). The condition modulo \(p\) is automatic, while finitely many order conditions modulo the prime powers in \(i\) are forced by choosing \(p\equiv1\pmod L\). Dirichlet's theorem supplies infinitely many such primes.

(d, search result) Exact-phrase and bibliographic searches for "2^n ≡ k (mod n)", "On values of 2^n modulo n", Graham Lehmer Lehmer, and the corresponding arXiv query did not locate a published version of the placeholder manuscript or a newer paper proving a new fixed \(k\). This is a reported search miss, not a proof that no such literature exists. OEIS pages were used only as secondary cross-checks.

2. A local valuation obstruction

Put

and let \(\omega_o(n)\) be the number of distinct odd prime divisors of \(n\).

Lemma 2.1

(a) If \(n\in A(k)\) and \(p^b\mid n\), where \(p\) is odd and \(b\geq1\), then

Proof. If \(p\mid k\), then \(2^n\equiv k\equiv0\pmod p\), impossible. Raise \(2^n\equiv k\pmod{p^b}\) to the \((p-1)\)-st power. Since

(indeed \(p^b\mid n\)), Euler's theorem gives

This proves (2.1). \(\square\)

(a) A second elementary restriction is that if \(n\geq2\), \(2^a\mid n\), and \(n\in A(k)\), then \(2^a\mid k\). Consequently, for \(k\neq0\),

Lemma 2.1 says that a repeated odd prime in a solution must be a Wieferich-type prime for base \(k\). This statement is only terminology; the divisibility (2.1), not any conjecture about such primes, is used below.

3. Exact classification when \(\omega_o(n)\leq1\)

This is the main proof-level output.

Theorem 3.1

(a) Fix an integer \(k\). All elements of \(A(k)\) with at most one distinct odd prime divisor are given by the finite procedure and exceptional families below.

Write such an \(n>1\) as

where \(a,b\geq0\), and \(p\) is odd when \(b>0\).

1. If \(b=0\), then \(n=2^a\) is a solution exactly when \(2^a\mid k\).

(For \(k=0\), every \(2^a\) works.) Also \(n=1\) works for every congruence.

1. Suppose \(b>0\) and \(k\neq0\). Then

\[ 0\leq a\leq\nu_2(k),\qquad p\mid D_a(k):=2^{\,2^a}-k. \tag{3.1} \]

1. If \(D_a(k)\neq0\) and \(k\neq-1\), there are only the finitely many

candidates \[ n=2^a p^b,\quad p\mid D_a(k),\quad 1\leq b\leq\nu_p(k^{p-1}-1), \tag{3.2} \] and direct modular exponentiation among these candidates is an exact decision procedure.

1. The \(k=-1\) solutions in this regime are exactly

\[ 1,3,3^2,3^3,\ldots. \tag{3.3} \]

1. If \(D_a(k)=0\), equivalently \(k=2^{2^a}\), the corresponding

solutions are exactly \[ 2^a p^b \quad\text{with \(p\) odd prime and}\quad p^b\mid2^{p-1}-1. \tag{3.4} \]

Proof. The pure power-of-two statement follows because \(2^a\mid2^n\). Equation (2.2) bounds \(a\) when \(k\neq0\).

For \(b>0\), reduce the exponent modulo \(p-1\):

so

This proves (3.1). If \(D_a(k)\neq0\), it leaves only the finitely many odd prime divisors of \(D_a(k)\), and Lemma 2.1 gives (3.2).

If \(k=-1\), parity forces \(a=0\), and (3.1) forces \(p\mid3\), hence \(p=3\). The elementary LTE identity

proves (3.3).

It remains to prove (3.4). If \(k=2^{2^a}\), the odd-prime-power condition is

Let \(d=\operatorname{ord}_{p^b}(2)\). From (3.5), \(d\mid2^a(p^b-1)\), while \(d\mid p^{b-1}(p-1)\). Because \(p\nmid2^a(p^b-1)\), the order \(d\) has no factor \(p\), hence \(d\mid p-1\). This is equivalent to \(p^b\mid2^{p-1}-1\). The converse follows because \(p-1\mid p^b-1\). \(\square\)

Consequences

(a) Unless

only finitely many members of \(A(k)\) can have at most one distinct odd prime divisor.

(a) For \(k=3\), Theorem 3.1 gives only \(n=1\). Every nontrivial solution therefore has at least two distinct odd prime divisors. The published example has three.

(a) For \(k=-2\), the complete list in this regime is \(\{1,2,6\}\). Thus every further member of the known infinite set \(A(-2)\) has at least two distinct odd prime divisors.

These are reductions, not solutions of the full conjecture: the number and size of odd prime factors may grow with \(n\).

Exact table for \(-20\leq k\leq20\)

(a) The following table is an exact consequence of Theorem 3.1 plus deterministic factorization of the small integers \(D_a(k)\). Define

Every set in the table is \(A(k)\cap\{n:\omega_o(n)\leq1\}\).

| \(k\) | Exact set with \(\omega_o(n)\leq1\) | |---:|:---| | -20 | \(1,2,4,6,11,12\) | | -19 | \(1,3,7,9,49,343\) | | -18 | \(1,2,5,22,25\) | | -17 | \(1,19\) | | -16 | \(1,2,3,4,8,10,16,136,272,3856\) | | -15 | \(1,17\) | | -14 | \(1,2,6\) | | -13 | \(1,3,5\) | | -12 | \(1,2,4,7,28\) | | -11 | \(1,13\) | | -10 | \(1,2,3,9,14\) | | -9 | \(1,11,121\) | | -8 | \(1,2,4,5,6,8,12,18,24,36,72,88\) | | -7 | \(1,3\) | | -6 | \(1,2,10\) | | -5 | \(1,7\) | | -4 | \(1,2,3,4,20\) | | -3 | \(1,5\) | | -2 | \(1,2,6\) | | -1 | \(\{1\}\cup\{3^b:b\geq1\}\) | | 0 | \(\{2^a:a\geq0\}\) | | 1 | \(1\) | | 2 | \(\{1,2\}\cup W_0\) | | 3 | \(1\) | | 4 | \(\{1,2,4,12\}\cup W_1\) | | 5 | \(1,3\) | | 6 | \(1,2\) | | 7 | \(1,5,25\) | | 8 | \(1,2,3,4,8,9,248\) | | 9 | \(1,7\) | | 10 | \(1,2,6,18\) | | 11 | \(1,3\) | | 12 | \(1,2,4,5\) | | 13 | \(1,11\) | | 14 | \(1,2,3,10\) | | 15 | \(1,13\) | | 16 | \(\{1,2,4,6,7,8,16,24,40,48,80,112,208\}\cup W_2\) | | 17 | \(1,3,5,9\) | | 18 | \(1,2,14,98,686\) | | 19 | \(1,17\) | | 20 | \(1,2,3,4\) |

The verifier recomputes this table rather than trusting the transcription. I do not claim that Theorem 3.1 is new to the literature; it is the proof-level reduction obtained in this run.

4. An exact one-prime extension lemma

Lemma 4.1

(a) Suppose \(n\in A(k)\), \(p\) is a prime with \(p\nmid n\), and

Then \(np\in A(k)\).

Proof. Modulo \(p\), Fermat's theorem gives

Modulo \(n\),

The Chinese remainder theorem combines the two congruences. \(\square\)

When \(\gcd(k,n)=1\), the second condition in (4.1) is equivalently

(a, explicit certificates) The standalone checker verifies primality, both hypotheses in (4.1), and the final congruence for:

| \(k\) | seed \(n\) | adjoined prime \(p\) | new solution \(np\) | |---:|---:|---:|---:| | -5 | 7 | 19 | 133 | | -5 | 133 | 11161 | 1484413 | | 7 | 25 | 1342177 | 33554425 | | 17 | 45 | 817913 | 36806085 |

These certificates are not asserted to be new sequence terms. Their value here is that they give small, from-scratch-checkable instances of the exact growth mechanism for fixed \(k\)'s whose infinitude is open.

What the lemma isolates

(a) Starting from a solution \(n\) coprime to \(k\), this particular growth mechanism needs a new prime divisor

(c) A theorem guaranteeing (4.3) at infinitely many stages would give an infinite branch. No such theorem was found. Standard primitive-divisor theorems do not supply the required residue class for the mixed expression \(2^n-k\) with arbitrary fixed \(k\).

(a) For \(k=-1\), condition \(k^p\equiv k\) is automatic for odd \(p\), which explains the much stronger closure in Kalmynin's Lemma 5. For a general \(k\), the order condition (4.2) is genuine.

5. Exact bounded computation

The complete standalone code is erdos479_wave9m_reverify.py. It uses only Python's integer arithmetic and standard library.

The bounded scan uses the unambiguous “nontrivial” convention

This discards only finitely many small congruence aliases and has no bearing on infinitude.

(d) A single exhaustive pass checked every \(1\leq n\leq20{,}000{,}000\) for every \(-20\leq k\leq20\). It took 40.41 CPU-seconds and 18.9 MB peak RSS. An independently written C modular-exponentiation loop took 8.19 CPU-seconds and reproduced all 41 counts.

For compactness, here is the exact subtable for the still-open \(k\)'s with \(|k|\leq10\). Rows with many hits show the first and last six; the full per-\(k\) SHA-256 digests are emitted by the checker.

| \(k\) | count through \(2\cdot10^7\) | values, or first six … last six | |---:|---:|:---| | -10 | 6 | 14, 161, 261, 5727, 12127, 16394 | | -9 | 5 | 11, 121, 323, 117283, 432091 | | -8 | 52 | 12, 18, 24, 36, 72, 88 … 8138628, 8496456, 11272278, 13362422, 14017188, 18656328 | | -7 | 3 | 15, 75, 6308237 | | -6 | 2 | 10, 1030 | | -5 | 8 | 7, 133, 1517, 11761, 676333, 1484413, 3627557, 10289371 | | -4 | 42 | 20, 260, 740, 2132, 2180, 5252 … 17083172, 18068276, 18104452, 18166772, 18196292, 18672404 | | -3 | 6 | 5, 917, 3223, 62911, 326329, 395819 | | 3 | 0 | — | | 5 | 1 | 19147 | | 6 | 2 | 10669, 6611474 | | 7 | 3 | 25, 1727, 3830879 | | 9 | 2 | 2228071, 16888457 | | 10 | 3 | 18, 16666, 262134 |

(d) The all-41-row count/digest fingerprint is

e57a9b24aed12cf9ea0d313322a27afe2a460715f5148b61d2e3012ef84f19d3

The script also independently verifies

including trial-division primality checks on the three factors. (d) It does not verify that this is the smallest \(k=3\) solution; that minimality remains a source-reported fact here.

Run:

python runs/erdos479_wave9m_reverify.py --quick
python runs/erdos479_wave9m_reverify.py > /tmp/erdos479_full.json

The default run recomputes the exact table, certificates, bounded scan, per-sequence hashes, and the recorded aggregate fingerprint. --bound B selects another exact bound.

6. Precise remaining wall

(a) Theorem 3.1 completely disposes of the one-odd-prime-support regime, but it gives no bound when the number of distinct odd primes grows. This is exactly what happens in the known recursive \(k=-2\) construction and in the displayed nontrivial \(k=3\) example.

(a) Lemma 4.1 reduces one natural inductive attack to the prime-divisor condition (4.3). The missing uniform statement is:

Given sufficiently many (or an infinite chain of) seeds \(n\in A(k)\), prove that \(2^n-k\) has a new prime divisor \(p\equiv1\pmod{\operatorname{ord}_n(k)}\).

No cited theorem provides this. Merely finding many finite solutions, or many successful extension certificates, does not establish the required uniformity.

(d, cost estimate) At the measured C rate, naively scanning all \(n<4700063497\) to independently reproduce the published \(k=3\) minimality would cost about \(0.55\)–\(0.8\) core-hours, allowing for the larger exponents; this exceeds the requested few-CPU-minute budget and was not run. Trying to factor \(2^{4700063497}-3\) for the next extension is far less realistic: the integer has about \(1.415\times10^9\) decimal digits (about 588 MB even in packed binary form), and general factorization is not a credible computation on this box.

(c) The structural evidence suggests that progress for a new fixed \(k\) requires either a new closure invariant analogous to the special \(-1\) and \(-2\) mechanisms, or a genuinely new theorem controlling prime divisors of \(2^n-k\) in the changing order class (4.3). This is a diagnosis, not a claim that those are the only possible approaches.

PARTIAL: Proved an exact classification for all solutions with at most one odd prime divisor, verified explicit extension certificates, and exhaustively enumerated \(n\leq20{,}000{,}000\) for \(|k|\leq20\); the uniform new-prime lemma needed for infinitude remains open.