OPEN
This is open, and cannot be resolved with a finite computation.
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$?
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].
View the LaTeX source
This page was last edited 02 December 2025.
Additional thanks to: Wouter van Doorn
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #820, https://www.erdosproblems.com/820, accessed 2026-01-16
