说明

感谢YuukiX和qinye_leaf大佬的指正,现已对部分内容进行了修改和补充

本文最后修改时间: 2026/1/23/15:08

模运算（Mod）性质总结

定义

对于任意实数 $( x, y )$，有：

$x \mod y = x - y \left\lfloor \frac{x}{y} \right\rfloor, \quad y \neq 0$

模运算（在一些场合使用符号 % 表示）是一个二元运算。$( x \mod y )$ 的值范围如下：

当 $( y > 0 )$ 时：$( 0 \leq x \mod y < y )$
当 $( y < 0 )$ 时：$( 0 \geq x \mod y > y )$
当 $( y = 0 )$ 时：为避免除以零，定义 $( x \mod 0 = x )$

基本运算规则

模运算与基本四则运算类似（除法除外）：

加法规则：$((a + b) \mod p = (a \mod p + b \mod p) \mod p)$
减法规则：$((a - b) \mod p = (a \mod p - b \mod p + mod) \mod p)$
乘法规则：$((a \times b) \mod p = (a \mod p \times b \mod p) \mod p)$
幂运算规则：$(a^b \mod p = ((a \mod p)^b) \mod p)$
求和规则：由第1个公式可推导出 $(\left(\sum_{i=1}^{n} x_i\right) \mod p = \left(\sum_{i=1}^{n} (x_i \mod p)\right) \mod p)$

对减法运算的解释: 注意此处可能减去后得到负数,因此要先加上一个mod

运算律

A. 结合律

$((a + b) \mod p + c) \mod p = (a + (b + c) \mod p) \mod p$ $((a \times b) \mod p \times c) \mod p = (a \times (b \times c) \mod p) \mod p$

B. 交换律

$(a + b) \mod p = (b + a) \mod p$ $(a \times b) \mod p = (b \times a) \mod p$

C. 分配律

$(a + b) \mod p = (a \mod p + b \mod p) \mod p$ $((a + b) \mod p \times c) \mod p = ((a \times c) \mod p + (b \times c) \mod p) \mod p$

补充性质

同余性质

反身性：$(a \equiv a \pmod{m})$
对称性：如果 $(a \equiv b \pmod{m})$，则 $(b \equiv a \pmod{m})$
传递性：如果 $(a \equiv b \pmod{m})$ 且 $(b \equiv c \pmod{m})$，则 $(a \equiv c \pmod{m})$

模运算与除法

模运算与除法不直接兼容，但有以下性质：

如果 $(ac \equiv bc \pmod{m})$ 且 $(\gcd(c, m) = 1)$，则 $(a \equiv b \pmod{m})$
模逆元：如果 $(\gcd(a, m) = 1)$，则存在整数 $(b)$ 使得 $(ab \equiv 1 \pmod{m})$，称 $(b)$ 为 $(a)$ 模 $(m)$ 的逆元
核心性质：在模运算里除以一个数等于乘以这个数的逆元，即： $c/a≡c×a^{−1} (modm)$ 其中 $a^{-1}$ 是 $a$ 在模 $m$ 下的逆元。

重要前提：模逆元存在的充分必要条件是 $\gcd(a, m) = 1$（即 $a$ 与 $m$ 互质）。如果 $a$ 与 $m$ 不互质，则 $a$ 在模 $m$ 下没有逆元，除法操作无法进行。

计算模逆元的方法

常用的计算模逆元的方法是扩展欧几里得算法，它不仅能求最大公约数，还能找到满足贝祖等式的系数。

示例代码;

#include <iostream>
using namespace std;

// 扩展欧几里得算法求逆元
long long mod_inverse(long long a, long long m) {
    long long m0 = m;
    long long y = 0, x = 1;
    
    if (m == 1) return 0;
    
    while (a > 1) {
        long long q = a / m;
        long long t = m;
        
        m = a % m;
        a = t;
        t = y;
        
        y = x - q * y;
        x = t;
    }
    
    if (x < 0) x += m0;
    
    return (a == 1) ? x : -1; // 如果逆元不存在返回 -1
}

// 使用示例
int main() {
    long long a = 3, m = 7;
    long long inv = mod_inverse(a, m);
    if (inv != -1) {
        cout << a << " 在模 " << m << " 下的逆元是: " << inv << endl;
    } else {
        cout << a << " 在模 " << m << " 下没有逆元" << endl;
    }
    return 0;
}

应用示例

计算 $6 / 3 \pmod{7}$：

先求 $3^{-1} \pmod{7}$：$3 \times 5 = 15 \equiv 1 \pmod{7}$，所以逆元为 5
$6 / 3 \equiv 6 \times 5 = 30 \equiv 2 \pmod{7}$
验证：$2 \times 3 = 6 \equiv 6 \pmod{7}$ ✓

这个性质在密码学、组合数学和算法竞赛中都有广泛应用。

模运算的周期性质

对于任意整数 $(k)$，有 $(a \mod m = (a + km) \mod m)$
模运算的结果具有周期性，周期为模数 $(m)$

逆元的计算

如果是计算单个的逆元，那么使用小费定理：

ll qpow(ll a,b=mod-2) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

计算多个数字的逆元，使用拓展欧几里得算法

LL inv[mod+5]; 
void getInv(LL mod) { 
	inv[1]=1; 
	for(int i=2;i<mod;i++) 
		inv[i]=(mod-mod/i)*inv[mod%i]%mod; 
}

然后如果是一个等式的话，考虑两边同时取逆元
例如：计算$n!$的逆元，得到递推式子 $(i+1)! \equiv i \,!*(i+1) \mod p$ 所以： $inv[(i+1)!]\equiv inv[i]*inv[i+1] \mod p$ 又因为： $inv[i+1]*(i+1)\equiv1\mod p$ 所以把已知的$inv[i+1]$移到左边，得到： $inv[(i+1)!]*(i+1)\equiv inv[i] \mod p$ 这就是求阶乘逆元的递推式了