I have an equation $$x \cdot a \equiv b\pmod m$$ where $a$ and $b$ are known and $m$ is a prime number.

I want to solve for $x$. If $b=1$ then $x=a^{m-2}$ but I need to solve it for any value of $b$.

I found this answer which seems to work but is there an easier way if $m$ is prime ?

  • 3
    $\begingroup$ Just multiply by b^(-1) and get it back to the form you easily know how to solve. $\endgroup$
    – Yunus Syed
    Mar 10 '19 at 15:58
  • 1
    $\begingroup$ Ah, that was easy! Thanks! $\endgroup$ Mar 10 '19 at 16:07

The integers mod. $m$ are a field if $m$ is prime. So, as in any other field, multiply both sides by $a^{-1}$:

$$x\equiv b a^{-1}\equiv ba^{m-2}\pmod m. $$ Note $a$ may very well have an order $< m-1 $. The only general result is that it is a divisor of $m-1$, and in real calculations, it may be useful to check its value.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.