求 a/b mod c

我知道这可能看起来像一个数学问题，但我刚刚在比赛中看到这个问题，我真的很想知道如何解决它。

We have

一个（模c）

and

b（模c）

我们正在寻找商的值

(a/b) (mod c)

有任何想法吗？

在整数环中模C，这些方程是等价的：

A / B (mod C)
A * (1/B) (mod C)
A * B^-1(mod C).

Thus you need to find B^-1, the multiplicative inverse of B modulo C. You can find it using e.g. extended Euclidian algorithm.

请注意，并非每个数字都具有给定模数的乘法逆元。

Specifically, B^-1 exists if and only if gcd(B, C) = 1 (i.e. B and C are coprime).

See also

• 维基百科/模乘法逆元 http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
• 维基百科/扩展欧几里得算法 http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

模乘法逆元：示例

假设我们想要求 3 模 11 的乘法逆元。

也就是说，我们想要找到

x = 3^-1(mod 11)
x = 1/3 (mod 11)
3x = 1 (mod 11)

使用扩展欧几里得算法，你会发现：

x = 4 (mod 11)

因此，3 模 11 的模乘逆为 4。换句话说：

A / 3 == A * 4 (mod 11)

朴素算法：暴力搜索

解决这个问题的一种方法是：

3x = 1 (mod 11)

就是简单地尝试x对于所有值0..11，并查看方程是否成立。对于小模数，该算法可能是可以接受的，但扩展欧几里德算法渐近性要好得多。