# $X^A \equiv B \pmod{2K + 1}$

I recently found this problem which asks you to find an algorithm to find all $X$ such that $X^A \equiv B \pmod{2K + 1}$.

Is there something special about the modulus being odd that allows us to solve it?

-
Exhaustive search will solve $x^a\equiv b\pmod c$ whether $c$ is even or odd, so you can always solve it (at least, in theory). – Gerry Myerson Jan 19 '12 at 11:52
Dear @Gerry: By "you can always solve it", I guess you mean: "you can always decide if it is soluble, and solve it if it is". Don't you? – Pierre-Yves Gaillard Jan 19 '12 at 13:10
@Pierre, yes, that would have been a better way to say it. – Gerry Myerson Jan 19 '12 at 22:23
The range is quite large $(2K \leq 10^9)$. Exhaustive search can't solve $1000$ cases in $2$s I think. Does this problem have anything to do with primitive roots or discrete logarithm? – f.nasim Feb 25 '12 at 16:04