# A question regarding Goormaghtigh conjecture

I have a question regarding Goormaghtigh conjecture on the Diophantine equation $$\frac{x^m-1}{x-1}=\frac{y^n-1}{y-1}.$$

Suppose that a positive integer $$N$$ is given. How many integer solutions are there to the equation $$\frac{x^m-1}{x-1}=N=\frac{y^n-1}{y-1},$$ with $$x$$ and $$y$$ prime powers?

Observe that I am not asking for a solution of Goormaghtigh conjecture in the case that $$x$$ and $$y$$ are prime powers, but I am asking whether one can bound the number of solutions with a very slow growing function of $$N$$, when $$x$$ and $$y$$ are prime powers. [Not sure what I mean with "slow growing". Just interested to know what is known in this case.]

Some simple observations, which are independent of x or y being prime powers.

m must be less than $$\log N$$. If there is a solution, $$N$$ has to factor into (about) d(m) factors which are values of cyclotomic polynomials of indices $$c$$ dividing m, and thus the sizes of the factors are close to $$x^{\phi(c)}$$ in size, so one can't have just any product of factors.

We have $$m=2$$ is always a solution with $$x = N-1$$, so if $$x$$ must be a prime power then so is $$N-1$$. For $$N$$ with few factors, one can rule out $$m$$ with many divisors. Large prime factors of $$N$$ must exist when $$m$$ is greater than 6, and these primes must be 1 mod m, so if there are two of the prime factors of $$N$$ greater than $$\log N$$, their difference can give some restrictions on the possible values of $$m$$.

Ribenboim's book on Catalan's conjecture will have related material, and possibly a good answer to your question.

Update 2018.10.10

There is a simple analysis which points at better than $$\log N / \log\log N$$ upper bound on the number of pairs $$(x,m)$$ satisfying the equation. I will use $$k$$ to express this upper bound, where $$k$$ is the largest integer satisfying $$k^k \leq N$$. A more careful computation might suggest using $$k+1$$, but I will not take such care for reasons that will appear.

The first point is that we cannot have $$m$$ and $$x$$ both larger than $$k+2$$. So immediately we have a bound of about $$2k$$ possible solutions, half coming from $$x$$ going from 2 up to $$k+1$$, and the other half from $$m$$ going from $$k+1$$ down to 3. (There is always a solution with m=2, which we ignore.) Indeed, a naive computer search could start with $$x=2$$, find the corresponding $$m$$ if any, and then increase $$x$$ by 1 until $$x$$ is larger than $$m$$ Then the search switches to taking $$m$$th roots and decrementing $$m$$ by 1 to test for further solutions. With a possible error of a small constant, this gives an easily proved upper bound of the number of solutions given $$N$$, and a hint of how to find them. For $$N$$ not too small ($$N$$ greater than 100, maybe?), this occurs in fewer tests than the number of bits needed to write $$N$$ in binary.

However, it gets better. We have $$(N -1) = x(1+jx)$$ for some integers $$j$$ and $$x$$ with $$x$$ part of a potential solution. This means $$x$$ is a unitary divisor of $$N-1$$, which means less than half the values of $$x$$ below $$k$$ need to be tested (e.g. $$x$$ can be 2 or a power of two, but not both, and similarly with odd multiples of two or the power), so really there are more like $$3k/2$$ possibilities for $$x$$.

Also, if one knows enough factors of $$N$$, one can speak to the possibilities for $$m$$. Namely, a prime divisor of $$N$$ must be one more than a multiple of a divisor of $$m$$. Further, if $$N$$ is prime or has few factors, then $$m$$ cannot have many factors, and thus one is limited to look at prime values for $$m$$, or non smooth values of $$m$$ (as noted above this update) which can cut out a third of the checks needed roughly.

Even further, one can show that for $$m$$ fixed, $$N$$ must have certain residues mod small primes, and so $$m$$ can be eliminated from further testing. The actual number of solutions looks more like it is bounded by $$k$$, again much less than the number of bits needed to express $$N$$ in binary.

End Update 2018.10.10

Gerhard "Playing Around With Prime Numbers" Paseman, 2018.10.05.

• To tie this in to the question, the restriction that x be a prime power limits the number now to the number of distinct prime factors of N-1. While this quantity can be as large as k, usually it is around log log N, which is what I would expect for an upper bound to the number of simultaneous solutions. Gerhard '"Of Course I'm Hoping Here" Paseman, 2018.10.10. – Gerhard Paseman Oct 11 '18 at 3:08