Are there easier ways to solve this integer equation than brute-force

Question

The following question searched for the solutions of

$$ y^x=x^{50} $$

User JCAA was able to reduce this to finding $s$ and $q$ as the solutions of

$$ \frac{s^q}{q} = \frac{50}{p} \quad\textrm{with}\ p\in\{1,2,5,10,25,50\}$$

The answers to these 6 equations are easy and can be done brute-force. But how does one go about it when you have an equation of the form:

$$ \frac{p^q}{q} = n $$

with $n$ a somewhat larger number like $n=4608$.

The only thing I could come up with is writing everything down in prime-factors:

$$ p = \prod{\pi_i^{a_i}}, \qquad q = \prod{\pi_i^{b_i}}, \qquad n = \prod{\pi_i^{c_i}}$$

And you can reduce the equation into:

$$ q a_i - b_i = c_i\qquad \forall i\in\mathbb{N}_0$$

Since $q>b_i$ $\forall i$, then you know that:

• If $c_i=0$ then $a_i=b_i=0$
• If $n$ is prime, $p=n$ and $q=1$ is the only solution

For all other cases, it seems you have to brute-force it.

Question: are there any standard methods in solving this, or is brute-force the only way?

Using Mathematica, I found the following brute-force solutions:

p      q     n
4608   1     4608
96     2     4608
24     3     4608

Answer 1

Given a positive integer $c>1$, you want to find all positive integers $a$ and $b$ such that $a^b=bc$. Clearly $c$ divides $a^b$, and for every prime number $p$ dividing $a$ we see that $p^b$ divides $bc$, from which it quickly follows that $p$ divides $c$. Moreover, we see that $a\leq c$ as otherwise $bc=a^b\geq c^b$ and so $b>c^{b-1}$, which is impossible given that $c>1$. This shows that $a$ divides $c$, and is divisible by every prime that divides $c$, i.e. $a$ is divisible by $\operatorname{rad}(c)$. Given a factorization $c=\prod_{p\mid c}p^{c_p}$ this leaves $\prod_{p\mid c}c_p$ candidates for $a$.

Of course $(a,b)=(c,1)$ is the only solution with $a=c$, so suppose $a<c$. The real continuous function $$f(b)=a^b-bc,$$ has at most two zeros, because its derivative has precisely one zero, say $x_a$. Clearly $f(0)>0$, and because $a<c$ we have $f(1)<0$, so $f$ has a root in the open interval $(0,1)$. Then there is at most one integer $b$ such that $a^b=bc$, for each value of $a$. Because $f(x_a)<0$ and $f(c)>0$, and $f$ is strictly increasing for $b>x_a$, it is not hard to determine whether there exists an integer $b$ such that $f(b)=0$.

Of course the amount of work this requires depends on the size of $c$, and especially its number of (repeated) prime factors. For large values this is better left to a computer, though I wouldn't quite call this a brute force approach.