Reused writeup on Math-5919 (gpt pro 5.2)

Erdős Problem 820 --- collection record

PROVENANCE AND STATUS

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

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/820.tex.

REUSED SOURCE 1

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

Erdos Problem #820

FORMAL RESTATEMENT.

For each integer $n\ge1$, define $H(n)$ to be the smallest integer $\ell\ge2$ such that there exists an integer $k$ with $2\le k<\ell$ and \[ \gcd(k^n-1,\ \ell^n-1)=1. \] (Here $\gcd$ is the greatest common divisor.) Equivalently, $H(n)$ is the least $\ell$ such that some smaller base $k$ produces multiplicatively "coprime" repunit-like numbers $k^n-1$ and $\ell^n-1$. The problem asks, among other things, whether $H(n)=3$ for infinitely many $n$, i.e. whether \[ \gcd(2^n-1,\ 3^n-1)=1 \] holds for infinitely many $n$, and for estimates on the growth of $H(n)$.

QUICK LITERATURE/CONTEXT CHECK.

The statement records: (a) Erdős proved there exists $c>0$ and infinitely many $n$ with $H(n) > \exp(n^{c/(\log\log n)^2})$; (b) a sketch (in comments) of a stronger lower bound $H(n) > \exp(n^{c/\log\log n})$ for infinitely many $n$; and (c) the exact values $H(n)$ for $1\le n\le 10$. I do not use any results not already stated in the problem text.

ATTACK PLAN.

Elementary track: prove basic upper and lower bounds that hold for every $n$, and compute small values to sanity-check. Deeper track: understand common prime divisors of $k^n-1$ and $\ell^n-1$ via multiplicative orders modulo primes; without external results this track remains largely open.

WORK.

Lemma 820.1 (trivial lower bound). For every $n\ge1$, $H(n)\ge 3$.

Proof. If $\ell=2$, the only possible choice is $k=1$ (since $k<\ell$), but then $k^n-1=0$ and \[ \gcd(0,2^n-1)=2^n-1>1. \] So no $\ell=2$ works, hence $H(n)\ge3$. $\square$

Lemma 820.2 (a general exponential upper bound via radicals). For every $n\ge2$, let \[ \ell := \operatorname{rad}(2^n-1) := \prod_{p\mid (2^n-1)} p \] (the product of the distinct prime divisors of $2^n-1$). Then with $k=2$ we have \[ \gcd(2^n-1,\ \ell^n-1)=1. \] Consequently, \[ H(n) \le \operatorname{rad}(2^n-1) \le 2^n-1. \]

Proof. Let $p$ be any prime divisor of $2^n-1$. By definition of $\ell$, we have $p\mid\ell$, hence $\ell\equiv 0\pmod p$ and so \[ \ell^n-1 \equiv -1 \not\equiv 0 \pmod p. \] Thus no prime $p\mid (2^n-1)$ divides $\ell^n-1$. Every common divisor of $2^n-1$ and $\ell^n-1$ must in particular be composed of primes dividing $2^n-1$, but we have just shown none of those primes divide $\ell^n-1$. Therefore $\gcd(2^n-1,\ell^n-1)=1$. Since $n\ge2$ implies $2^n-1\ge3$, we have $\ell\ge3$ and indeed $k=2<\ell$. Finally, $\operatorname{rad}(m)\le m$ for every integer $m\ge1$, giving $\ell\le 2^n-1$. $\square$

FAST REALITY CHECK (exact $H(n)$ for $n\le 10$ and gcd test for $k=2,\ell=3$). By direct brute-force search over $\ell$ and $k<\ell$, I confirmed the sequence in the problem statement: \[ H(1),\dots,H(10)=3,3,3,6,3,18,3,6,3,12. \] Also, for $1\le n\le 100$, the set of $n$ such that $\gcd(2^n-1,3^n-1)=1$ is \[ \{1,2,3,5,7,9,13,14,15,17,19,21,25,26,27,29,31,34,37,38,39,41,45,47,49,51,53,57,59,61,62,63,65,67,71,73,74,79,81,85,87,89,91,93,94,97,98\}. \]

VERIFICATION.

Lemma 820.2: the argument checks each prime divisor $p$ of $2^n-1$ individually; choosing $\ell$ divisible by all such primes forces $\ell^n-1\equiv -1\pmod p$, so these primes cannot divide $\ell^n-1$. Since any common divisor must use primes from $2^n-1$, the gcd is $1$. The computed sequences are finite checks.

FINAL.

UNRESOLVED.

1. (i) Strongest proved partial results here: the universal bounds $3\le H(n)\le \operatorname{rad}(2^n-1)\le 2^n-1$ for $n\ge2$ (Lemmas 820.1--820.2), and verification of the exact values $H(n)$ for $1\le n\le 10$ plus the list of $n\le100$ for which $\gcd(2^n-1,3^n-1)=1$.
2. (ii) First gap: decide whether $\gcd(2^n-1,3^n-1)=1$ for infinitely many $n$ (equivalently, whether $H(n)=3$ infinitely often).
3. (iii) Top 3 next moves: $1$ study primes $p$ for which $2^n\equiv 3^n\equiv 1\pmod p$, i.e. orders of $2$ and $3$ modulo $p$ both divide $n$; $2$ compute $H(n)$ and $\gcd(2^n-1,3^n-1)$ for much larger $n$ to look for patterns in the exceptional set; $3$ attempt to bound from below the number of distinct prime factors shared by $k^n-1$ and $\ell^n-1$ for small $\ell$ by using order considerations.
4. (iv) A minimal counterexample to "$H(n)=3$ infinitely often" would be a situation where for all sufficiently large $n$ there exists a prime $p$ with $2^n\equiv 3^n\equiv 1\pmod p$; equivalently, the multiplicative orders of $2$ and $3$ modulo $p$ both divide $n$, forcing a persistent shared prime divisor of $2^n-1$ and $3^n-1$.

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.