How to calculate the "modular multiplicative inverse" when the denominator is not consistent with m?

Question

I need to calculate where and are very large numbers. (a/b) mod m a b

What I'm trying to do is figure out where is the modular inverse . (a mod m) * (x mod m) x b

I tried using the Extended Euclidean algorithm , but what if b and m are not compatible? In particular, it is mentioned that b and m must be joint.

I tried using the code here and realized that, for example: it’s not at all possible for any value , it doesn’t exist! 3 * x mod 12 x

What should I do? Is there any way to change the algorithm?

Answer 1

Yes, you have a problem. x has no solution in b*x = 1 mod mif b and m have a common factor. Similarly, in your original problem, a/b = y mod myou are looking for y to a=by mod m. If a is divisible by gcd(b,m), then you can split this factor and decide for y. If not, then y cannot solve the equation (i.e. a/b mod mnot defined).

Answer 2

The reason b and m should be relatively simple is related to the Chinese stopping theorem. Basically the problem:

3 * x mod 12

Can be considered as a complex problem involving

3*x mod 3 and 3*x mod 4 = 2^2

Now, if b is not coprime to 12, this is like trying to divide by zero. So the answer does not exist!

. , , , . GF (p ^ n), p , n - , - p ^ n. 12 , . , b, m.

Answer 3

Note this: http://www.math.harvard.edu/~sarah/magic/topics/division This may help. He explains modular division techniques.