一元线性同余方程
你有没有玩过这样的猜数游戏?心里想一个整数 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) 的解就可以通过如下步骤得到:
- 设 d=gcd(a,m)d = \gcd(a,m)d=gcd(a,m)。
- 如果 b % d≠0b \ % \ d \neq 0b % d=0,无解。
- 令 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。
- 用扩展欧几里得求 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′))。
- 特解 x=b′⋅x0 mod m′x = b' \cdot x_0 \bmod m'x=b′⋅x0modm′。
- 全部解为 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++ 代码
#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]
常见错误与调试小贴士
- 忘记检查无解条件 把 b%db % db%d 和 000 搞反了,或者漏掉了,导致程序在无解时仍输出错误结果。一定要先判断!
- x0 为负数时没处理 扩展欧几里得返回的 x0x0x0 可能是负数。不调整就直接参与后续计算,会得到负数解。代码中通过
(x0 % mod + mod) % mod(或x0 % mod)保证非负。 - 把原模数 mmm 和缩小后的模数 m′m'm′ 搞混 生成多个解时,步长是 m′=m/dm' = m/dm′=m/d,而不是 mmm。同时最终要对 mmm 取模,保证解在 0∼m−10 \sim m-10∼m−1 范围内。
- 认为解只有一个 当 d>1d>1d>1 时,方程有 ddd 个不同的解。比如 6x≡18(mod9)6x \equiv 18 \pmod{9}6x≡18(mod9) 的解是 0, 3, 6,而不是只有一个。
- 递归中的参数顺序写错 在 exgcd 中,递归调用是
exgcd(b, a % b, y, x),注意最后两个参数是交换的,回溯时用y -= a / b * x。如果顺序弄反,结果会乱。
完整示例:从手算到程序验证
我们手动解一下 6x≡18(mod9)6x \equiv 18 \pmod{9}6x≡18(mod9),然后用程序验证。
- gcd(6,9)=3\gcd(6,9)=3gcd(6,9)=3,181818 能被 333 整除,有解。
- 缩小:a′=2a'=2a′=2, m′=3m'=3m′=3, b′=6b'=6b′=6。
- 解 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。
- 特解 x=6×2 mod 3=12 mod 3=0x = 6 \times 2 \bmod 3 = 12 \bmod 3 = 0x=6×2mod3=12mod3=0。
- 全部解: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,求这个数。”这种问题正是多个一元线性同余方程联立的结果。学会了今天的单个方程,离破解这种“物不知数”的经典谜题只有一步之遥了!