Problem Statement
Let $H(n)$ be the smallest integer $l$ such that there exist $k<l$ with $(k^n-1,l^n-1)=1$.
Is it true that $H(n)=3$ infinitely often? (That is, $(2^n-1,3^n-1)=1$ infinitely often?)
Estimate $H(n)$. Is it true that there exists some constant $c>0$ such that, for all $\epsilon>0$,\[H(n) > \exp(n^{(c-\epsilon)/\log\log n})\]for infinitely many $n$ and\[H(n) < \exp(n^{(c+\epsilon)/\log\log n})\]for all large enough $n$?
Does a similar upper bound hold for the smallest $k$ such that $(k^n-1,2^n-1)=1$?
Is it true that $H(n)=3$ infinitely often? (That is, $(2^n-1,3^n-1)=1$ infinitely often?)
Estimate $H(n)$. Is it true that there exists some constant $c>0$ such that, for all $\epsilon>0$,\[H(n) > \exp(n^{(c-\epsilon)/\log\log n})\]for infinitely many $n$ and\[H(n) < \exp(n^{(c+\epsilon)/\log\log n})\]for all large enough $n$?
Does a similar upper bound hold for the smallest $k$ such that $(k^n-1,2^n-1)=1$?
Categories:
Number Theory
Progress
Erdős [Er74b] proved that there exists a constant $c>0$ such that\[H(n) > \exp(n^{c/(\log\log n)^2})\]for infinitely many $n$.van Doorn in the comments sketches a proof of the lower bound: that there exists some constant $c>0$ and infinitely many $n$ such that\[H(n) > \exp(n^{c/\log\log n}).\]The sequence $H(n)$ for $1\leq n\leq 10$ is\[3,3,3,6,3,18,3,6,3,12.\]The sequence of $n$ for which $(2^n-1,3^n-1)=1$ is A263647 in the OEIS.
See also [770].
Source: erdosproblems.com/820 | Last verified: January 16, 2026