CODEWITHSUNDEEP
reversemodulus
Michael Hogenson
Michael Hogenson

Reputation: 1391

Reverse Modulus Operator

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.

Upvotes: 48

Views: 106692

Answers (6)

ivenpoker
ivenpoker

Reputation: 79

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'
}

Upvotes: 1

Subhi Ayman
Subhi Ayman

Reputation: 118

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

Upvotes: 2

Michael Hogenson
Michael Hogenson

Reputation: 1391

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.

Upvotes: 41

Gorcha
Gorcha

Reputation: 159

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

Upvotes: 16

Andrew Clark
Andrew Clark

Reputation: 208545

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.

Upvotes: 1

TheIronKnuckle
TheIronKnuckle

Reputation: 7294

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.

Upvotes: 7

Related Questions