一元线性同余方程组 - 编程数学 | C++ & Algorithm 编程研习社

同余方程组：把多个条件合并成一个

当你遇到一个数要同时满足好几个余数条件时，比如：一包糖果，3个3个地数剩2颗，5个5个地数剩3颗，7个7个地数剩2颗。你最少有多少颗糖果？这就是一个一元线性同余方程组问题。方程组由多个形如 $x \equiv a_i \pmod{m_i}$ 的方程组成，目标是找到同时满足所有方程的数 $x$ 。这类问题在生活中很常见：分东西、排队编号、日历推算等等。解方程组就像解开连环锁，我们可以用两两合并法，一步步把所有条件压缩成一个。

1. 数学原理和公式推导

1.1 什么是同余方程组？

你已经知道单个同余方程是 $a \cdot x \equiv b \pmod{m}$ 。但实际中常遇到更复杂的情况：一个数要满足多个不同的余数条件。比如中国古代的“物不知数”问题：

有一堆物品，3个3个地数剩2个，5个5个地数剩3个，7个7个地数剩2个，问这堆物品有多少个？

这个问题的数学模型就是：

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

这就是一个一元线性同余方程组。这里每个方程都是最简单的形式：未知数 $x$ 直接模某个数等于一个常数，即 $x \equiv a_i \pmod{m_i}$ 。更一般地，方程也可以是 $a_i \cdot x \equiv b_i \pmod{m_i}$ ，但我们先学这种最简单的标准形式。对于一般形式，可以先通过求解每个方程得到 $x \equiv r_i \pmod{m_i'}$ ，再合并。

1.2 如何解两方程？

先看只有两个方程的情况：

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

我们想找到同时满足这两个条件的 $x$ 。如果 $m_1$ 和 $m_2$ 不互素，可能无解或有多个解。为了简单，我们先假设 $m_1$ 和 $m_2$ 互素（即最大公因数为1），这种情况一定有解。

思路：从第一个方程知道 $x = a_1 + m_1 \cdot k$ （ $k$ 是某个整数），代入第二个方程：

a_1 + m_1 \cdot k \equiv a_2 \pmod{m_2}

整理得：

m_1 \cdot k \equiv a_2 - a_1 \pmod{m_2}

这就是一个关于 $k$ 的一元线性同余方程！我们可以用之前学过的方法（扩展欧几里得）解出 $k$ 模 $m_2$ 的解。假设解为 $k \equiv k_0 \pmod{m_2}$ ，那么：

x = a_1 + m_1 \cdot (k_0 + t \cdot m_2) = (a_1 + m_1 \cdot k_0) + (m_1 \cdot m_2) \cdot t

即：

x \equiv a_1 + m_1 \cdot k_0 \pmod{m_1 \cdot m_2}

这样我们就把两个方程合并成了一个方程： $x \equiv \text{new\_a} \pmod{\text{new\_m}}$ ，其中 $\text{new\_m} = m_1 \cdot m_2$ ， $\text{new\_a} = a_1 + m_1 \cdot k_0$ （需要模到 $[0, \text{new\_m})$ 内）。

生活例子：假设你有一些零花钱，每次数5元还剩2元，每次数8元还剩3元。即：

x \equiv 2 \pmod{5}, \quad x \equiv 3 \pmod{8}

设 $x = 2 + 5k$ ，代入第二个： $2 + 5k \equiv 3 \pmod{8} \Rightarrow 5k \equiv 1 \pmod{8}$ 。5模8的逆元是5（因为 $5 \times 5 = 25 \equiv 1 \pmod{8}$ ），所以 $k \equiv 5 \times 1 = 5 \pmod{8}$ 。取 $k_0 = 5$ ，则 $x = 2 + 5 \times 5 = 27$ 。合并后 $x \equiv 27 \pmod{40}$ 。最小的正整数解是27元。

如果 $m_1$ 和 $m_2$ 不互素，例如 $m_1 = 4, m_2 = 6$ ，我们需要先判断解是否存在，并且合并后的模数变成它们的最小公倍数（LCM）。后面在扩展中国剩余定理中会详细讲。

1.3 多个方程的合并

我们可以重复使用上述方法：先合并前两个方程得到一个方程，然后再和第三个方程合并，以此类推，直到所有方程合并成一个。如果中间某一对无解，整个方程组就无解。

常见错误：有些新手以为可以直接把每个方程的模数相乘作为新模数，但只适用于模数两两互素的情况。如果模数不互素，直接用乘积会导致错误结果（可能多出不存在的解或漏掉真正的解）。正确的做法是每次合并后模数变成当前两模数的最小公倍数。

1.4 回到“物不知数”例子

用两两合并法解：

先合并前两个（模3和模5）：
$x \equiv 2 \pmod{3}, \quad x \equiv 3 \pmod{5}$
设 $x = 2 + 3k$ ，代入第二个： $2 + 3k \equiv 3 \pmod{5} \Rightarrow 3k \equiv 1 \pmod{5}$ 。3的逆元模5是2（因为 $3 \times 2 = 6 \equiv 1$ ），所以 $k \equiv 2 \pmod{5}$ 。取 $k_0 = 2$ ，则 $x = 2 + 3 \times 2 = 8$ ，合并后 $x \equiv 8 \pmod{15}$ 。
再和第三个方程 $x \equiv 2 \pmod{7}$ 合并：
$x \equiv 8 \pmod{15}, \quad x \equiv 2 \pmod{7}$
设 $x = 8 + 15k$ ，代入： $8 + 15k \equiv 2 \pmod{7} \Rightarrow 15k \equiv -6 \equiv 1 \pmod{7}$ （因为 $-6 \mod 7 = 1$ ）。 $15 \mod 7 = 1$ ，所以 $1 \cdot k \equiv 1 \pmod{7} \Rightarrow k \equiv 1 \pmod{7}$ 。取 $k_0 = 1$ ，则 $x = 8 + 15 \times 1 = 23$ ，合并后 $x \equiv 23 \pmod{105}$ 。所以最小的正整数解是23。

2. 新手容易犯的错误

忘记检查无解条件：在合并两个方程时，如果 $a_2 - a_1$ 不能被 $m_1, m_2$ 的最大公因数整除，则该方程无解。必须检查并返回无解，否则会算出错误答案。
模数溢出：当模数较大时，乘积 $m_1 \times m_2$ 可能超过 int 范围（大约21亿）。C++ 中必须使用 long long，Python 中整数可以无限大，但也要注意性能。
认为所有模数互素才是唯一解：实际上模数不互素也可能有解（只要相容），合并后的模数是最小公倍数，而不是乘积。很多人直接相乘导致新模数太大，得到错误的解集合。
忽略负数的模运算：在计算 k 或 new_rem 时，负数结果需要调整到非负范围。例如 C++ 中 % 运算对负数结果可能是负值，要手动加模数保证非负。

3. 编程实现

我们将编写一个函数 solve_congruence_system，它接收两个列表：余数列表 rem 和模数列表 mod，返回合并后的 (remainder, modulus) 或者报告无解。这里我们先假设模数两两互素（简化），但代码中也处理了不互素的情况（会正确判断无解并输出 LCM）。

C++ 代码示例（带详细注释）

#include <iostream>
#include <vector>
using namespace std;

// 扩展欧几里得，返回 gcd(a,b)，并设置 x,y 满足 a*x + b*y = gcd
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;                 // 回溯更新 y
    return d;
}

// 合并两个同余方程: x ≡ a1 (mod m1), x ≡ a2 (mod m2)
// 如果成功，返回 true，并通过引用设置 a = 新余数，m = 新模数（lcm）
// 如果无解，返回 false
bool merge(int a1, int m1, int a2, int m2, long long &a, long long &m) {
    // 解方程 m1 * k ≡ a2 - a1 (mod m2)
    int x0, y0;                     // 用于存放 exgcd 的结果
    int d = exgcd(m1, m2, x0, y0);  // d = gcd(m1, m2)
    int diff = a2 - a1;             // 差值为 a2 - a1
    if (diff % d != 0) return false; // 无解情况

    // 计算特解 k0 (模 m2/d)
    int mod = m2 / d;
    // x0 是 m1*x0 + m2*y0 = d 的解，乘以 (diff/d) 后得到 k 的一个特解
    long long k = (long long)x0 * (diff / d) % mod;
    if (k < 0) k += mod;            // 调整到非负

    // 新模数是 lcm(m1, m2) = m1 / d * m2
    long long new_mod = (long long)m1 / d * m2;
    // 新余数 = a1 + m1 * k (模 new_mod)
    long long new_rem = (a1 + (long long)m1 * k) % new_mod;
    if (new_rem < 0) new_rem += new_mod;

    a = new_rem;
    m = new_mod;
    return true;
}

// 求解同余方程组，返回合并后的 (rem, mod) 或 (-1, -1) 表示无解
pair<long long, long long> solve_system(const vector<int>& rem, const vector<int>& mod) {
    long long result_rem = rem[0];   // 当前合并后的余数
    long long result_mod = mod[0];   // 当前合并后的模数
    for (size_t i = 1; i < rem.size(); ++i) {
        if (!merge(result_rem, result_mod, rem[i], mod[i], result_rem, result_mod)) {
            return {-1, -1};         // 无解标记
        }
    }
    return {result_rem, result_mod}; // 返回最终解
}

int main() {
    // 物不知数问题: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
    vector<int> rem = {2, 3, 2};
    vector<int> mod = {3, 5, 7};
    auto [r, m] = solve_system(rem, mod); // C++17 结构化绑定
    if (r == -1) {
        cout << "无解" << endl;
    } else {
        cout << "解为: x ≡ " << r << " (mod " << m << ")" << endl; // 预期 23 mod 105
    }

    // 测试无解情况: x ≡ 1 (mod 2), x ≡ 2 (mod 4)
    rem = {1, 2};
    mod = {2, 4};
    tie(r, m) = solve_system(rem, mod);
    if (r == -1) {
        cout << "无解" << endl;
    } else {
        cout << "解为: x ≡ " << r << " (mod " << m << ")" << endl;
    }

    // 测试模数不互素但有解的情况: x ≡ 2 (mod 6), x ≡ 8 (mod 10)  -> 解 x ≡ 8 (mod 30)
    rem = {2, 8};
    mod = {6, 10};
    tie(r, m) = solve_system(rem, mod);
    if (r == -1) {
        cout << "无解" << endl;
    } else {
        cout << "解为: x ≡ " << r << " (mod " << m << ")" << endl; // 预期 8 mod 30
    }

    return 0;
}

Python 代码示例（带详细注释）

def exgcd(a, b):
    """扩展欧几里得，返回 (g, x, y) 使得 a*x + b*y = g"""
    if b == 0:
        return (a, 1, 0)
    else:
        g, x1, y1 = exgcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return (g, x, y)

def merge(a1, m1, a2, m2):
    """
    合并两个同余方程 x ≡ a1 (mod m1) 和 x ≡ a2 (mod m2)
    返回 (new_rem, new_mod) 如果成功，否则返回 None
    """
    g, x0, _ = exgcd(m1, m2)           # m1*x0 + m2*y0 = g
    diff = a2 - a1                     # 余数之差
    if diff % g != 0:                  # 无解条件
        return None

    mod = m2 // g                      # 模数约简后的范围
    # x0 乘以倍数得到 k 的一个特解，并取模
    k = (x0 * (diff // g)) % mod
    new_mod = m1 // g * m2             # 新模数是 lcm
    new_rem = (a1 + m1 * k) % new_mod  # 新余数
    return (new_rem, new_mod)

def solve_system(rem, mod):
    """求解同余方程组，返回 (最终余数, 最终模数) 或 None"""
    r, m = rem[0], mod[0]              # 从第一个方程开始
    for i in range(1, len(rem)):
        res = merge(r, m, rem[i], mod[i])
        if res is None:                # 无解则终止
            return None
        r, m = res                     # 更新合并结果
    return (r, m)

if __name__ == "__main__":
    # 物不知数
    rem = [2, 3, 2]
    mod = [3, 5, 7]
    res = solve_system(rem, mod)
    if res:
        r, m = res
        print(f"解为: x ≡ {r} (mod {m})")  # 23 mod 105
    else:
        print("无解")

    # 无解例子
    rem = [1, 2]
    mod = [2, 4]
    res = solve_system(rem, mod)
    if res:
        r, m = res
        print(f"解为: x ≡ {r} (mod {m})")
    else:
        print("无解")

    # 模数不互素但有解的例子
    rem = [2, 8]
    mod = [6, 10]
    res = solve_system(rem, mod)
    if res:
        r, m = res
        print(f"解为: x ≡ {r} (mod {m})")  # 8 mod 30
    else:
        print("无解")

4. 代码解释

exgcd 函数：扩展欧几里得算法的经典实现。它不仅能求最大公因数，还能找到一组整数解 $x, y$ 使得 $a \cdot x + b \cdot y = \gcd(a,b)$ 。在合并方程时，我们需要这个特解来求 $k$ 。
merge 函数：实现了两个方程的合并公式。
1. 先用 exgcd 求 $m_1$ 和 $m_2$ 的最大公因数 $d$ 。
2. 判断差值 $a_2 - a_1$ 能否被 $d$ 整除。不能则返回无解。
3. 计算模数约简后的范围 mod = m2 // d，并利用扩欧得到的 x0 计算 $k$ 的一个特解：k = (x0 * (diff/d)) % mod。
4. 新模数是最小公倍数 lcm(m1, m2) = m1/d * m2。
5. 新余数 = (a1 + m1 * k) % new_mod，并调整非负。
solve_system 函数：从第一个方程开始，依次与后续方程调用 merge 合并。如果某次合并失败，整个方程组无解。
注意：代码中使用了 long long（C++）或 Python 的大整数，避免乘法溢出。调整非负的操作保证了结果在 $[0, \text{new\_mod})$ 范围内。

5. 相关指引

中国剩余定理：当所有模数两两互素时，可以通过构造法直接得到解，无需逐次合并。它是本篇文章方法的特例，效率更高。
扩展欧几里得算法：求解形如 $a \cdot x + b \cdot y = \gcd(a,b)$ 的方程，是解决同余方程和合并方程组的核心工具。
模逆元：在解单个同余方程 $a \cdot x \equiv b \pmod{m}$ 时，如果 $a$ 与 $m$ 互素，可以求逆元直接得到 $x \equiv b \cdot a^{-1} \pmod{m}$ 。这在合并中也会用到。
最小公倍数 (LCM)：当模数不互素时，合并后的模数是 LCM，而不是乘积。理解 LCM 和 GCD 的关系有助于判断解的存在性。

解同余方程组就像解谜题，把多个条件一步步组合成一个条件。只要掌握了两两合并的技巧，无论多少个方程都能优雅地解决。在实际编程中，我们还需要注意数据类型范围，因为合并后的模数可能会变得很大（例如所有模数的乘积）。下一次你可以学习中国剩余定理，它提供了一种更高效的批量解法，但背后的思路是一样的。

例题精讲