CODEWITHSUNDEEP
bashmathformulareversemodulus
Hiraeth
Hiraeth

Reputation: 1

Calculate Reverse Modulus

I'm trying to calculate the value of x in this equation:

(4 + 11111111/x)mod95 = 54

I've tried solving it using the top answer here: how to calculate reverse modulus However, it provides the lowest possible value for x (145, if helpful to anyone.) In addition, whenever 11111111/x is calculated, it removes any decimal places from the answer. Thanks!

Upvotes: 0

Views: 230

Answers (1)

jottbe
jottbe

Reputation: 4521

I guess you are referring to the bash code

(4 + 11111111 / x)  % 95 # == 54

Where / yields the int part of the division.

If you simplify that, an x that sattisfies this, also sattisfies:

(11111111 / x)  % 95 # == 50

And so also:

(11111111 / x) == 95 * i + 50  # for integer i

If we further look at the division that rounds towards the next lowest integer, we have

r= 11111111 % x
(11111111 - r)/x == 95*i + 50  # for integer i

(11111111 - r) == 5*(19*i + 10)*x # for integer i

So it can be rewritten as two conditions, which have to be met by any solution at once:

2222222 = (19*i + 10)*x
0 < 11111111 % x < x-1  # -1 because 11111111 % 5 == 1 and 11111111 % x < x

In other words, to find x you just need to check the two conditions for all divisors of 2222222.

In general, if you have questions like:

(a + b/x) mod m = c

transform it to

g=gcd(m, c-a)
c'= (c-a)/g
(b/x) mod m = g*c'
m= g*m'
b/x = g*c' + g*m'*i
r=  b%x
r'= b%g

# now search for an x that divides (b-r')/g
# and complies with the following conditions:
(b-r')/g = (c' + m'*i)*x
r' <= r < x-r'

Upvotes: 1

Related Questions