How to calculate “modular multiplicative inverse” when the denominator is not co-prime with m?

Question

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

What I am trying to do is to calculate (a mod m) * (x mod m), where x is the modular inverse of b.

I tried using Extended Euclidean algorithm, but what to do when b and m are not co-prime? It is specifically mentioned that b and m need to be co-prime.

I tried using the code here, and realized that for example: 3 * x mod 12 is not at all possible for any value of x, it does not exist!

What should I do? Can the algorithm be modified somehow?

Answer 1

Yep, you are in trouble. x has no solution in b*x = 1 mod m if b and m have a common divisor. Similarly, in your original problem a/b = y mod m, you are looking for y such that a=by mod m. If a is divisible by gcd(b,m), then you can divide out by that factor and solve for y. If not, then there is no y that can solve the equation (i.e. a/b mod m is not defined).

Answer 2

The reason that b and m have to be coprime is because of the Chinese Remainder Theorem. Basically the problem:

3 * x mod 12

Can be thought of as a compound 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. Thus the answer doesn't exist!

This is due to field theory in abstract algebra. A field is basically a set which has addition, subtraction, multiplication, and division well-defined. A finite field is always of the form GF(p^n), where p is prime and n is a positive integer, and the operations are addition and multiplication modulo p^n. Now, 12 is not a prime power, so your ring is not a field. Thus this problem can't be solved for any b which is not coprime to m.

Answer 3

Check this: http://www.math.harvard.edu/~sarah/magic/topics/division It might help. It explains methods of modular division.