Reverse Modulus Operator

Michael Hogenson picture Michael Hogenson · Apr 13, 2012 · Viewed 62.2k times · Source

Over 3 years after asking the question I found the solution. I have included it as an answer.

I have an expression with modulus in it that needs to be put in terms of x.

(a + x) mod m = b

I can't figure out what to do with the modulus. Is there a way to get x by itself, or am I out of luck on this one?

Edit: I realize that I can get multiple answers, but I'm looking for an answer that falls within the range of m.

Answer

Michael Hogenson picture Michael Hogenson · Jul 31, 2015

I was revisiting this question and realized it is possible based off of the answer @Gorcha gave.

(a + x) mod m = b  
a + x = nm + b  
x = nm + b - a for some integer n

I don't know why I didn't realize it before but the solution can be derived by setting n to 0.

The answer to my question then appears to be x = b - a, though in the example (26 + x) mod 29 = 3 the result is -23, which is less than m. To get -23 back in the expected range mod it with 29, which gives 6. While not specified in the question this gives a value between 0 and m.

The final solution then becomes: x = (b - a) mod m

I.E.

(26 + x) mod 29 = 3
x = (3 - 26) mod 29
x = -23 mod 29
x = 6

Which puts x in the range of 0 to m. Checking will show (26 + 6) mod 29 = 3.