找到一个/ b mod c

Question

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

我们有

a(mod c)

和

b(mod c)

我们正在寻找商的价值

(a/b)(mod c)

有任何想法吗？

Answer 1

在整数模数模中C,这些等式是等价的:

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

因此,你需要找到B^-1,B模数的乘法逆C.您可以使用例如扩展欧几里德算法找到它.

请注意,并非每个数字都具有给定模数的乘法逆.

具体而言,当且仅当(即并且是互质)存在时,B^-1存在.gcd(B, C) = 1BC

也可以看看

• 维基百科/模块乘法逆
• 维基百科/扩展欧几里德算法

模数乘法逆:示例

假设我们想找到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,看看方程式是否成立.对于小模数,该算法可能是可接受的,但扩展欧几里德算法渐近更好.