Solve the equation `a*x == b` with Int32 arithmetics In this thread we use 32-bit signed integers (assuming the usual two's complement). For simplicity I shall call this type Int32. The range is from -2147483648 through 2147483647. Any two values can be successfully multiplied (the result is an Int32 as well) since we use multiplication without overflow checking (we only keep the 32 least significant bits of the product).

For example, we have:

2147483647 * 2 == -2


and so on.

If your language does not have native support for 32-bit signed integers (with two's complement), you must emulate it.

Your task is to solve the equation:

a * x == b


where a and b are given as input, and it is assumed that a is an odd number (i.e. least significant bit is 1). You output an Int32 value.


The input to your program shall be two Int32 values a and b, and a will be odd
The output must be one Int32 value such that (if we call the output x) a*x == b
You do not have to handle invalid input; in particular, if the argument a is an even number, it does not matter what your code does
Code golf


Test cases:


Input                  Output

1,42                   42
3,126                  42
5,5                    1

-3,126                 -42
3,-126                 -42
-3,-126                42

2147483647,-2          2
2147483647,2           -2
2147483647,666         -666

3,0                    0
3,1                    -1431655765
3,2                    1431655766

-387907419,1342899768  1641848792
348444091,1076207126   -1334551070
10,14                  irrelevant (illegal input)


In the last case [a,b]==[10,14], even if there is a solution x = -1717986917 (not unique, x = 429496731 also works), you do not have to handle that case (10 is not odd).
Python 3, 39 bytes



lambda a,b,h=2**31:(a**~-h*b+h)%(2*h)-h


This is a theoretical solution that will take a long time unless a = 1. It uses the Euler-Fermat theorem to determine the modular inverse of a.

Alternate version, 47 bytes

lambda a,b,h=2**31:(pow(a,h-1,2*h)*b+h)%(2*h)-h


This does exactly the same, but in a more efficient manner.

Try it online!