gpt pro 5.2 attempt on Math-5919

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$.