Reused writeup on Math-829 (gpt pro 5.2)

Erdős Problem 479 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/479

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/479.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/479.tex.

1) “FORMAL RESTATEMENT”

Fix an integer k != 1. The question is whether there exist infinitely many integers n>=2 such that

2^n ≡ k (mod n),

i.e. n divides $2^n - k$.

2) “QUICK LITERATURE/CONTEXT CHECK”

The problem statement notes that the case k=2^i $i>=1$ and k=-1 is known (attributed to Graham-Lehmer-Lehmer, with a later note by Tang), while the general case is open. A quick check of the Erdos Problems page for #479 shows it is listed as OPEN (as of mid-Jan 2026). I do not rely on any external paper; I give self-contained proofs for the k=-1 family and for infinitely many k=2^i using standard number theory facts.

3) “ATTACK PLAN”

- Produce explicit infinite families of solutions for certain k (sanity check that the phenomenon is real). - For general k, understand constraints from prime factors of n: if p|n then 2^n ≡ k (mod p), giving conditions on the order of 2 mod p. - Try to “lift” solutions by building n with controlled prime factors (Pratt-tree / Korselt-type constructions).

4) “WORK”

Lemma 479.1 (k=2 has infinitely many solutions). For every odd prime p, we have 2^p ≡ 2 (mod p). Hence k=2 has infinitely many solutions.

Proof. By Fermat's little theorem, for odd prime p we have 2^{p-1} ≡ 1 (mod p). Multiply both sides by 2 to get 2^p ≡ 2 (mod p). QED.

Lemma 479.2 (k=-1 has an explicit infinite family). For every integer m>=1, n=3^m satisfies 2^n ≡ -1 (mod n).

Proof. We will show the stronger statement that for every m>=1,

2^{3^{m-1}} ≡ -1 (mod 3^m).

Then raising both sides to the third power yields 2^{3^m} ≡ $-1$^3 = -1 (mod 3^m), which is exactly 2^n ≡ -1 (mod n) with n=3^m.

To prove 2^{3^{m-1}} ≡ -1 (mod 3^m), we compute the 3-adic valuation of 2^{3^{m-1}}+1 using the special-case LTE (Lifting The Exponent) identity:

Claim: For any odd integer t>=1, v_3$2^t + 1$ = v_3$2+1$ + v_3(t).

Justification of the claim (standard LTE for p=3, a=2, b=1, t odd): since 3 divides 2+1 and t is odd, the exponent-lifting formula gives v_3$2^t+1^t$=v_3$2+1$+v_3(t).

Apply this with t = 3^{m-1}. Then v_3(t)=m-1 and v_3$2+1$=1, so

v_3$2^{3^{m-1}} + 1$ = 1 + $m-1$ = m,

meaning 3^m divides 2^{3^{m-1}}+1, i.e. 2^{3^{m-1}} ≡ -1 (mod 3^m). This completes the proof. QED.

Lemma 479.3 (infinitely many solutions for each k=2^i). Fix i>=1 and put k=2^i. Let r be the odd part of i (so i=2^a r with r odd). Let M := r. Then for every prime p satisfying

p ≡ 1 (mod M) and p does not divide i,

the integer n := i p satisfies 2^n ≡ 2^i (mod n). In particular, assuming the standard theorem that there are infinitely many primes in the arithmetic progression 1 (mod M) (Dirichlet), there are infinitely many such n.

Proof. Let n=i p. First, modulo p we have by Fermat:

2^{ip} = $2^p$^i ≡ 2^i (mod p),

since 2^p ≡ 2 (mod p).

Now work modulo i. We need i | (2^{ip} - 2^i) = 2^i$2^{i(p-1)} - 1$. The power of 2 dividing i is at most 2^i, so the 2-part of i divides 2^i automatically. For the odd part r of i, we need

2^{i$p-1$} ≡ 1 (mod r).

Because p ≡ 1 (mod r), we have r | $p-1$, hence i$p-1$ is a multiple of r. Also, since gcd$2,r$=1, Euler's theorem gives 2^{phi(r)} ≡ 1 (mod r), so certainly 2^{i$p-1$} ≡ 1 (mod r) whenever phi(r) divides i$p-1$. A sufficient (simple) condition is that r divides $p-1$, which we assumed; since 2^{r} ≡ 1 (mod r) is not always true, the clean way is to take p ≡ 1 (mod phi(r)) instead. Thus, replacing M by phi(r), we get:

If p ≡ 1 (mod phi(r)) and p does not divide i, then 2^{i$p-1$} ≡ 1 (mod r), hence 2^{ip} ≡ 2^i (mod i).

Finally, if gcd(i,p)=1 (i.e. p does not divide i), then congruence modulo i and modulo p implies congruence modulo ip=n. Therefore 2^n ≡ 2^i (mod n).

This gives an infinite family of solutions n=i p provided there are infinitely many primes p ≡ 1 (mod phi(r)), which is guaranteed by Dirichlet's theorem on primes in arithmetic progressions.

(Concrete small check: for i=2, phi(r)=1, so every odd prime p works and n=2p gives infinitely many solutions for k=4; for i=3, phi(r)=2, so every odd prime p works and n=3p gives infinitely many solutions for k=8.) QED.

FAST REALITY CHECK (local computation). I searched exhaustively for solutions with n<=5000 for a few k. The first solutions found:

- k=2: n = 2,3,5,7,11,... (all odd primes appear, consistent with Lemma 479.1). - k=-1: n = 3,9,27,81,171,243,513,729,... (in particular 3^m works, consistent with Lemma 479.2). - k=3: no solutions with n<=5000 (consistent with the statement that the first solution is enormous).

5) “VERIFICATION”

- Lemma 479.2 was checked numerically for m<=10 by direct modular exponentiation and matches. - Lemma 479.3 is logically self-contained except for the infinitude of primes in a given progression; for that last step I invoked Dirichlet's theorem.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: We have explicit infinite families for k=2 (all odd primes p) and k=-1 (all n=3^m). Moreover, for every i>=1 we can construct infinitely many solutions for k=2^i of the form n=i p with p prime in a suitable progression (using standard primes-in-progressions input).

(ii) First gap (crisp statement): Prove or disprove: for a fixed k not of the special forms above $e.g. k=3$, there are infinitely many n such that 2^n ≡ k (mod n).

(iii) Top 3 next moves (concrete): 1. Attempt to generalize the k=-1 construction: find a prime power q^m and an exponent pattern forcing 2^{q^m} ≡ k (mod q^m) via LTE. 2. Develop a lifting mechanism: from one solution n, build a larger solution n' by adjoining a new prime factor p chosen so that 2^{n'} ≡ k (mod p) and also (mod n). 3. For specific k (starting with k=3), run targeted searches for n with controlled factorization (e.g. n a product of a few primes) and look for patterns suggesting an infinite family.

(iv) Minimal counterexample structure (if the answer is “no” for some k): A value k!=1 and a proof that the set { n>=2 : n | $2^n - k$ } is finite; equivalently, all sufficiently large n fail the congruence 2^n ≡ k (mod n).

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.