0

I am trying to solve $ax + b = y \; (mod \; m)$ for x, where $a,b,y,m$ are known values. This corresponds to running a linear congruential generator in reverse for one iteration.

I am happy to assume that $gcd(a,m) = 1$, which according to this page, means there is a single solution for $x$. I am looking for a nice algebraric manipulation of the equation that will produce this value for $x$.

I begin like this: first subtract $b$ from both sides

$$ax = y - b = u \; (mod \; m)$$

Next, compute $n$, the multiplicative inverse of $u$, to arrive at

$$axn = un = 1 \; (mod \; m)$$

How do I continue and find $x$?

  • 1
    Correction: There is a single solution for $x$ mod m. – wythagoras May 07 '15 at 13:47
  • 1
    You want to find the inverse of $a$, not of $u$. For intuition, ask yourself what you would do if it were a regular equation, not a modular equation. You would divide both sides by $a$. – vadim123 May 07 '15 at 13:47
  • Thanks for the help. Of course, I should have been "dividing" by $a$, which makes sense now. –  May 07 '15 at 15:15

1 Answers1

0

Once you have $ax = u \pmod{m}$, just multiply by $a$'s inverse in $\Bbb Z/m\Bbb Z$ (i.e. the only solution to $a a' = 1 \pmod{m}$ since you assume $\gcd(a,m)=1$): $$x = a^{-1} ax = a^{-1}u \pmod{m}$$

There's a lot of info (including computation methods) on modular inverse on Wikipedia.

Alexandre Halm
  • 3,714