Menu
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.
552
An additive inverse of a modulo m always exists for every a and m . It's given by any number of the form –a + k * m , where k is an integer. We usually want to find the inverse in the range {0, ... , m - 1} , i.e., in the set of remainders of division by m .
The modular multiplicative inverse is an integer 'x' such that. The multiplicative inverse of “a modulo m” exists if and only if a and m are relatively prime (i.e., if gcd(a, m) = 1). Examples: Input: a = 3, m = 11 Output: 4 Since (4*3) mod 11 = 1, 4 is modulo inverse of 3(under 11).
If a,b are coprime, then there are integers u,v such that au+bv=1, which gives aumodb=1, that is, u is the multiplicative inverse of a. Then a(cu)modb=c. In the above, for a=3, b=16 you have u=11, so the formula is x=(11cmod16).
The modulo operator, denoted by %, is an arithmetic operator. The modulo division operator produces the remainder of an integer division. produces the remainder when x is divided by y.
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.
111
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 If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
