Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.