

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

If $a$, $b$, and $c$ are known, is there an efficient way to find values of $x$ which satisfy $x^a\ \textrm{mod}\ b \geq c$ ?

share|cite|improve this question
What order are you using? Usually we don't think of an order on $\frac{\mathbb{Z}}{\mathbb{Z_p}}$ because of the circularity. – Ross Millikan Apr 11 '11 at 16:52
@Ross: Since he is using the $\bmod$ operator, $x^a\bmod b$ is always the unique integer between $0$ and $b-1$ (or between $1$ and $b$) that is congruent to $x^a$ modulo $b$, rather than a congruence class. So you can compare $x^a\bmod b$ with an integer $c$ in the usual order. For example, we can ask if $3^5\bmod 7$ is greater than or equal to $4$ (it is, since $3^5\equiv 5\pmod{7}$, so $3^5\bmod 7 = 5$). – Arturo Magidin Apr 11 '11 at 17:14
@Arturo: fair enough. – Ross Millikan Apr 11 '11 at 17:18
Note that $x$ might not exist, e.g., for $c\geq b$. Or it might be not unique... – Fabian Apr 11 '11 at 17:33

Your Answer



Browse other questions tagged or ask your own question.