数论基础

【第三讲】

第三讲我们要学习的概念有：

线性同余方程
逆元
费马小定理

一、线性同余方程

如下形式的方程我们称作线性同余方程

ax\equiv b\ (\mod m)

依据定义可知，该方程表示 $ax$ 模 $m$ 等于 $b$ 模 $m$ 的值

\begin{cases} r=ax\mod m & \\ r=b\mod m& \end{cases}

将模运算写成带余除法的形式

\begin{cases} r=ax -mq_{1} & \\ r=b-mq_{2}& \end{cases}

合并化简成线性不定方程

ax+(q_{2}-q_{1})m=b

令 $y=q_{2}-q_{1}$

ax+my=b

可以发现，线性同余方程和线性不定方程是可以相互转化的

回顾之前学过的 裴蜀定理 ， $\gcd(a,m)|b$ 是 $ax+by=c$ 有解的 充要条件

也就是说 $\gcd(a,m)|b$ 也是线性同余方程 $ax\equiv b\ (\mod m)$ 有解的 充要条件

那么代码实现和解线性不定方程一样

以 $84x\equiv 12(\mod 30)$ 为例，等价于求解 $84x+30y=12$

C++：

#include<bits/stdc++.h>
using namespace std;
int exgcd(int a, int b, int& x, int& y){
    x = 1; y = 0;
    int x2 = 0; int y2 = 1;
    while (b != 0){
        int q = a / b;
        tie(a, b) = make_tuple(b, a % b);
        tie(x, x2) = make_tuple(x2, x-x2 * q);
        tie(y, y2) = make_tuple(y2, y-y2 * q);
    }
    return a;
}

void solve(int a, int b, int c, int& x,int& y){
	int d = exgcd(a,b,x,y);
	if (c % d != 0) return;  // 无解
	x *= c / d; y *= c / d;
}

int main(){
	int x,y;
	solve(84,30,12,x,y);
	cout << x << " " << y << endl;
	return 0;
}

Python：

def exgcd(a,b):
    x1, y1 = 1, 0
    x2, y2 = 0, 1
    while b!=0:
        q = a // b
        a, b = b, a % b
        x1, x2 = x2, x1 - x2 * q
        y1, y2 = y2, y1 - y2 * q
    return a, x1, y1

def solve(a,b,c):
    d, x, y = exgcd(a,b)
    if c % d != 0:
        return -1  # 无解
    return x * c // d, y * c // d

二、逆元

2.1 逆元的定义

若整数 $a$ 和 $m$ 满足：存在整数 $x$ 使得

ax\equiv1(\mod m)

ax+my=1

则称 $x$ 为 $a$ 模 $m$ 的逆元，记为 $a^{-1}(\mod m)$

逆元存在的条件是该线性同余方程有解，根据裴蜀定理，该方程有解的充要条件是 $a,m$ 互质，即 $\gcd(a,m)=1$

2.2 逆元的性质

（1） 唯一性

若 $a$ 与 $m$ 互质，则 $a$ 模 $m$ 的逆元在模 $m$ 意义下唯一，即所有逆元均相差 $m$ 的倍数

（2） 逆元的逆元

$a$ 的逆元的逆元是 $a$ 本身，即

(a^{-1})^{-1}=a(\mod m)

（3） 乘积的逆元

若 $a,b$ 逆元均存在

(a\times b)^{-1}=a^{-1}\times b^{-1}(\mod m)

(a\times b^{-1})^{-1}\equiv b\times a^{-1}(\mod m)

若 $k$ 与 $m$ 互质（即 $k^{-1}$ 存在），则

(ka)^{-1}=k^{-1}\cdot a^{-1}(\mod m)

（4） 幂的逆元

对于正整数 $n$ ，有

(a^{n})^{-1}\equiv (a^{-1})^{n}(\mod m)

（5）负数的逆元

若 $a$ 与 $m$ 互质（即 $a$ 的逆元 $a^{-1}$ 存在），则 $-a$ 的逆元满足

(-a)^{-1}\equiv-a^{-1}(\mod m)

（6）等价性

若 $a\equiv b(\mod m)$ ，且 $a,b$ 均与 $m$ 互质（即逆元存在），则

a^{-1}\equiv b^{-1}(\mod m)

若 $a$ 与 $m$ 互质，由模运算的定义 $a\mod m\equiv a(\mod m)$ ，则

(a\mod m)^{-1}\equiv a^{-1}\ (\mod m)

（7） 消去律

若 $a$ 与 $m$ 互质（即 $a^{-1}$ 存在），且 $ab\equiv ac\ (\mod m)$ ，则

b\equiv c\ (\mod m)

（8） 封闭性

若 $a$ 与 $m$ 互质，则 $a^{-1}\ (\mod m)$ 仍与 $m$ 互质

2.3 逆元的计算方法

2.3.1 扩展欧几里得算法

扩展欧几里得算法可直接求解不定方程 $ax+my=1$ ,其中 $x$ 的解即为 $a$ 模 $m$ 的逆元

示例： 求3模7的逆元

因为 $\gcd(3,7)=1$ ，所以逆元存在

解方程 $3x+7y=1$ ，通过扩展欧几里得算法得到 $x=5$

故 $3^{-1}\equiv 5 (\mod 7)$

def exgcd(a, b):
    # 扩展欧几里得算法，返回 (gcd(a,b), x, y) 满足 ax + by = gcd(a,b)
    x1, y1 = 1, 0
    x2, y2 = 0, 1
    while b != 0:
        q = a // b
        a, b = b, a % b
        x1, x2 = x2, x1 - x2 * q
        y1, y2 = y2, y1 - y2 * q
    return a, x1, y1

def mod_inverse(a, m):
    d, x, y = exgcd(a, m)
    if d != 1:
        return None  # 逆元不存在（a与m不互质）
    return x % m  # 调整为模m的最小正逆元

# 示例：求3模7的逆元
print(mod_inverse(3, 7))  # 输出：5

2.3.2 费马小定理

若 $p$ 是质数，且 $a$ 不是 $p$ 的倍数（即 $\gcd(a,p)=1$ ），则

a^{p-1}\equiv1(\mod p)

两边同时除以 $a$ 可得

a^{p-2}\equiv a^{-1}(\mod p)

即当 $m$ 为质数时， $a$ 的逆元为 $a^{m-2}(\mod m)$

示例：求 5 模 7 的逆元

依据费马小定理，逆元为 $5^{7-2}(\mod 7)$ = $5^{5}(\mod 7)$

$5^{5}=3125$ , $3125\mod 7=3125-7\times 446=3125-3122=3$ ，故逆元为 $3$

验证： $5\times 3=15\equiv 1(\mod 7)$

def inverse(a, p):
    # 费马小定理求逆元，p必须是质数且a不是p的倍数
    if a % p == 0:
        return None  # 逆元不存在
    return pow(a, p-2, p)

# 示例：求5模7的逆元（7是质数）
print(inverse(5, 7))  # 输出：3

一般来说，使用费马小定理进行逆元计算会出现非常的大的幂计算，这时候我们需要采用 快速幂算法 来加速计算，

由于python中的 pow 函数底层已经采用快速幂算法进行了优化，故此省略，详细的快速幂算法参考 数论基础十讲第五讲

2.3.3 欧拉定理

事实上，费马小定理是欧拉定理的一种特殊情况，由于篇幅限制，在此仅介绍欧拉定理如何计算逆元，不做深入探究，详细内容见 数论基础入门第四讲

设 $\phi(m)$ 为欧拉函数，表示小于等于 $m$ 且与 $m$ 互质的整数的个数

若 $a$ 与 $m$ 互质，则：

a^{\phi(m)}\equiv 1(\mod m)

两边同时除以 $a$ 可得：

a^{\phi(m)-1}\equiv a^{-1}(\mod m)

即 $a$ 的逆元为

a^{\phi(m)-1}(\mod m)

联系：

当 $m$ 为质数 $p$ 时， $\phi(p)=p-1$ ，欧拉定理退化为费马小定理，因此费马小定理是欧拉定理的特例

2.3.4 线性递推求逆元

在需要计算 $1\sim n$ 模 $p$ 的逆元时（例如组合数计算、多项式问题），逐个用扩展欧几里得或者费马小定理计算效率较低（ $O(nlohp)$ ），而 线性递推求逆元 可将效率优化至 $O(n)$ ，适用模数 $p$ 为质数的场景

线性递推公式：

设 $p$ 是质数， $i$ 是区间 $[1,p-1]$ 中的整数， $inv[i]$ 表示 $i$ 模 $p$ 的逆元，则有递推关系：

inv[1]=1

inv[i]=(p-\lfloor\frac{p}{i}\rfloor)\cdot inv[p \% i] \% p

推导:

对于 $i>2$ ，设 $p=q\cdot i+r$ ，其中 $q=\lfloor\frac{p}{i}\rfloor$ ， $0<r=p\%i<i$ ，因 $p$ 是质数且 $i<p$ ，故 $r \ne 0$

模 $p$ 意义下， $q\cdot i+r\equiv 0(\mod p)$ ，整理得
$r\equiv-q\cdot i(\mod p)$
两边同时乘上 $i^{-1}\cdot r^{-1}$ （因 $r<i$ ， $inv[r]$ 已通过递推求得）
$i^{-1}\equiv -q\cdot r^{-1}(\mod p)$
带入 $q=\lfloor \frac{p}{i} \rfloor,r=p\%i$ ，并调整符号，避免负数
$inv[i]=(p-q)\cdot inv[r]\%p=(p-\lfloor \frac{p}{i} \rfloor)\cdot inv[p\%i]\%p$

C++:

#include <bits/stdc++.h>
using namespace std;

// 线性递推求逆元：求1~n模p的逆元（p必须是质数，且n < p）
vector<int> linear_inv(int n, int p) {
    vector<int> inv(n + 1);  // 存储inv[1]到inv[n]的逆元
    inv[1] = 1;  // 1的逆元是1（1*1≡1 mod p）
    for (int i = 2; i <= n; ++i) {
        // 核心公式：inv[i] = (p - p/i) * inv[p%i] % p
        // 用1LL将中间结果转换为long long，避免乘法溢出
        inv[i] = ( (p - p / i) * 1LL * inv[p % i] ) % p;
    }
    return inv;
}

int main() {
    int p = 7;  // 质数模
    int n = 5;  // 求1~5的逆元
    vector<int> inv = linear_inv(n, p);
    
    // 输出1~5模7的逆元
    for (int i = 1; i <= n; ++i) {
        cout << inv[i] << " ";
    }
    // 输出：1 4 5 2 3
    return 0;
}

Python:

def linear_inv(n, p):
    # 求1~n模p的逆元（p为质数，且n < p）
    inv = [0] * (n + 1)
    inv[1] = 1
    for i in range(2, n + 1):
        inv[i] = (p - p // i) * inv[p % i] % p
    return inv

# 示例：求1~5模7的逆元
p = 7
inv = linear_inv(5, p)
print(inv[1:6])  # 输出：[1,4,5,2,3]（验证：2*4=8≡1, 3*5=15≡1, 4*2=8≡1, 5*3=15≡1 mod7）

2.3.5 线性递推求阶乘的逆元

如果我们需要预处理 阶乘的逆元 ，即 $inv\_fact[i]=(i!)^{-1}\mod MOD$ ，有如下公式

inv\_fact[i]=inv\_fact[i+1]\cdot(i+1) \% MOD

推导：

根据逆元定义，有

i!\cdot(i!)^{-1}\equiv1(\mod MOD)

同时，由于

(i+1)!=i!\cdot(i+1)

两边取逆元

((i+1)!)^{-1}\equiv (i!)^{-1} \cdot (i+1)^{-1}\ (\mod MOD)

两边同时乘以 $(i+1)$ ，得到

(i!)^{-1}\equiv ((i+1)!)^{-1}\cdot (i+1) \ (\mod MOD)

即

inv\_fact[i]=inv\_fact[i+1]\cdot(i+1) \% MOD

2.4 逆元的应用

逆元的 核心作用 是 将模运算中的“除法”转化为”乘法”

例如，计算 $\frac{a}{b}\mod m$ ，若 $\gcd(b,m)=1$ ，存在逆元，则

\frac{a}{b}\mod m=a\times b^{-1}\mod m

又例如，在 $C(n,k)\mod p=\frac{n!}{k!\cdot (n-k)!}$ 中，由于阶乘的除法无法直接在模运算中进行，需要用逆元转换成乘法

C(n,k)\mod p=(n!\cdot inv[k!]\cdot inv[(n-k)!])\mod p