困难通用14 分钟4,844 字

一元线性同余方程

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

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

我们先拆解“同余”这个词。想象一下钟表盘:只有 12 个小时,所以 13 点其实和下午 1 点 在同一位置​​(因为 13÷12=113 \div 12 = 113÷12=1 余 111)。我们说 13 和 1 关于模 12 同余​​,记作

13≡1(mod12)13 \equiv 1 \pmod{12}13≡1(mod12)

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

更多的日常例子:

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

数学定义​​:如果两个整数 AAA 和 BBB 除以同一个正整数 mmm 得到相同的余数,就称 AAA 和 BBB 关于模 mmm 同余,记作

A≡B(modm)A \equiv B \pmod{m}A≡B(modm)

例如 17≡5(mod12)17 \equiv 5 \pmod{12}17≡5(mod12),因为 17÷1217 \div 1217÷12 余 555,而 5÷125 \div 125÷12 余 555,余数相同。

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

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

a⋅x≡b(modm)a \cdot x \equiv b \pmod{m}a⋅x≡b(modm)

其中 aaa、bbb、mmm 是已知整数(m>0m > 0m>0),xxx 是我们要求解的整数。方程的意思是:找到一个整数 xxx,使得 aaa 乘以 xxx 之后,除以 mmm 的余数恰好等于 bbb。

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

3x≡1(mod7)3x \equiv 1 \pmod{7}3x≡1(mod7)

试试看:

  • x=1x=1x=1:3×1=33\times1=33×1=3,3÷73 \div 73÷7 余 333,不是 111。
  • x=2x=2x=2:3×2=63\times2=63×2=6,余 666。
  • x=3x=3x=3:999 余 222。
  • x=4x=4x=4:121212 余 555。
  • x=5x=5x=5:151515 余 111,找到了!

所以 x=5x=5x=5 是一个解。其实还有其它解吗?因为模 777,每隔 777 个单位就会重复余数,所以 5+7=125+7=125+7=12 也是解(3×12=363\times12=363×12=36,36÷736 \div 736÷7 余 111)。但通常我们只取 000 到 666 之间的最小非负解,即 555。

什么时候有解?——试试 2x≡1(mod4)2x \equiv 1 \pmod{4}2x≡1(mod4)

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

2x≡1(mod4)2x \equiv 1 \pmod{4}2x≡1(mod4)

因为 2x2x2x 一定是偶数,偶数除以 444 的余数只能是 000 或 222,永远得不到 111,所以无解。

判断条件​​:方程有解当且仅当 bbb 能被 aaa 和 mmm 的最大公约数整除​​,即 gcd⁡(a,m)∣b\gcd(a,m) \mid bgcd(a,m)∣b。

  • 对于 2x≡1 mod 42x \equiv 1 \bmod 42x≡1mod4:gcd⁡(2,4)=2\gcd(2,4)=2gcd(2,4)=2,111 不能被 222 整除 → 无解。
  • 对于 3x≡1 mod 73x \equiv 1 \bmod 73x≡1mod7:gcd⁡(3,7)=1\gcd(3,7)=1gcd(3,7)=1,111 能被 111 整除 → 有解(且只有 1 个解在模 7 下)。
  • 对于 6x≡18 mod 96x \equiv 18 \bmod 96x≡18mod9:gcd⁡(6,9)=3\gcd(6,9)=3gcd(6,9)=3,181818 能被 333 整除 → 有解,而且解的数量等于最大公约数 333(在模 9 范围内有 3 个解)。

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

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

a⋅x′+m⋅y′=gcd⁡(a,m)a \cdot x' + m \cdot y' = \gcd(a,m)a⋅x′+m⋅y′=gcd(a,m)

比如 a=3,m=7a=3, m=7a=3,m=7,我们希望 3x′+7y′=13x' + 7y' = 13x′+7y′=1。可以手算:

  • 用欧几里得算法:7=3×2+17 = 3\times2 + 17=3×2+1,3=1×3+03 = 1\times3 + 03=1×3+0,所以 gcd⁡=1\gcd=1gcd=1。
  • 回代:1=7−3×21 = 7 - 3\times21=7−3×2,整理成 3×(−2)+7×1=13\times(-2) + 7\times1 = 13×(−2)+7×1=1,所以 x′=−2x'=-2x′=−2,y′=1y'=1y′=1。

得到 x′x'x′ 后,原方程 ax≡b(modm)a x \equiv b \pmod{m}ax≡b(modm) 的解就可以通过如下步骤得到:

  1. 设 d=gcd⁡(a,m)d = \gcd(a,m)d=gcd(a,m)。
  2. 如果 b % d≠0b \ % \ d \neq 0b % d=0,无解。
  3. 令 a′=a/da' = a/da′=a/d,m′=m/dm' = m/dm′=m/d,b′=b/db' = b/db′=b/d。现在方程变为 a′x≡b′(modm′)a' x \equiv b' \pmod{m'}a′x≡b′(modm′),且 gcd⁡(a′,m′)=1\gcd(a',m')=1gcd(a′,m′)=1。
  4. 用扩展欧几里得求 a′a'a′ 模 m′m'm′ 的逆元 x0x_0x0​,即 a′x0≡1(modm′)a' x_0 \equiv 1 \pmod{m'}a′x0​≡1(modm′)。其实上一步的 x′x'x′ 就是 x0x_0x0​(因为我们有 ax′+my′=da x' + m y' = dax′+my′=d,两边除以 ddd 得 a′x′+m′y′=1a' x' + m' y' = 1a′x′+m′y′=1,所以 a′x′≡1(modm′)a' x' \equiv 1 \pmod{m'}a′x′≡1(modm′))。
  5. 特解 x=b′⋅x0 mod m′x = b' \cdot x_0 \bmod m'x=b′⋅x0​modm′。
  6. 全部解为 x,x+m′,x+2m′,…,x+(d−1)m′x, x+m', x+2m', \dots, x+(d-1)m'x,x+m′,x+2m′,…,x+(d−1)m′(模 mmm 下)。

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

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

C++ 代码

cpp
#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 代码

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%db % db%d 和 000 搞反了,或者漏掉了,导致程序在无解时仍输出错误结果。一定要先判断!
  2. x0 为负数时没处理 扩展欧几里得返回的 x0x0x0 可能是负数。不调整就直接参与后续计算,会得到负数解。代码中通过 (x0 % mod + mod) % mod(或 x0 % mod)保证非负。
  3. 把原模数 mmm 和缩小后的模数 m′m'm′ 搞混 生成多个解时,步长是 m′=m/dm' = m/dm′=m/d,而不是 mmm。同时最终要对 mmm 取模,保证解在 0∼m−10 \sim m-10∼m−1 范围内。
  4. 认为解只有一个 当 d>1d>1d>1 时,方程有 ddd 个不同的解。比如 6x≡18(mod9)6x \equiv 18 \pmod{9}6x≡18(mod9) 的解是 0, 3, 6,而不是只有一个。
  5. 递归中的参数顺序写错 在 exgcd 中,递归调用是 exgcd(b, a % b, y, x),注意最后两个参数是交换的,回溯时用 y -= a / b * x。如果顺序弄反,结果会乱。

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

我们手动解一下 6x≡18(mod9)6x \equiv 18 \pmod{9}6x≡18(mod9),然后用程序验证。

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

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

总结与下一步

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

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

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

同类知识点