How to calculate "modular multiplicative inverse" when the denominator is not co-prime with m?
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
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).