numbers - 当分母与m不互质时如何计算 "modular multiplicative inverse"？

Question

我需要计算 (a/b) mod m 哪里 a 和 b 是非常大的数字。

我想做的是计算 (a mod m) * (x mod m) ，其中 x 是 modular inverse的 b .

我尝试使用 Extended Euclidean algorithm ，但是当 b 和 m 不是互质时怎么办？
具体是mentioned b 和 m 需要互质。

我尝试使用代码 here ，并意识到例如:
3 * x mod 12 对于 的任何值根本不可能x ， 它不存在!

我该怎么办？ 可以以某种方式修改算法吗？

Answer 1

是的，你有麻烦了。 x 在 b*x = 1 mod m 中没有解如果 b 和 m 有公约数。同样，在您原来的问题 a/b = y mod m 中，您正在寻找 y 使得 a=by mod m .如果 a 可以被 gcd(b,m) 整除，然后您可以除以该因子并求解 y。如果不是，则没有 y 可以解方程(即 a/b mod m 未定义)。