同余方程与逆元

同余方程与逆元

同余把整数等式推广到模意义下；
裴蜀定理与扩展欧几里得算法则负责判断并构造其中的解。

1 从整数等式到模意义下的等式

普通整数等式要求两个整数完全相同，而同余只关心它们相差多少个模数。

本章主线：同余与剩余类 → 最大公因数与裴蜀定理 → 扩展欧几里得算法 → 一次不定方程 → 线性同余方程 → 乘法逆元 → 中国剩余定理 → 扩展中国剩余定理。

这些内容表面上分别处理方程、除法和方程组，核心始终是整数线性方程 ax+by=cax+by=c。

2 同余与剩余类

2.1 同余的定义

设 mm 为正整数，a,b∈Za,b\in\mathbb Z。若 m∣(a−b)m\mid(a-b)，则称 aa 与 bb 模 mm 同余，记作 a≡b(modm)a\equiv b\pmod m

它等价于 a,ba,b 除以 mm 后具有相同余数。

例如：17≡5(mod12)17\equiv 5\pmod{12}，因为 12∣(17−5)12\mid(17-5)。

2.2 剩余类

整数 aa 模 mm 的剩余类定义为 [a]m={a+km∣k∈Z}[a]_m=\{a+km\mid k\in\mathbb Z\}。

两个整数属于同一个剩余类，当且仅当它们模 mm 同余：[a]m=[b]m⟺a≡b(modm)[a]_m=[b]_m \Longleftrightarrow a\equiv b\pmod m。

同余关系将整数划分为 mm 个剩余类，通常选取 0,1,2,…,m−10,1,2,\ldots,m-1 作为它们的代表元。

所有模 mm 剩余类构成集合 Z/mZ\mathbb Z/m\mathbb Z。

与关系理论的联系

同余是等价关系的典型例子，它按照余数把整数划分为互不相交的等价类。

参见：02_关系

2.3 同余运算

若 a≡b(modm)a\equiv b\pmod m 且 c≡d(modm)c\equiv d\pmod m，则可以直接进行：

a±c≡b±d(modm)ac≡bd(modm)ak≡bk(modm)\begin{align} a \pm c &\equiv b \pm d \pmod m \\ ac &\equiv bd \pmod m \\ a^k &\equiv b^k \pmod{m} \\ \end{align}

因此，加法、减法、乘法和非负整数次幂都可以在过程中不断取模。

除法则需要额外条件。由 ac≡bc(modm)ac\equiv bc\pmod m，设 d=gcd⁡(c,m)d=\gcd(c,m)，一般只能推出 a≡b(modm/d)a\equiv b\pmod{m/d}，

只有当 gcd⁡(c,m)=1\gcd(c,m)=1 时，才能在模 mm 意义下直接约去 cc。

3 欧几里得算法与裴蜀定理

3.1 欧几里得算法

对正整数 a,ba,b，设 a=qb+r,0≤r<ba = qb+r, \quad 0\le r<b，一个整数同时整除 a,ba,b，当且仅当它同时整除 b,rb,r，

因此 gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b)=\gcd(b,a\bmod b) 不断递归，直到余数为 00，即可得到最大公因数。

1
2
3
4
ll gcd( ll a, ll b ) {
	if( b == 0 ) return a;
	else return gcd( b, a % b );
}

时间复杂度为 O(log⁡min⁡(a,b))O(\log\min(a,b))。

3.2 裴蜀定理

裴蜀定理：对不全为 00 的整数 a,ba,b，存在整数 x,yx,y，使得 ax+by=gcd⁡(a,b)ax+by = \gcd(a,b)。

更一般地，方程 ax+by=cax+by = c 有整数解，当且仅当 gcd⁡(a,b)∣c\gcd(a,b)\mid c。

裴蜀定理说明：所有形如 ax+byax+by 的整数线性组合，恰好构成 gcd⁡(a,b)\gcd(a,b) 的全部整数倍。

因此：若 cc 不是 gcd⁡(a,b)\gcd(a,b) 的倍数，方程一定无解，若是其倍数，则可以将等式整体放大得到一组解。

3.3 扩展欧几里得算法

扩展欧几里得算法在计算 gcd⁡(a,b)\gcd(a,b) 的同时，构造一组系数 x,yx,y：ax+by=gcd⁡(a,b)ax+by=\gcd(a,b)

设递归已经求得 bx′+(a mod b)y′=dbx'+(a\bmod b)y' = d，

其中 d=gcd⁡(b,a mod b)=gcd⁡(a,b)d=\gcd(b,a\bmod b)=\gcd(a,b)。

因为 a mod b=a−⌊a/b⌋ba\bmod b=a-\left\lfloor a / b\right\rfloor b，代入可得：d=ay′+b(x′−⌊ab⌋y′)d=ay'+b\left(x'-\left\lfloor\frac ab\right\rfloor y'\right)，

因此新的系数为 x=y′,y=x′−⌊ab⌋y′x=y', \quad y=x'-\left\lfloor\frac ab\right\rfloor y'。

递归边界为 b=0b=0，此时 a⋅1+0⋅0=aa \cdot 1 + 0 \cdot 0 = a。

1
2
3
4
5
6
7
// 扩展欧几里得：求 ax + by = gcd(a,b) 的一组整数解
ll exgcd( ll a, ll b, ll &x, ll &y ) {
    if( b == 0 ) { x = 1, y = 0; return a; }
    ll d = exgcd( b, a % b, y, x );
    y -= a / b * x;
    return d;
}

该写法在递归调用中交换 x, y 的位置，使返回后的 x 已经对应推导中的 y′y'，再修正 y 即可。

若 (x0,y0)(x_0,y_0) 是 ax+by=dax+by=d 的一组解，则对任意 t∈Zt\in\mathbb Z，x=x0+tbd,y=y0−tadx=x_0+t\frac bd, y=y_0-t\frac ad 仍然是解。

扩展欧几里得只负责计算出其中的一组。

4 一次不定方程与线性同余方程

4.1 一次不定方程

考虑整数方程 ax+by=cax + by = c，其中 a,b,c∈Za,b,c\in\mathbb Z，且 a,ba,b 不全为 00。

设 d=gcd⁡(a,b)d=\gcd(a,b)。由裴蜀定理，方程有整数解当且仅当 d∣cd\mid c，若 d∤cd\nmid c，方程无整数解。

若有解，先用 Exgcd 求出一组特解 ax∗+by∗=dax^{*} + by^{*} = d，再乘以 c/dc / d，得到一组特解：

x0=x∗cd,y0=y∗cd.x_0=x^*\frac cd, \qquad y_0=y^*\frac cd.

若 (x0,y0)(x_0,y_0) 是一组特解，则全部整数解为

x=x0+tbd,y=y0−tad,t∈Z.\boxed{ \begin{aligned} x&=x_0+t\frac bd,\\ y&=y_0-t\frac ad, \end{aligned} \qquad t\in\mathbb Z. }

4.2 线性同余方程

形如 ax≡c(modm)ax \equiv c \pmod m 的方程称为一元线性同余方程，其中 m>0m>0。

由同余定义，ax≡c(modm)ax\equiv c\pmod m 等价于 m∣(ax−c)m \mid (ax-c)，也就是存在整数 yy，使得 ax+my=cax + my = c。

所以线性同余方程本质上就是一次不定方程。

因此，设 d=gcd⁡(a,m)d = \gcd(a, m)，方程有解当且仅当 d∣cd \mid c。

若有解，将方程同时除以 dd：adx≡cd(modmd)\displaystyle \frac{a}{d}x \equiv \frac{c}{d} \pmod{ \frac{m}{d} }。

此时 a/da / d 与 m/dm / d 互质，可以乘上逆元，若 x0x_{0} 是一组解，那么 x≡x0(modm/d)x\equiv x_0\pmod{m/d}。

也就是说：解的周期是 m/dm/d，在模 mm 的完整剩余系中，共有 dd 个不同解类。

x0, x0+md, x0+2md,…, x0+(d−1)md.x_0,\ x_0+\frac md,\ x_0+2\frac md, \ldots ,\ x_0+(d-1)\frac md.

特别地，当 d=1d=1 时，方程在模 mm 意义下有唯一解。

5 乘法逆元

5.1 定义与存在条件

若存在整数 xx 满足 ax≡1(modm)ax\equiv1\pmod m，则称 xx 是 aa 模 mm 的乘法逆元，记作 a−1(modm)a^{-1}\pmod m。

逆元是剩余类乘法中的逆元素，不是普通实数意义下的 1/a1/a。

这是线性同余方程在 c=1c = 1 时的特殊情形，因此逆元存在当且仅当 gcd⁡(a,m)=1\gcd(a, m) = 1。

当逆元存在时，它在模 mm 意义下唯一。

模意义下的除法：在 bb 可逆时，ab(modm)\displaystyle \frac ab\pmod m 应理解为 a⋅b−1(modm)a\cdot b^{-1}\pmod m。

5.2 扩展欧几里得求逆元

要求 a−1(modm)a^{-1}\pmod m，等价于求 ax+my=1ax + my = 1

只要 gcd⁡(a,m)=1\gcd(a,m)=1，扩展欧几里得就能给出一组系数 x,yx,y，其中 xx 就是 aa 的一个逆元。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Exgcd 求逆元
ll exgcd( ll a, ll b, ll &x, ll &y ) {
    if( b == 0 ) { x = 1, y = 0; return a; }
    ll d = exgcd( b, a % b, y, x );
    y -= a / b * x;
    return d;
}

ll exgcd_inv( ll a, ll mod ) {
    ll x, y; 
    ll d = exgcd( a, mod, x, y );
    if( d != 1 ) return -1;
    return ( x % mod + mod ) % mod;
}

它只要求 gcd⁡(a,m)=1\gcd(a,m)=1，模数不必是质数。

5.3 费马小定理求逆元

若 pp 是质数且 p∤ap\nmid a，费马小定理给出 ap−1≡1(modp)a^{p-1}\equiv1\pmod p，两边乘以 a−1a^{-1} 得到 a−1≡ap−2(modp)a^{-1}\equiv a^{p-2}\pmod p。

因此可以使用快速幂求逆元。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 费马小定理求逆元
ll mul( ll a, ll b, ll mod ) { 
    return (ll)( (i128)a * b % mod ); 
}

ll qpow( ll a, ll k, ll mod ) {
    ll res = 1 % mod; a %= mod;
    for( ; k; k >>= 1, a = mul( a, a, mod ) )
        if( k & 1 ) res = mul( res, a, mod );
    return res;
}

ll fermat_inv( ll a, ll mod ) { 
    return qpow( a, mod - 2, mod ); 
}

这一方法要求模数为质数，并且 aa 不是模数的倍数。

5.4 线性递推求连续整数的逆元

当模数 pp 为质数且 1≤n<p1\le n<p 时，可以在线性时间内求出 1,2,…,n1,2,\ldots,n 的全部逆元。

设 p=⌊pi⌋i+(p mod i).\displaystyle p=\left\lfloor\frac pi\right\rfloor i+(p\bmod i).

在模 pp 意义下整理，可以得到下列递推式：

inv⁡[i]=(p−⌊pi⌋)inv⁡[p mod i] mod p.\operatorname{inv}[i] =\left(p-\left\lfloor\frac pi\right\rfloor\right) \operatorname{inv}[p\bmod i] \bmod p. 

1
2
3
4
5
6
7
// 线性递推求逆元
ll inv[maxn];

void init_linear( int N, ll mod ) {
    inv[1] = 1;
    for( int i = 2; i <= N; ++ i ) inv[i] = ( mod - mod / i ) * inv[mod % i] % mod;
}

条件 N<pN<p 保证区间内每个整数都可逆。

5.5 一个数组的全部逆元

给定 a1,a2,…,ana_1,a_2,\ldots,a_n，若每个 aia_i 在模 mm 下都可逆，可以只求一次总乘积的逆元，再在线性时间内得到每个元素的逆元。

定义前缀积 Pi=∏j=1iaj\displaystyle P_i=\prod_{j=1}^{i}a_j， 先求 Pn−1P_n^{-1}，然后从右向左维护后缀乘积，即可得到 ai−1=(∏j≠iaj)Pn−1a_i^{-1} = \left(\prod_{j \neq i}a_j\right) P_n^{-1}。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 数组整体求逆：默认 mod 为质数
ll inv[maxn], pre[maxn], suf[maxn];

ll mul( ll a, ll b, ll mod ) { 
    return (ll)( (i128)a * b % mod ); 
}

ll qpow( ll a, ll k, ll mod ) {
    ll res = 1 % mod; a %= mod;
    for( ; k; k >>= 1, a = mul( a, a, mod ) )
        if( k & 1 ) res = mul( res, a, mod );
    return res;
}

ll fermat_inv( ll a, ll mod ) { 
    return qpow( a, mod - 2, mod ); 
}

void init_array( int N, ll val[], ll mod ) {
    pre[0] = 1;
    for( int i = 1; i <= N; ++ i ) pre[i] = mul( pre[i - 1], val[i], mod );
    suf[N] = fermat_inv( pre[N], mod );
    for( int i = N; i >= 1; -- i ) {
        inv[i] = mul( pre[i - 1], suf[i], mod );
        if( i > 1 ) suf[i - 1] = mul( suf[i], val[i], mod );
    }
}

这一方法不要求模数为质数，只要求每个元素都与模数互质。

6 中国剩余定理

考虑同余方程组

{x≡a1(modm1),x≡a2(modm2),⋮x≡an(modmn),\begin{cases} x\equiv a_1\pmod{m_1}, \\ x\equiv a_2\pmod{m_2}, \\ \qquad \vdots \\ x\equiv a_n\pmod{m_n}, \\ \end{cases}

其中 m1,m2,…,mnm_1,m_2,\ldots,m_n 两两互质。

令 M=∏i=1nmi,Mi=Mmi\displaystyle M = \prod_{i=1}^{n}m_i, \quad M_i=\frac M{m_i}，

因为 mim_i 与其他模数两两互质，所以 gcd⁡(Mi,mi)=1\gcd(M_i,m_i)=1，

因此 MiM_i 在模 mim_i 下存在逆元 tit_i：Miti≡1(modmi)M_i t_i \equiv 1 \pmod{m_i}；

定义 ei=Mitie_i=M_i t_i，则 ei≡1(modmi)e_i\equiv1\pmod{m_i}，而对 j≠ij\ne i，由于 mj∣Mim_j\mid M_i，又有 ei≡0(modmj)e_i\equiv0\pmod{m_j}，

因此 x≡∑i=1naiMiti(modM)x\equiv\sum_{i=1}^{n}a_iM_it_i\pmod M 同时满足所有方程。

该方程组的解在模 MM 意义下唯一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 中国剩余定理：x ≡ a[i] (mod m[i])，模数两两互质
ll a[maxn], m[maxn];

ll mul( ll a, ll b, ll mod ) { 
    return (ll)( (i128)a * b % mod ); 
}

ll exgcd( ll a, ll b, ll &x, ll &y ) {
    if( b == 0 ) { x = 1, y = 0; return a; }
    ll d = exgcd( b, a % b, y, x );
    y -= a / b * x;
    return d;
}

ll crt( int N ) {
    ll M = 1, res = 0;
    for( int i = 1; i <= N; ++ i ) M *= m[i];
    for( int i = 1; i <= N; ++ i ) {
        ll Mi = M / m[i], ti, y;
        exgcd( Mi, m[i], ti, y );
        ti = ( ti % m[i] + m[i] ) % m[i];
        ll term = mul( a[i], Mi, M );
        term = mul( term, ti, M );
        res = ( res + term ) % M;
    }
    return ( res + M ) % M;
}

时间主要消耗在 nn 次扩展欧几里得运算上。

7 扩展中国剩余定理

当模数不两两互质时，CRT 的直接构造失效，因为 MiM_i 未必在模 mim_i 下存在逆元。

更一般的方法是不断合并两个同余方程。

假设当前已经得到 x≡r(modM)x\equiv r\pmod M，现在需要加入 x≡a(modm)x\equiv a\pmod m。

由第一个方程，可以写成 x=r+Mkx = r + Mk，代入第二个方程：Mk≡a−r(modm)Mk \equiv a - r \pmod m

于是合并问题重新转化为一个线性同余方程。设 d=gcd⁡(M,m)d=\gcd(M,m)：

  • 若 d∤(a−r)d\nmid(a-r)，两个条件冲突，无解；
  • 若有解，求出一组 k0k_0，新余数为 r+Mk0r+Mk_0；
  • 新模数为 lcm⁡(M,m)=Mm/d\operatorname{lcm}(M,m)=Mm/d。

因此，ExCRT 的本质是反复求解线性同余方程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 扩展中国剩余定理：模数不要求互质
ll a[maxn], m[maxn];

ll mul( ll a, ll b, ll mod ) { 
    return (ll)( (i128)a * b % mod ); 
}

ll exgcd( ll a, ll b, ll &x, ll &y ) {
    if( b == 0 ) { x = 1, y = 0; return a; }
    ll d = exgcd( b, a % b, y, x );
    y -= a / b * x;
    return d;
}

ll excrt( int N ) {
    ll M = m[1], res = a[1];
    for( int i = 2; i <= N; ++ i ) {
        ll x, y, A = M, B = m[i], C = ( a[i] - res % B + B ) % B;
        ll d = exgcd( A, B, x, y );
        if( C % d != 0 ) return -1;
        x = mul( x, C / d, B / d );
        res += x * M, M *= B / d;
        res = ( res % M + M ) % M;
    }
    return res;
}

8 与后续内容的联系

  • 可逆剩余类构成模乘法群；
  • 欧拉定理、费马小定理、阶与原根研究其指数结构；
  • BSGS 求解模意义下的指数方程；
  • Lucas 与 ExLucas 依赖逆元、质数幂分解和 CRT；
  • NTT 依赖模素数下的逆元与原根。

相关内容：

数学 > 数论
#数论/同余
同余方程与逆元
http://miqiu.space/posts/cdb83860/
作者
Miqiu
发布于
2026年7月1日
许可协议