Discrete Logarithm Variation

Question

Given a positive integer $x$, is there an efficient method to determine integers $k$, $a$ and $b$ such that $kx+1=a^b$?

Examples:

$x=17$, $15(17)+1=2^8$

$x=13$, $2(13)+1 = 3^3$

$x=12$, $2(12)+1 = 5^2$

Answer 1

For any positive integer $x$, you can have $a = cx + 1$, for any positive integer $c$. Then, for any positive integer $b$, you get the positive integer $k = \frac{(cx+1)^b - 1}{x}$.

If you wish to use other values for $a$, in particular for $a \lt x$, here's how you can do it. Choose any $a$ which is relatively prime to $x$ (i.e., have no factors in common). Then you can choose $b$ to be the multiplicative order of $a$ modulo $x$, or any integral multiple of this (such as Euler's totient function). For the special case where $x$ is prime, then by Fermat's little theorem, you can choose any $a$ not a multiple of $x$, with $b = x - 1$ (or any integral multiple of this) working. Finally, note with any $a$ which works, then this value plus or minus any multiple of $x$ will also work.