找到a / b模c [英] finding a/b mod c

问题描述

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

I know this may seem like a math question but i just saw this in a contest and I really want to know how to solve it.

我们有

We have

a（mod c）

a (mod c)

/ p>

and

b（mod c）

b (mod c)

我们正在寻找商的值

（a / b）（mod c）

(a/b) (mod c)

任何想法？

推荐答案

c $ c> C ，这些等式是等价的：

In the ring of integers modulo C, these equations are equivalent:

A / B mod C）

A *（1 / B）（mod C）

A * B ^-1 （mod C）。

因此，您需要找到 B ^-1 $ c> B modulo 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.

注意，并不是每个数字都有一个乘数的倒数。

Note that not every number has a multiplicative inverse for the given modulus.

= 1 （）时， B -1 即 B 和 C 是互斥的）。

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

• 维基百科/模块乘法逆< a>


• 维基百科/扩展欧几里德算法

• Wikipedia/Modular multiplicative inverse
• Wikipedia/Extended Euclidian algorithm

找到3的乘数倒数11。

Suppose we want to find the multiplicative inverse of 3 modulo 11.

也就是说，我们要找到

x = 3 ^-1 （mod 11）

x = 1/3（mod 11）

3x = 1（mod 11）

使用扩展的欧几里德算法，您会发现：

Using extended Euclidian algorithm, you will find that:

x = 4（mod 11）

，模3的模乘11是4.换句话说：

Thus, the modular multiplicative inverse of 3 modulo 11 is 4. In other words:

A / 3 == A * 4（mod 11）

---

强力搜索

一种解决方法：

---

Naive algorithm: brute force search

One way to solve this:

3x = 1（mod 11）

是简单地尝试 x 对于所有值 0..11 ，并查看方程是否成立。对于小的模量，这种算法可能是可以接受的，但是扩展的欧几里得算法是渐进的。

Is to simply try x for all values 0..11, and see if the equation holds true. For small modulus, this algorithm may be acceptable, but extended Euclidian algorithm is much better asymptotically.

这篇关于找到a / b模c的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！