逆元的三种核心求解算法：原理、证明与实现

前置定义与核心定理

模乘法逆元的严格定义

设 $m$ 为正整数，对于整数 $a$ ，若存在整数 $x$ 满足同余式：

$a \cdot x \equiv 1 \pmod{m}$

则称 $x$ 为 $a$ 在模 $m$ 下的乘法逆元，记作 $\mathrm{inv}(a) \pmod{m}$ 。

逆元存在性充要条件

整数 $a$ 在模 $m$ 下存在乘法逆元的充要条件是 $\gcd(a,m)=1$ ，即 $a$ 与 $m$ 互质。

推论：若模数 $p$ 为素数，则区间 $[1,p-1]$ 内的所有整数均与 $p$ 互质，其模 $p$ 逆元必然存在。

核心应用性质

若 $\mathrm{inv}(b) \pmod{m}$ 存在（即 $\gcd(b,m)=1$ ），则模运算中的除法可等价转化为模乘法，满足：

$\frac{a}{b} \equiv a \cdot \mathrm{inv}(b) \pmod{m}$

性质推导（严格数学证明）

证明核心基于逆元的严格定义与同余式的基本性质，步骤如下：

1. 由逆元的定义（1.1节），因 $\mathrm{inv}(b) \pmod{m}$ 存在，故满足: $$ b \cdot \mathrm{inv}(b) \equiv 1 \pmod{m} \tag{1}$$

2. 定义模除法的等价形式：设 $\frac{a}{b} \equiv c \pmod{m}$ （其中 $c$ 为整数），根据同余式的定义，上式等价于“存在整数 $k$ ，使得 $a = b \cdot c + k \cdot m$ ”（避免直接出现分数形式的模运算，符合数论严谨性）。

3. 对 $a = b \cdot c + k \cdot m$ 两边同时取模 $m$ ，根据模运算“和的模等于模的和的模”性质，以及 $k \cdot m \equiv 0 \pmod{m}$ ，化简得：

   $$a \equiv b \cdot c \pmod{m} \tag{2}$$

4. 对式 (2) 两边同时乘以 $\mathrm{inv}(b)$ ，根据同余式的乘法性质（若 $x \equiv y \pmod{m}$ ，则对任意整数 $z$ ，有 $x \cdot z \equiv y \cdot z \pmod{m}$ ），可得：

$$a \cdot \mathrm{inv}(b) \equiv b \cdot c \cdot \mathrm{inv}(b) \pmod{m} \tag{3}$$

5. 将式 (1) 代入式 (3)，利用乘法结合律，右边化简为：

   $$b \cdot c \cdot \mathrm{inv}(b) = c \cdot (b \cdot \mathrm{inv}(b)) \equiv c \cdot 1 \equiv c \pmod{m}$$

6. 结合步骤2中 $\frac{a}{b} \equiv c \pmod{m}$ 的定义，可得：

   $$a \cdot \mathrm{inv}(b) \equiv \frac{a}{b} \pmod{m}$$

即 $\frac{a}{b} \equiv a \cdot \mathrm{inv}(b) \pmod{m}$ ，推导完毕。

---

扩展欧几里得算法求解逆元

适用条件

仅要求 $\gcd(a,m)=1$ ，对模数 $m$ 无素性要求，是模逆元的通用求解算法。

数学原理与证明

贝祖定理

对任意整数 $a,b$ ，必然存在整数 $x,y$ ，使得：

$a \cdot x + b \cdot y = \gcd(a,b)$

该定理是扩展欧几里得算法的理论基础。

同余式到不定方程的等价转化

逆元的定义式 $a \cdot x \equiv 1 \pmod{m}$ 等价于：存在整数 $y$ ，使得

$a \cdot x - 1 = m \cdot y$

移项后得到二元一次不定方程：

$a \cdot x + m \cdot y = 1$

结合逆元存在性条件 $\gcd(a,m)=1$ ，该方程符合贝祖定理的有解条件，其整数解 $x$ 即为 $a$ 在模 $m$ 下的逆元。

扩展欧几里得算法的递归推导

普通欧几里得算法的核心是辗转相除： $\gcd(a,b) = \gcd(b, a \bmod b)$ 。

设对于 $\gcd(b, a \bmod b)$ ，存在整数解 $x_1,y_1$ 满足：

$b \cdot x_1 + (a \bmod b) \cdot y_1 = \gcd(a,b)$

由带余除法， $a \bmod b = a - \lfloor \frac{a}{b} \rfloor \cdot b$ ，代入上式得：

$b \cdot x_1 + \left(a - \lfloor \frac{a}{b} \rfloor \cdot b\right) \cdot y_1 = \gcd(a,b)$

整理后得到原方程的解：$\begin{cases}x = y_1 \\ y = x_1 - \lfloor \frac{a}{b} \rfloor \cdot y_1 \end{cases}$

递归终止条件为 $b=0$ ，此时 $\gcd(a,0)=a$ ，对应解为 $x=1, y=0$ 。

算法实现

#include <iostream>
using namespace std;
typedef long long ll;

/**
 * @brief 扩展欧几里得算法
 * @param a 整数a
 * @param b 整数b
 * @param x 引用返回贝祖方程的解x
 * @param y 引用返回贝祖方程的解y
 * @return gcd(a,b)
 */
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

/**
 * @brief 扩展欧几里得法求解模逆元
 * @param a 待求逆元的整数a
 * @param m 模数m
 * @return 若逆元存在，返回模m的最小非负逆元；否则返回-1
 */
ll mod_inv_exgcd(ll a, ll m) {
    ll x, y;
    ll g = exgcd(a, m, x, y);
    if (g != 1) return -1; // 不互质，逆元不存在
    return (x % m + m) % m; // 将解映射到模m的最小非负剩余系
}

复杂度分析

算法的递归深度与普通欧几里得算法一致，时间复杂度为 $O(\log \min(a,m))$ 。

---

费马小定理法求解逆元

适用条件

模数 $p$ 为素数，且 $\gcd(a,p)=1$ （即 $a$ 不是 $p$ 的倍数）。

数学原理与证明

费马小定理

若 $p$ 为素数，且整数 $a$ 与 $p$ 互质，则：

$a^{p-1} \equiv 1 \pmod{p}$

费马小定理的严谨证明

定义模 $p$ 的最小正简化剩余系 $S = {1,2,\dots,p-1}$ ，该集合满足：

1. 集合内所有元素均与 $p$ 互质；

2. 任意两个元素模 $p$ 不同余。

构造新集合 $S' = {a\cdot1, a\cdot2, \dots, a\cdot(p-1)}$ ，下证 $S'$ 模 $p$ 后是 $S$ 的一个排列：

• 反证法：假设存在 $i \neq j$ 使得 $a\cdot i \equiv a\cdot j \pmod{p}$ ，则 $a(i-j) \equiv 0 \pmod{p}$ 。由于 $\gcd(a,p)=1$ ，故 $i-j \equiv 0 \pmod{p}$ ，与 $i,j \in [1,p-1]$ 且 $i \neq j$ 矛盾。

• 因此 $S'$ 模 $p$ 后与 $S$ 包含完全相同的元素，仅顺序不同。

对两个集合的所有元素分别求乘积，模 $p$ 结果相等:
$$\prod{k=1}^{p-1} k \equiv \prod{k=1}^{p-1} (a\cdot k) \pmod{p}$$

整理得：

$(p-1)! \equiv a^{p-1} \cdot (p-1)! \pmod{p}$

由于 $p$ 为素数， $\gcd((p-1)!, p)=1$ ，故可在同余式两边约去 $(p-1)!$ ，最终得到：

$a^{p-1} \equiv 1 \pmod{p}$

费马小定理得证。

逆元公式推导

将费马小定理的结论拆分为：

$a \cdot a^{p-2} \equiv 1 \pmod{p}$

对比逆元的定义式，直接得到逆元公式：

$\mathrm{inv}(a) \equiv a^{p-2} \pmod{p}$

算法实现

逆元公式的核心是大指数模运算，采用快速幂算法实现，时间复杂度为对数级别。

#include <iostream>
using namespace std;
typedef long long ll;

/**
 * @brief 快速幂算法：计算 (base^exponent) % mod
 * @param base 底数
 * @param exponent 指数
 * @param mod 模数
 * @return 模运算结果
 */
ll qpow(ll base, ll exponent, ll mod) {
    ll res = 1;
    base %= mod;
    while (exponent > 0) {
        if (exponent & 1) res = res * base % mod;
        base = base * base % mod;
        exponent >>= 1;
    }
    return res;
}

/**
 * @brief 费马小定理法求解模逆元
 * @param a 待求逆元的整数a
 * @param p 素数模数p
 * @return 若逆元存在，返回模p的最小非负逆元；否则返回-1
 */
ll mod_inv_fermat(ll a, ll p) {
    if (a % p == 0) return -1; // a是p的倍数，逆元不存在
    return qpow(a, p - 2, p);
}

复杂度分析

快速幂算法的时间复杂度为 $O(\log p)$ ，与扩展欧几里得算法同阶，代码实现更简洁，是素数模数下的首选单次逆元求解方案。

---

线性递推法求解逆元

适用条件

模数 $p$ 为素数，需要批量求解区间 $[1,n]$ （ $n < p$ ）内所有整数的模 $p$ 逆元。

数学原理与推导

对于素数 $p$ 和任意整数 $i \in [2,p-1]$ ，对 $p$ 和 $i$ 做带余除法：

$p = k \cdot i + r, \quad k = \lfloor \frac{p}{i} \rfloor, \quad 0 < r < i$

将上式转化为模 $p$ 下的同余式：

$0 \equiv k \cdot i + r \pmod{p}$

移项得：

$r \equiv -k \cdot i \pmod{p}$

由于 $i,r \in [1,p-1]$ ，其逆元必然存在，在同余式两边同时乘以 $\mathrm{inv}(i) \cdot \mathrm{inv}(r)$ ，得：

$r \cdot \mathrm{inv}(i) \cdot \mathrm{inv}(r) \equiv -k \cdot i \cdot \mathrm{inv}(i) \cdot \mathrm{inv}(r) \pmod{p}$

化简后得到：

$\mathrm{inv}(i) \equiv -k \cdot \mathrm{inv}(r) \pmod{p}$

将 $k = \lfloor \frac{p}{i} \rfloor$ 、 $r = p % i$ 代入，并利用模运算性质 $-x \equiv p-x \pmod{p}$ 将负号转化为正，得到最终递推公式：

$\mathrm{inv}(i) = \left(p - \lfloor \frac{p}{i} \rfloor\right) \cdot \mathrm{inv}(p \% i) \% p$

边界条件： $\mathrm{inv}(1) = 1$ ，即1的模任意数逆元均为1。

注：由于 $r = p % i < i$ ，递推过程中 $\mathrm{inv}(r)$ 已在之前的步骤中计算完成，保证了递推的可行性。

算法实现

#include <iostream>
using namespace std;
typedef long long ll;

const int MAXN = 1e6 + 10; // 按需调整数组上限
ll inv[MAXN];

/**
 * @brief 线性递推法批量求解模逆元
 * @param n 求解区间[1,n]的逆元
 * @param p 素数模数p
 */
void mod_inv_linear(int n, ll p) {
    inv[1] = 1; // 边界条件
    for (int i = 2; i <= n; ++i) {
        inv[i] = (p - p / i) * inv[p % i] % p;
    }
}

复杂度分析

算法仅需一次遍历即可完成区间内所有逆元的求解，时间复杂度为 $O(n)$ ，是批量求解逆元的最优复杂度，显著优于 $n$ 次单次求解的 $O(n \log p)$ 复杂度。

---

算法选型总结

算法	模数要求	核心适用场景	时间复杂度	优势
扩展欧几里得算法	无素性要求，仅需 $\gcd(a,m)=1$	通用场景、非素数模数下单次逆元求解	$O(\log \min(a,m))$	通用性最强，无素数约束
费马小定理法	必须为素数，且 $\gcd(a,p)=1$	素数模数下单次逆元求解	$O(\log p)$	代码简洁，实现成本低，竞赛场景首选
线性递推法	必须为素数，且求解区间 $[1,n] < p$	素数模数下批量求解区间逆元	$O(n)$	批量求解效率最优，适合组合数、DP等大规模逆元应用场景

---