Reverse Modulus Operator

Question

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.

You may try to use The Chinese Remainder Theorem. Check this [video](https://www.youtube.com/watch?v=Y5RcMWiUyyE). — Leonidas, Nov 27 '13 at 12:24

Michael Hogenson · Accepted Answer · 2015-07-31T02:31:58.747

36

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.

edited Jul 31 '15 at 02:31

answered Jul 30 '15 at 22:52

Michael Hogenson

1,292
1
15
31

4

Technically you don't have to set n to 0. Any n appears to work. I.E. x = (nm + b - a) mod m will give the correct answer of x for any integer n. – Michael Hogenson Jul 31 '15 at 02:43
3

What about `26x mod 29 = 3` ? – Bugs Happen Oct 03 '15 at 06:02
1

How does that help solve for x within the range of 0 to m? – Michael Hogenson Oct 03 '15 at 16:58
Oh sorry, I see. I'm not entirely sure. Wolfram Alpha says x = 29n + 28 for some integer n but I haven't been able to work out why. – Michael Hogenson Oct 04 '15 at 00:13
2

A note: "setting n to 0" is a good assumption for some problems. Exactly speaking considering nm to be 0 is good assumption, since nm is divisible by m, for those kind of problems. – Manohar Reddy Poreddy Jul 10 '16 at 13:30
I know this is 2 years after. But the correct answer would be `x = 29 * n + 6`, where `n in Z` – KaZyKa Sep 25 '18 at 08:54

score 15 · Answer 2 · answered Mar 18 '13 at 04:48

You can't definitively figure out x, but we can get a bit further given the definition of the operator.

x mod y = z if x = ny + z for some integer n, where 0 <= z < y

So in your case:

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

score 7 · Answer 3 · answered Apr 12 '12 at 23:24

7

yep. you're screwed.

example:

5 mod 3 = 2
8 mod 3 = 2

so inverse mod 2 is what? 8 or 5? or 11? or an infinitude of other numbers?

Inverse mod is a relation, you start to get to more tricky mathematics if you try to pursue this. If you're in haskell you could easilyish model it with non-determinism (an infinite list of possible answers)

Also, this isn't really a programming question. check out math exchange.

answered Apr 12 '12 at 23:24

TheIronKnuckle

7,224
4
33
56

Haha, just saw your edit. in the end i think you've thrown away too much info by applying modulus. It's a bit of an event horizon – TheIronKnuckle Apr 12 '12 at 23:26
Right, I was hoping someone smarter than myself had a convenient solution, but I had almost come to this conclusion by myself before hand. Thx bout the tip about math exchange, I didn't know it existed till today! – Michael Hogenson Apr 12 '12 at 23:29

score 2 · Answer 4 · answered Mar 07 '17 at 20:24

2

I have this Equation to reverse the modulus if we have

(var1 +var2) mod num=Res

then to get

var1= num-((Res-var2)*-1)

e.g. 25+5mod26=4

var1=26-((4-5)*-1)
var1=26-1
var1=5

answered Mar 07 '17 at 20:24

Subhi Ayman

118
8

score 1 · Answer 5 · answered Apr 12 '12 at 23:25

1

The tricky part about this equation is that even if you know a, m, and b, you can not conclusively figure out x.

For example, say your equation was:

(2 + x) % 4 = 3

x could be 1, 5, 9, 13 etc.

This means you are out of luck, there is no way to get x by itself.

answered Apr 12 '12 at 23:25

Andrew Clark

202,379
35
273
306

Except that I'm looking for a value within the range of m, so it would only be 1, since 5, 9 and 13 are all outside the range I'm looking for. – Michael Hogenson Apr 12 '12 at 23:28

score 1 · Answer 6 · answered Apr 26 '20 at 18:04

Using @Subhi Anyman answer as reference (with slight modifications), if we have this equation to reverse the modulus operation

 (var1 + var2) mod num = Res

then to obtain var1, we use the following

var1 = num - ((Res - var2) * -1)
if (var1 > num) {
   var1 = var % num;          // making sure var1 is in range of 'num'
}

Reverse Modulus Operator

6 Answers6

Linked