Return to Answer

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.

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

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 $l$, gain much less than the number of bits needed to express $N$ in binary.

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.

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

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.

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.

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 is 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, 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.

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

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 $l$, gain much less than the number of bits needed to express $N$ in binary.

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 +2 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 mth 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 is 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, 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.

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 is 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, 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.