从猜数字到解方程：一元线性同余方程

你有没有玩过这样的猜数游戏？心里想一个整数 $x$，然后告诉你“$3$ 乘以你的数，除以 $7$ 的余数等于 $1$”，你能猜出 $x$ 是多少吗？这其实就是一元线性同余方程要解决的问题。它像一把钥匙，帮我们从余数的信息里还原出隐藏的数字。而且在密码学、日程安排、排队问题里，它都大有用处。

什么是同余？——时钟和周期的故事

我们先拆解“同余”这个词。想象一下钟表盘：只有 12 个小时，所以 13 点其实和下午 1 点 在同一位置（因为 $13 \div 12 = 1$ 余 $1$）。我们说 13 和 1 关于模 12 同余，记作

中文读作“13 同余于 1 模 12”。这里的“模”就是钟表盘上的最大数字 12。

更多的日常例子：

• 一周有 7 天，今天是星期一，那 8 天后也是星期一（因为 $8 \equiv 1 \pmod{7}$）。
• 电影院的座位每排有 10 个，第 23 号座位和第三排第 3 号座位同一个位置（$23 \equiv 3 \pmod{10}$）。

数学定义：如果两个整数 $A$ 和 $B$ 除以同一个正整数 $m$ 得到相同的余数，就称 $A$ 和 $B$ 关于模 $m$ 同余，记作

例如 $17 \equiv 5 \pmod{12}$，因为 $17 \div 12$ 余 $5$，而 $5 \div 12$ 余 $5$，余数相同。

一元线性同余方程：猜数游戏升级版

现在我们把猜数游戏写成数学形式：

其中 $a$、$b$、$m$ 是已知整数（$m > 0$），$x$ 是我们要求解的整数。方程的意思是：找到一个整数 $x$，使得 $a$ 乘以 $x$ 之后，除以 $m$ 的余数恰好等于 $b$。

生活例子：
小华有 3 盒铅笔，每盒有 相同数量 的铅笔（设为 $x$ 支）。他把所有铅笔分给 7 个朋友，每人得到同样多的铅笔后，还剩 1 支。那么铅笔总数 $3x$ 除以 7 的余数应该是 1。也就是解方程

试试看：

• $x=1$：$3\times1=3$，$3 \div 7$ 余 $3$，不是 $1$。
• $x=2$：$3\times2=6$，余 $6$。
• $x=3$：$9$ 余 $2$。
• $x=4$：$12$ 余 $5$。
• $x=5$：$15$ 余 $1$，找到了！

所以 $x=5$ 是一个解。其实还有其它解吗？因为模 $7$，每隔 $7$ 个单位就会重复余数，所以 $5+7=12$ 也是解（$3\times12=36$，$36 \div 7$ 余 $1$）。但通常我们只取 $0$ 到 $6$ 之间的最小非负解，即 $5$。

什么时候有解？——试试 $2x \equiv 1 \pmod{4}$

并不是每个同余方程都有解。例如：

因为 $2x$ 一定是偶数，偶数除以 $4$ 的余数只能是 $0$ 或 $2$，永远得不到 $1$，所以无解。

判断条件：方程有解当且仅当 $b$ 能被 $a$ 和 $m$ 的最大公约数整除，即 $\gcd(a,m) \mid b$。

• 对于 $2x \equiv 1 \bmod 4$：$\gcd(2,4)=2$，$1$ 不能被 $2$ 整除 → 无解。
• 对于 $3x \equiv 1 \bmod 7$：$\gcd(3,7)=1$，$1$ 能被 $1$ 整除 → 有解（且只有 1 个解在模 7 下）。
• 对于 $6x \equiv 18 \bmod 9$：$\gcd(6,9)=3$，$18$ 能被 $3$ 整除 → 有解，而且解的数量等于最大公约数 $3$（在模 9 范围内有 3 个解）。

扩展欧几里得算法：求解的万能钥匙

当方程有解时，怎么找到那个 $x$ 呢？最经典的方法是 扩展欧几里得算法。这个算法不仅能求出两个数的最大公约数，还能找到整数 $x'$ 和 $y'$ 使得

比如 $a=3, m=7$，我们希望 $3x' + 7y' = 1$。可以手算：

• 用欧几里得算法：$7 = 3\times2 + 1$，$3 = 1\times3 + 0$，所以 $\gcd=1$。
• 回代：$1 = 7 - 3\times2$，整理成 $3\times(-2) + 7\times1 = 1$，所以 $x'=-2$，$y'=1$。

得到 $x'$ 后，原方程 $a x \equiv b \pmod{m}$ 的解就可以通过如下步骤得到：

1. 设 $d = \gcd(a,m)$。
2. 如果 $b \ \% \ d \neq 0$，无解。
3. 令 $a' = a/d$，$m' = m/d$，$b' = b/d$。现在方程变为 $a' x \equiv b' \pmod{m'}$，且 $\gcd(a',m')=1$。
4. 用扩展欧几里得求 $a'$ 模 $m'$ 的逆元 $x_0$，即 $a' x_0 \equiv 1 \pmod{m'}$。其实上一步的 $x'$ 就是 $x_0$（因为我们有 $a x' + m y' = d$，两边除以 $d$ 得 $a' x' + m' y' = 1$，所以 $a' x' \equiv 1 \pmod{m'}$）。
5. 特解 $x = b' \cdot x_0 \bmod m'$。
6. 全部解为 $x, x+m', x+2m', \dots, x+(d-1)m'$（模 $m$ 下）。

编程实现：用代码自动解方程

下面我们用 C++ 和 Python 实现一个函数，输入 $a, b, m$，输出所有模 $m$ 意义下的解（最小非负形式），或报告无解。

C++ 代码

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

// 扩展欧几里得算法，返回 gcd(a,b)，并设置 x, y 满足 a*x + b*y = gcd
// 参数：a, b        // 输入整数
//       &x, &y      // 引用，用于返回满足方程的系数
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1; y = 0;   // 当 b=0 时，gcd=a，且 a*1 + 0*0 = a
        return a;
    }
    int d = exgcd(b, a % b, y, x);  // 递归时交换 x 和 y 的位置
    y -= a / b * x;                 // 回溯更新 y
    return d;
}

// 求解一元线性同余方程 a*x ≡ b (mod m)
// 返回所有模 m 意义下的解（0 <= sol < m），若无解则返回空 vector
vector<int> solve_linear_congruence(int a, int b, int m) {
    int x0 = 0, y0 = 0;               // 用于接收 exgcd 的系数
    int d = exgcd(a, m, x0, y0);      // 得到 a*x0 + m*y0 = d
    vector<int> solutions;            // 存放结果的数组

    if (b % d != 0) {                 // 条件不满足，无解
        return solutions;             // 返回空数组
    }

    int mod = m / d;                  // 缩小后的模数 m'
    x0 = (x0 % mod + mod) % mod;      // 将 x0 调整为 [0, mod-1] 的非负数
    int x = (b / d) * x0 % mod;       // 特解（模 mod 下）

    for (int i = 0; i < d; ++i) {     // 共有 d 个解
        int sol = (x + i * mod) % m;  // 加上 i 倍的模差，再对原模数取模
        solutions.push_back(sol);
    }
    return solutions;
}

int main() {
    // 例1：3x ≡ 1 (mod 7)
    int a = 3, b = 1, m = 7;
    vector<int> ans = solve_linear_congruence(a, b, m);
    cout << "方程 " << a << "x ≡ " << b << " (mod " << m << ") 的解：";
    for (int sol : ans) cout << sol << " ";
    cout << endl;   // 预期输出: 5

    // 例2：2x ≡ 1 (mod 4) 无解
    a = 2; b = 1; m = 4;
    ans = solve_linear_congruence(a, b, m);
    if (ans.empty()) {
        cout << "方程 " << a << "x ≡ " << b << " (mod " << m << ") 无解" << endl;
    } else {
        cout << "解：";
        for (int sol : ans) cout << sol << " ";
        cout << endl;
    }

    // 例3：6x ≡ 18 (mod 9) 有多个解
    a = 6; b = 18; m = 9;
    ans = solve_linear_congruence(a, b, m);
    cout << "方程 " << a << "x ≡ " << b << " (mod " << m << ") 的解：";
    for (int sol : ans) cout << sol << " ";
    cout << endl;   // 预期输出: 0 3 6

    return 0;
}

Python 代码

def exgcd(a, b):
    """
    扩展欧几里得算法
    返回 (g, x, y) 使得 a*x + b*y = g
    参数：a, b      // 输入整数
    """
    if b == 0:
        return (a, 1, 0)   # 基本情况：a*1 + 0*0 = a
    else:
        g, x1, y1 = exgcd(b, a % b)   # 递归调用
        # 回溯得到新的 x, y
        x = y1
        y = x1 - (a // b) * y1
        return (g, x, y)

def solve_linear_congruence(a, b, m):
    """
    求解一元线性同余方程 a*x ≡ b (mod m)
    返回所有模 m 意义下的解（列表），无解返回空列表
    """
    g, x0, _ = exgcd(a, m)     # 得到 gcd 和一组特解，y0 不需要
    if b % g != 0:
        return []              # 无解

    mod = m // g               # 缩小后的模数 m'
    x0 = x0 % mod              # 调整到非负
    x = (b // g) * x0 % mod    # 特解

    # 生成所有 d 个解：x, x+mod, x+2*mod, ... 并模 m 确保范围
    solutions = [(x + i * mod) % m for i in range(g)]
    return solutions

if __name__ == "__main__":
    # 例1
    a, b, m = 3, 1, 7
    sols = solve_linear_congruence(a, b, m)
    print(f"方程 {a}x ≡ {b} (mod {m}) 的解：{sols}")   # 预期 [5]

    # 例2：无解
    a, b, m = 2, 1, 4
    sols = solve_linear_congruence(a, b, m)
    print(f"方程 {a}x ≡ {b} (mod {m}) 的解：{sols}")   # 预期 []

    # 例3：多个解
    a, b, m = 6, 18, 9
    sols = solve_linear_congruence(a, b, m)
    print(f"方程 {a}x ≡ {b} (mod {m}) 的解：{sols}")   # 预期 [0, 3, 6]

常见错误与调试小贴士

1. 忘记检查无解条件
   把 $b \% d$ 和 $0$ 搞反了，或者漏掉了，导致程序在无解时仍输出错误结果。一定要先判断！

2. x0 为负数时没处理
   扩展欧几里得返回的 $x0$ 可能是负数。不调整就直接参与后续计算，会得到负数解。代码中通过 (x0 % mod + mod) % mod（或 x0 % mod）保证非负。

3. 把原模数 $m$ 和缩小后的模数 $m'$ 搞混
   生成多个解时，步长是 $m' = m/d$，而不是 $m$。同时最终要对 $m$ 取模，保证解在 $0 \sim m-1$ 范围内。

4. 认为解只有一个
   当 $d>1$ 时，方程有 $d$ 个不同的解。比如 $6x \equiv 18 \pmod{9}$ 的解是 0, 3, 6，而不是只有一个。

5. 递归中的参数顺序写错
   在 exgcd 中，递归调用是 exgcd(b, a % b, y, x)，注意最后两个参数是交换的，回溯时用 y -= a / b * x。如果顺序弄反，结果会乱。

完整示例：从手算到程序验证

我们手动解一下 $6x \equiv 18 \pmod{9}$，然后用程序验证。

1. $\gcd(6,9)=3$，$18$ 能被 $3$ 整除，有解。
2. 缩小：$a'=2$, $m'=3$, $b'=6$。
3. 解 $2x' \equiv 1 \pmod{3}$：因为 $2 \times 2 = 4 \equiv 1 \pmod{3}$，所以逆元 $x_0=2$。
4. 特解 $x = 6 \times 2 \bmod 3 = 12 \bmod 3 = 0$。
5. 全部解：$0, 0+3=3, 0+6=6$（模 9 下）。验证：$6\times0=0 \equiv 0$? 不对，我们需要余数是 18 mod 9 = 0，所以 0 是对的。$6\times3=18 \equiv 0$，$6\times6=36 \equiv 0$，都满足。

运行上面的 C++ 或 Python 程序，输出正是 0 3 6。

总结与下一步

一元线性同余方程就像一场“已知余数，反推乘数”的数学游戏。要点有三：

• 方程结构：$a x \equiv b \pmod{m}$
• 有解条件：$\gcd(a,m) \mid b$
• 求解工具：扩展欧几里得算法，找到特解后加上 $m/\gcd(a,m)$ 的整数倍得到全部解。

掌握了这个基础，我们就可以挑战更复杂的问题——比如中国剩余定理，它专门解决由多个同余方程组成的方程组。例如：“一个数除以 3 余 2，除以 5 余 3，除以 7 余 2，求这个数。”这种问题正是多个一元线性同余方程联立的结果。学会了今天的单个方程，离破解这种“物不知数”的经典谜题只有一步之遥了！