模除法详解：原理、算法与实现

给定三个正整数 a、b 和 M，我们的目标是计算 (a/b) % M。换言之，就是求 (a × b⁻¹) % M 的值，其中 b⁻¹ 是 b 在模 M 下的模逆元。

示例：

> 输入： a = 10, b = 2, M = 13

> 输出： 5

> 解释： 2 在模 13 下的模逆元是 7，所以 (10 / 2) % 13 = (10 × 7) % 13 = 70 % 13 = 5。

>

> 输入： a = 7, b = 4, M = 9

> 输出： 4

> 解释： 4 在模 9 下的模逆元是 7，所以 (7 / 4) % 9 = (7 × 7) % 9 = 49 % 9 = 4。

Try it on GfG Practice<img src="https://www.geeksforgeeks.org/problems/inverse-division/1" alt="redirect icon" />

目录

• [方法 1] 使用费马小定理（当 M 为质数时）O(log M) 时间和 O(1) 空间
• [方法 2] 扩展欧几里得算法 O(log M) 时间和 O(1) 空间

模除法（Modular division） 是指在模运算规则下进行一个数对另一个数的除法运算。与普通算术不同，模运算系统不支持直接除法。相反，除法是通过将被除数乘以除数在给定模数下的模乘法逆元来完成的。

简单来说，为了计算 (a/b) % M，我们要转而计算 (a × b⁻¹) % M，其中 b⁻¹ 是 INLINECODE398a83bf 在模 INLINECODE70e0871e 下的模逆元（即 b × b⁻¹ ≡ 1 mod M）。

阅读本文前，建议先了解以下内容：

• 模乘法逆元
• 扩展欧几里得算法

我们总是可以进行模除法吗？

答案是“不能”。首先，像普通算术一样，除以 0 是无定义的。例如，不允许 4/0。在模运算中，不仅 4/0 是不允许的，而且在模 6 下的 4/12 也是不允许的。原因是，当模数为 6 时，12 同余于 0。

什么时候模除法有定义？

当除数的模逆元存在时，模除法才有定义。整数 ‘x‘ 的逆元是另一个整数 ‘y‘，使得 (x*y) % m = 1，其中 m 是模数。

什么时候逆元存在？

正如我们所讨论的，如果数 ‘a‘ 和模数 ‘m‘ 互质，即它们的最大公约数（GCD）为 1，那么数 ‘a‘ 在模 ‘m‘ 下的逆元存在。

模运算规则：

> (a b) % m = ((a % m) (b % m)) % m

> (a + b) % m = ((a % m) + (b % m)) % m

> (a – b) % m = ((a % m) – (b % m) + m) % m // 加上 m 是为了处理负数

> 但是，

> (a / b) % m 不等同于 ((a % m)/(b % m)) % m

> 例如，a = 10, b = 5, m = 5。 (a / b) % m 是 2，但 ((a % m) / (b % m)) % m 是未定义的。

[方法 1] 使用费马小定理（当 M 是质数时）O(log M) 时间和 O(1) 空间

> 如果模数 INLINECODE06cdf8e0 是一个质数，我们可以利用费马小定理来找到 INLINECODE1a5cc61e 的模逆元。根据该定理，INLINECODE51b8de54 在模 INLINECODE867f844a 下的逆元是 b^(M-2) % M。因此，我们可以使用模幂运算来计算 b^(M-2) % M。

C++


CODEBLOCK_2e6d0594


C


CODEBLOCK_7922c2a8


Java

`

class GfG {
    
    // 二进制求幂（快速幂）
    static int power(int base, int exp, int mod) {
        int result = 1;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1)
                result = (int)((1L * r