专栏文章

乘法逆元

zzifuneko
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqf0kwn
此快照首次捕获于
2025/12/04 03:43
3 个月前
此快照最后确认于
2025/12/04 03:43
3 个月前
查看原文

乘法逆元的定义

乘法逆元是一个数 bb，对于一个整数 aa，满足以下公式：
a×b≡1 ( mod  m)a×b \equiv 1\ (\bmod\ m)
即 aa 和 bb 的乘积对 mm 取余后等于 11。只有当 aa 和 mm 互质（gcd⁡⁡(a,m)=1\gcd⁡(a,m)=1），乘法逆元才存在。

费马小定理

适用条件：模数 mm 必须是素数，且 aa 和 mm 互质。
公式推导 费马小定理告诉我们，如果 mm 是素数且 aa 和 mm 互质，则：
am−1≡1 ( mod  m) a^{m-1} \equiv 1 \ (\bmod\ m)
将两边同时除以 aa ，得到：
am−2≡a−1 ( mod  m) a^{m-2} \equiv a^{-1} \ (\bmod\ m)
因此，乘法逆元 a−1 ( mod  m)a^{-1}\ (\bmod \ m) 可以用以下公式计算：
a−1≡am−2 ( mod  m) a^{-1} \equiv a^{m-2} \ (\bmod\ m)
例子：求 3 在模 7 下的逆元
模数 m=7m=7，且 mm 是质数，使用公式 am−2 mod  ma^{m-2} \bmod\ m：
3−1≡37−2≡35 ( mod  7) 3^{-1} \equiv 3^{7-2} \equiv 3^5\ (\bmod\ 7)
直接计算 35 mod 7=53^5 \bmod 7 = 5；
逐步计算 35 mod 73^5 \bmod 7：
  1. 32=9≡2 ( mod  7)3^2 = 9 \equiv 2\ (\bmod\ 7)
  2. 34=(32)2=22=4 ( mod  7)3^4 = (3^2)^2 = 2^2 = 4\ (\bmod\ 7)
  3. 35=34×3=4×3=12≡5 ( mod  7)3^5 = 3^4 \times 3 = 4 \times 3 = 12 \equiv 5\ (\bmod\ 7)
∴ 3\therefore\ 3 在模 77 下的逆元是 55。

扩展欧几里得

适用条件：只要 aa 和 mm 互质即可，无需 mm 是素数。

基本原理

扩展欧几里得算法不仅能求最大公约数，还能找到整数 xx 和 yy 使得：
ax+my=gcd⁡(a,m)ax+my=\gcd(a, m)
当 gcd⁡(a,m)=1\gcd(a,m)=1 时，方程变为：
ax+my=1ax+my=1
将方程两边对 mm 取模，那么 mymy 对 mm 取模即 00，得到：
ax≡1 ( mod  m)ax \equiv 1\ (\bmod\ m)
这表明 xx 就是 aa 的乘法逆元。

步骤

1. 普通欧几里得算法：求最大公约数（GCD）
我们先通过普通的欧几里得算法（辗转相除法）求出两个数的最大公约数。假设我们有两个整数 aa 和 bb，我们通过以下递归步骤来计算它们的 GCD：
  1. a=b×q1+r1a=b \times q_1+r_1
  2. b=r1×q2+r2b=r_1\times q_2+r_2
  3. r1=r2×q3+r3r_1=r_2\times q_3+r_3
  4. ⋅⋅⋅⋅⋅⋅······
  5. rn−2=rn−1×qn+rnr_{n-2} = r_{n-1} \times q_n + r_n
  6. 最终直到某一余数为零为止，最后一个非零余数就是 gcd⁡(1,b)\gcd(1,b)。
2. \ 反向推导：扩展过程
在计算 gcd⁡(a,m)\gcd(a,m) 的过程中，我们逐步记录每一次除法的余数和商。然后通过反向推导的方式，得到整数 xx 和 yy，使得：
ax+my=gcd⁡(a,m)ax+my=\gcd(a, m)
在 gcd⁡(a,m)=1\gcd(a,m) = 1 的情况下，xx 就是 aa 对模 mm 的乘法逆元。
例子：求 33 在模 1111 下的逆元
  1. 用普通欧几里得算法（辗转相处法）求 gcd⁡(3,11)\gcd(3,11)：
    · 11=3×3+211 = 3 \times 3 + 2 （11÷3=3⋯211 \div 3 = 3 \cdots 2）
    · 3=2×1+13 = 2 \times 1 + 1（3÷2=1⋯13 \div 2 = 1 \cdots 1）
    · 2=2×1+02 = 2 \times 1 + 0（2÷1=2⋯02 \div 1 = 2 \cdots 0）
    最后 gcd⁡(3,11)=1\gcd(3,11) = 1，表示 33 和 1111 互质，所以乘法逆元存在。
  2. 反向推导（扩展欧几里得算法）：
从第二步（3=2×1+13 = 2 \times 1 + 1）反向推导，计算 xx 和 yy。
从第二步 3=2×1+13 = 2 \times 1 + 1 得到：
1=3−2×11 = 3 - 2 \times 1
然后，将第一步中的 2=111−3×32 = 111-3\times3 带入上式：
1=3−1×(11−3×3)1 = 3 - 1 \times (11 - 3 \times 3)
1=3−1×11+3×31 = 3 - 1 \times 11 + 3 \times 3
1=4×3−1×111 = 4 \times 3 - 1 \times 11
因此得到：
3×4+11×(−1)=13 \times 4 + 11 \times (-1) = 1
∴x=4\therefore x=4，y=−1y=-1。表示 33 的乘法逆元是 44。

乘法逆元的作用

这里列举两个常用的作用。

求解模线性同余方程

乘法逆元可以用来求解模线性同余方程：
ax≡b ( mod  m)ax \equiv b \ (\bmod\ m)
当 aa 和 mm 互质时，方程有唯一解，解法是通过计算 aa 在模 mm 下的逆元 a−1a^{-1}
x≡b⋅a−1 ( mod  m)x \equiv b \sdot a^{-1}\ (\bmod\ m)
示例：
求解3x≡7 ( mod  11)3x \equiv 7\ (\bmod\ 11)：
  1. 先求 33 在  mod  11\bmod\ 11 下的逆元，3−1≡4 ( mod  m)3^{-1} \equiv 4\ (\bmod\ m)
  2. 解方程：x≡7⋅4≡28≡6 ( mod  11)x \equiv 7\sdot 4 \equiv 28 \equiv 6\ (\bmod\ 11)。
∴x=6\therefore x=6

计算分数的模运算

在整数模运算中，分数无法直接处理。例如，计算 ab ( mod  m)\frac{a}{b}\ (\bmod\ m) 时，可以通过乘法逆元将其转化为：
ab≡a⋅b−1 ( mod  m)\frac a b \equiv a\sdot b^{-1}\ (\bmod\ m)
b−1b^{-1} 就是 bb 在模 mm 下的逆元。

代码

费马小定理 + 快速幂

CPP
int qpow(int x, int y)
{
    int res = 1;
    for(; y > 0; x = (x * x) % mod, y >>= 1)
        if(y & 1) res = (res * x) % mod;
    return res;
}
int inv(int a) {return qpow(a, mod - 2);}

扩展欧几里得

CPP
int exgcd(int a, int b, int &x, int &y) 
{
    if(b == 0) {x = 1; y = 0; return a;}
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int inv(int a)
{
    int x, y;
    exgcd(a, mod, x, y);
    return (x + mod) % mod;
}

线性求 1−n\bold{1-n} 逆元

CPP
void init(int m)
{
    inv[1] = 1;
    for(int i = 2; i <= m; ++i) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}

线性求 1−n\bold{1-n} 逆元（妙招）

CPP
void init(int m)
{
    fac[0] = 1;
    for(int i = 1; i <= m; ++i) fac[i] = (fac[i - 1] * i) % mod;
    fac_inv[m] = qpow(fac[m], mod - 2);
    for(int i = m; i >= 1; --i) fac_inv[i - 1] = (fac_inv[i] * i) % mod;
    for(int i = 1; i <= m; ++i) inv[i] = (fac_inv[i] * fac[i - 1]) % mod;
}

线性求 val1,val2,...,valn\bold{\text{val}_1,\text{val}_2,...,\text{val}_n} 逆元

CPP
void init(int m)
{
    fac[0] = 1;
    for(int i = 1; i <= m; ++i) fac[i] = (fac[i - 1] * val[i]) % mod;
    fac_inv[m] = qpow(fac[m], mod - 2);
    for(int i = m; i >= 1; --i) fac_inv[i - 1] = (fac_inv[i] * val[i]) % mod;
    for(int i = 1; i <= m; ++i) inv[i] = (fac_inv[i] * fac[i - 1]) % mod;
}

总结

  • 费马小定理：适合模数 mm 是素数时使用，直接计算 am−2 mod ma^{m-2} \bmod m。
  • 扩展欧几里得算法：通用方法，无论模数是否是素数，只要 aa 和 mm 互质，都可以用。
  • OI Wiki: https://oi-wiki.org/math/number-theory/inverse/

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...