同余方程怎么解：从判别式到可运行代码

一次同余方程看起来只是 $ax \equiv b \pmod m$ ，真正要回答的却有三问：有没有解、有几个解、怎么把它们全部找出来。下面按这条线索把原理、手算和代码放在一起。

同余在说什么

整数 $a$ 、 $b$ 对模 $m$ 同余，记作

a \equiv b \pmod m

意思是 $m$ 整除 $a-b$ ，也就是两者除以 $m$ 余数相同。例如 $17 \equiv 5 \pmod{12}$ ，因为 $17-5=12$ 。

同余可以像普通等式那样做加减乘，但不能随便约分。 $6 \equiv 15 \pmod 9$ 成立，两边同除以 $3$ 得到 $2 \equiv 5 \pmod 9$ ，这就错了。正确做法是：约掉的因子必须和模数一起约。

一次同余方程

最常见的是一次同余方程

ax \equiv b \pmod m

其中 $m > 0$ ，未知数 $x$ 是整数。它等价于：存在整数 $k$ ，使得

ax - my = b

这是二元一次不定方程，也叫线性丢番图方程。于是整套理论可以落到一件事上：求 $\gcd(a,m)$ ，再看它能不能整除 $b$ 。

设 $d = \gcd(a,m)$ 。

若 $d \nmid b$ ，无解。
若 $d \mid b$ ，恰有 $d$ 个模 $m$ 互不同余的解。
先求出一个特解 $x_0$ ，通解就是

x \equiv x_0 + \frac{m}{d}\, t \pmod m,\qquad t = 0,1,\dots,d-1

也可以写成对更小的模 $\frac{m}{d}$ 只有一个解：

x \equiv x_0 \pmod{\frac{m}{d}}

为什么是这个判别

$ax - my = b$ 的左边一定是 $d$ 的倍数，因为 $d$ 同时整除 $a$ 和 $m$ 。所以右边 $b$ 也必须是 $d$ 的倍数，否则无解。

反过来，裴蜀定理保证：存在整数 $x,y$ 使 $ax + my = d$ 。两边乘 $b/d$ ，就得到 $b$ 的一组表示，于是原方程有解。

解的个数来自周期。若 $x_0$ 是特解，则

x_0 + \frac{m}{d}t

也都是解。这些解模 $m$ 恰好分成 $d$ 类，对应 $t = 0,1,\dots,d-1$ 。

扩展欧几里得：把特解算出来

普通欧几里得算法只给出 $d$ 。扩展欧几里得在辗转相除的同时，把

d = ax + my

里的系数也记下来。

迭代写法最适合写代码。维护两组系数，使每一步的余数都能写成 $a$ 、 $m$ 的整数组合：

def egcd(a: int, b: int) -> tuple[int, int, int]:
    """返回 (d, x, y)，满足 d = gcd(a, b) = a*x + b*y。"""
    old_r, r = a, b
    old_s, s = 1, 0
    old_t, t = 0, 1
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
        old_t, t = t, old_t - q * t
    return old_r, old_s, old_t

得到 $d,x,y$ 后， $x$ 就是 $ax \equiv d \pmod b$ 的一个解。原方程若 $d \mid b$ ，特解就是

x_0 = x \cdot \frac{b}{d}

再把 $x_0$ 收进 $[0, m)$ 即可。

手算例子

例一：有唯一解

解 $3x \equiv 4 \pmod 7$ 。

$\gcd(3,7)=1$ ，能整除 $4$ ，所以模 $7$ 恰有一解。

用扩展欧几里得：

\begin{aligned} 7 &= 2\cdot 3 + 1 \\ 3 &= 3\cdot 1 + 0 \end{aligned}

回代： $1 = 7 - 2\cdot 3$ ，故 $3\cdot(-2) \equiv 1 \pmod 7$ 。两边乘 $4$ ：

3\cdot(-8) \equiv 4 \pmod 7 \implies x \equiv -8 \equiv 6 \pmod 7

验算： $3\cdot 6 = 18 \equiv 4 \pmod 7$ 。

例二：有多个解

解 $6x \equiv 9 \pmod{15}$ 。

$d=\gcd(6,15)=3$ ，且 $3 \mid 9$ ，所以有 $3$ 个解。先把方程除以 $3$ ：

2x \equiv 3 \pmod 5

$2$ 模 $5$ 的逆元是 $3$ ，因为 $2\cdot 3=6\equiv 1$ 。于是

x \equiv 9 \equiv 4 \pmod 5

特解 $x_0=4$ ，通解

x = 4 + 5t,\qquad t=0,1,2

也就是模 $15$ 的三个解： $4,9,14$ 。

验算： $6\cdot 4=24\equiv 9$ ， $6\cdot 9=54\equiv 9$ ， $6\cdot 14=84\equiv 9 \pmod{15}$ 。

例三：无解

$4x \equiv 2 \pmod 6$ 。 $\gcd(4,6)=2$ ，但 $2$ 不能整除……等等， $2$ 能整除 $2$ ，所以有解。改成 $4x \equiv 3 \pmod 6$ ： $\gcd=2$ 且 $2 \nmid 3$ ，无解。直观理解是：偶数乘任何整数再模 $6$ ，余数只能是偶数，到不了 $3$ 。

模逆元是特例

当 $\gcd(a,m)=1$ 时， $ax\equiv 1 \pmod m$ 有唯一解，这个解叫 $a$ 模 $m$ 的逆元，记作 $a^{-1}$ 。于是

ax \equiv b \pmod m \iff x \equiv a^{-1} b \pmod m

费马小定理给素数模一个快算法：若 $p$ 是素数且 $p \nmid a$ ，则

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

一般模数仍用扩展欧几里得更稳妥。

def modinv(a: int, m: int) -> int:
    d, x, _ = egcd(a, m)
    if d != 1:
        raise ValueError(f"{a} 与 {m} 不互素，没有逆元")
    return x % m

同余方程组：中国剩余定理

一组两两互素的模

\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases}

在模 $M=m_1 m_2 \cdots m_k$ 下恰有一解。构造法是：

M_i = \frac{M}{m_i},\qquad t_i \equiv M_i^{-1} \pmod{m_i},\qquad x = \sum_{i=1}^{k} a_i M_i t_i

最后取 $x \bmod M$ 。

若模数不两两互素，仍可能有解，条件更严：对任意 $i,j$ ，

a_i \equiv a_j \pmod{\gcd(m_i,m_j)}

这时可以用两两合并：先解前两个，得到一个新的同余，再和下一个合并。

例四：韩信点兵

\begin{cases} x \equiv 2 \pmod 3 \\ x \equiv 3 \pmod 5 \\ x \equiv 2 \pmod 7 \end{cases}

$M=105$ ， $M_1=35$ ， $M_2=21$ ， $M_3=15$ 。

$35 \equiv 2 \pmod 3$ ，逆元 $2$ ，因为 $2\cdot 2=4\equiv 1$
$21 \equiv 1 \pmod 5$ ，逆元 $1$
$15 \equiv 1 \pmod 7$ ，逆元 $1$

x = 2\cdot 35\cdot 2 + 3\cdot 21\cdot 1 + 2\cdot 15\cdot 1 = 140+63+30=233 \equiv 23 \pmod{105}

$23$ 除以 $3$ 余 $2$ ，除以 $5$ 余 $3$ ，除以 $7$ 余 $2$ 。

一份可直接用的实现

下面把「单方程」和「方程组」放在一起。单方程返回模 $m$ 下全部互异解；方程组用两两合并，不要求模数互素。

from math import gcd
 
 
def egcd(a: int, b: int) -> tuple[int, int, int]:
    old_r, r = a, b
    old_s, s = 1, 0
    old_t, t = 0, 1
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
        old_t, t = t, old_t - q * t
    return old_r, old_s, old_t
 
 
def solve_linear(a: int, b: int, m: int) -> list[int]:
    """解 a x ≡ b (mod m)，返回 [0, m) 内全部解；无解返回空列表。"""
    if m <= 0:
        raise ValueError("模数必须为正")
    a, b = a % m, b % m
    d, x, _ = egcd(a, m)
    if b % d:
        return []
    x0 = (x * (b // d)) % (m // d)
    step = m // d
    return sorted((x0 + step * t) % m for t in range(d))
 
 
def merge(a1: int, m1: int, a2: int, m2: int) -> tuple[int, int] | None:
    """合并 x ≡ a1 (mod m1) 与 x ≡ a2 (mod m2)。"""
    d = gcd(m1, m2)
    if (a2 - a1) % d:
        return None
    # 解 m1 * t ≡ a2 - a1 (mod m2)
    t = solve_linear(m1, a2 - a1, m2)
    if not t:
        return None
    lcm = m1 // d * m2
    return (a1 + m1 * t[0]) % lcm, lcm
 
 
def solve_system(congruences: list[tuple[int, int]]) -> tuple[int, int] | None:
    """congruences 为 [(a, m), ...]，表示 x ≡ a (mod m)。
    有解返回 (x0, modulus)，无解返回 None。"""
    x, mod = 0, 1
    for a, m in congruences:
        merged = merge(x, mod, a, m)
        if merged is None:
            return None
        x, mod = merged
    return x, mod
 
 
if __name__ == "__main__":
    print(solve_linear(3, 4, 7))          # [6]
    print(solve_linear(6, 9, 15))         # [4, 9, 14]
    print(solve_linear(4, 3, 6))          # []
    print(solve_system([(2, 3), (3, 5), (2, 7)]))  # (23, 105)

跑一下就能对上前面的手算。solve_linear 的时间是欧几里得的 $O(\log m)$ ，再加 $O(d)$ 枚举全部解；方程组是依次合并，模数变大时注意用 Python 整数即可，不必担心溢出。

写代码时容易踩的坑

先取模再求 $\gcd$ 。 $a$ 可能是负数，Python 的 % 会收成非负，扩展欧几里得也能处理负数，但先规范化更不容易错。

特解要乘 $b/d$ ，不是乘 $b$ 。漏掉这一步，方程就解成了 $ax\equiv d$ 而不是 $ax\equiv b$ 。

通解的步长是 $m/d$ ，不是 $d$ 。 $6x\equiv 9\pmod{15}$ 的相邻解相差 $5$ ，不是 $3$ 。

合并方程组时，新模是 $\mathrm{lcm}(m_1,m_2)=m_1 m_2 / \gcd$ ，不是随便乘。模数不互素时，这一步决定解是否唯一。

若只要任意一个解，不必枚举 $d$ 个，返回 $x_0$ 即可。竞赛里常见「输出任意解或 $-1$ 」。

和更高次方程的边界

二次同余 $x^2 \equiv n \pmod p$ 在素数模上可以用 Cipolla 或 Tonelli–Shanks，那是另一套二次剩余的语言。更高次则进入原根、指数和离散对数。一次同余是这些算法的底座：求逆、CRT 拆模、把大模拆成素因子幂，几乎都会先回到 $ax\equiv b$ 。

所以不必把一次同余看成小学奥数。它是数论算法里最常被调用的那一层。把存在性、特解和通解三件事分开，手算和代码就会对得上。