2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Oct 11 '18 at 3:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.