一元线性同余方程组
同余方程组:把多个条件合并成一个
当你遇到一个数要同时满足好几个余数条件时,比如:一包糖果,3个3个地数剩2颗,5个5个地数剩3颗,7个7个地数剩2颗。你最少有多少颗糖果?这就是一个一元线性同余方程组问题。方程组由多个形如 x≡ai(modmi)x \equiv a_i \pmod{m_i}x≡ai(modmi) 的方程组成,目标是找到同时满足所有方程的数 xxx。这类问题在生活中很常见:分东西、排队编号、日历推算等等。解方程组就像解开连环锁,我们可以用两两合并法,一步步把所有条件压缩成一个。
1. 数学原理和公式推导
1.1 什么是同余方程组?
你已经知道单个同余方程是 a⋅x≡b(modm)a \cdot x \equiv b \pmod{m}a⋅x≡b(modm)。但实际中常遇到更复杂的情况:一个数要满足多个不同的余数条件。比如中国古代的“物不知数”问题:
有一堆物品,3个3个地数剩2个,5个5个地数剩3个,7个7个地数剩2个,问这堆物品有多少个?
这个问题的数学模型就是:
{x≡2(mod3)x≡3(mod5)x≡2(mod7)\begin{cases} x \equiv 2 \pmod{3} \ x \equiv 3 \pmod{5} \ x \equiv 2 \pmod{7} \end{cases}⎩⎨⎧x≡2(mod3)x≡3(mod5)x≡2(mod7)
这就是一个一元线性同余方程组。这里每个方程都是最简单的形式:未知数 xxx 直接模某个数等于一个常数,即 x≡ai(modmi)x \equiv a_i \pmod{m_i}x≡ai(modmi)。更一般地,方程也可以是 ai⋅x≡bi(modmi)a_i \cdot x \equiv b_i \pmod{m_i}ai⋅x≡bi(modmi),但我们先学这种最简单的标准形式。对于一般形式,可以先通过求解每个方程得到 x≡ri(modmi′)x \equiv r_i \pmod{m_i'}x≡ri(modmi′),再合并。
1.2 如何解两方程?
先看只有两个方程的情况:
{x≡a1(modm1)x≡a2(modm2)\begin{cases} x \equiv a_1 \pmod{m_1} \ x \equiv a_2 \pmod{m_2} \end{cases}{x≡a1(modm1)x≡a2(modm2)
我们想找到同时满足这两个条件的 xxx。如果 m1m_1m1 和 m2m_2m2 不互素,可能无解或有多个解。为了简单,我们先假设 m1m_1m1 和 m2m_2m2 互素(即最大公因数为1),这种情况一定有解。
思路:从第一个方程知道 x=a1+m1⋅kx = a_1 + m_1 \cdot kx=a1+m1⋅k(kkk 是某个整数),代入第二个方程:
a1+m1⋅k≡a2(modm2)a_1 + m_1 \cdot k \equiv a_2 \pmod{m_2}a1+m1⋅k≡a2(modm2)
整理得:
m1⋅k≡a2−a1(modm2)m_1 \cdot k \equiv a_2 - a_1 \pmod{m_2}m1⋅k≡a2−a1(modm2)
这就是一个关于 kkk 的一元线性同余方程!我们可以用之前学过的方法(扩展欧几里得)解出 kkk 模 m2m_2m2 的解。假设解为 k≡k0(modm2)k \equiv k_0 \pmod{m_2}k≡k0(modm2),那么:
x=a1+m1⋅(k0+t⋅m2)=(a1+m1⋅k0)+(m1⋅m2)⋅tx = a_1 + m_1 \cdot (k_0 + t \cdot m_2) = (a_1 + m_1 \cdot k_0) + (m_1 \cdot m_2) \cdot tx=a1+m1⋅(k0+t⋅m2)=(a1+m1⋅k0)+(m1⋅m2)⋅t
即:
x≡a1+m1⋅k0(modm1⋅m2)x \equiv a_1 + m_1 \cdot k_0 \pmod{m_1 \cdot m_2}x≡a1+m1⋅k0(modm1⋅m2)
这样我们就把两个方程合并成了一个方程:x≡new_a(modnew_m)x \equiv \text{new_a} \pmod{\text{new_m}}x≡new_a(modnew_m),其中 new_m=m1⋅m2\text{new_m} = m_1 \cdot m_2new_m=m1⋅m2,new_a=a1+m1⋅k0\text{new_a} = a_1 + m_1 \cdot k_0new_a=a1+m1⋅k0(需要模到 [0,new_m)[0, \text{new_m})[0,new_m) 内)。
生活例子:假设你有一些零花钱,每次数5元还剩2元,每次数8元还剩3元。即:
x≡2(mod5),x≡3(mod8)x \equiv 2 \pmod{5}, \quad x \equiv 3 \pmod{8}x≡2(mod5),x≡3(mod8)
设 x=2+5kx = 2 + 5kx=2+5k,代入第二个:2+5k≡3(mod8)⇒5k≡1(mod8)2 + 5k \equiv 3 \pmod{8} \Rightarrow 5k \equiv 1 \pmod{8}2+5k≡3(mod8)⇒5k≡1(mod8)。5模8的逆元是5(因为 5×5=25≡1(mod8)5 \times 5 = 25 \equiv 1 \pmod{8}5×5=25≡1(mod8)),所以 k≡5×1=5(mod8)k \equiv 5 \times 1 = 5 \pmod{8}k≡5×1=5(mod8)。取 k0=5k_0 = 5k0=5,则 x=2+5×5=27x = 2 + 5 \times 5 = 27x=2+5×5=27。合并后 x≡27(mod40)x \equiv 27 \pmod{40}x≡27(mod40)。最小的正整数解是27元。
如果 m1m_1m1 和 m2m_2m2 不互素,例如 m1=4,m2=6m_1 = 4, m_2 = 6m1=4,m2=6,我们需要先判断解是否存在,并且合并后的模数变成它们的最小公倍数(LCM)。后面在扩展中国剩余定理中会详细讲。
1.3 多个方程的合并
我们可以重复使用上述方法:先合并前两个方程得到一个方程,然后再和第三个方程合并,以此类推,直到所有方程合并成一个。如果中间某一对无解,整个方程组就无解。
常见错误:有些新手以为可以直接把每个方程的模数相乘作为新模数,但只适用于模数两两互素的情况。如果模数不互素,直接用乘积会导致错误结果(可能多出不存在的解或漏掉真正的解)。正确的做法是每次合并后模数变成当前两模数的最小公倍数。
1.4 回到“物不知数”例子
用两两合并法解:
- 先合并前两个(模3和模5): x≡2(mod3),x≡3(mod5)x \equiv 2 \pmod{3}, \quad x \equiv 3 \pmod{5}x≡2(mod3),x≡3(mod5) 设 x=2+3kx = 2 + 3kx=2+3k,代入第二个:2+3k≡3(mod5)⇒3k≡1(mod5)2 + 3k \equiv 3 \pmod{5} \Rightarrow 3k \equiv 1 \pmod{5}2+3k≡3(mod5)⇒3k≡1(mod5)。3的逆元模5是2(因为 3×2=6≡13 \times 2 = 6 \equiv 13×2=6≡1),所以 k≡2(mod5)k \equiv 2 \pmod{5}k≡2(mod5)。取 k0=2k_0 = 2k0=2,则 x=2+3×2=8x = 2 + 3 \times 2 = 8x=2+3×2=8,合并后 x≡8(mod15)x \equiv 8 \pmod{15}x≡8(mod15)。
- 再和第三个方程 x≡2(mod7)x \equiv 2 \pmod{7}x≡2(mod7) 合并: x≡8(mod15),x≡2(mod7)x \equiv 8 \pmod{15}, \quad x \equiv 2 \pmod{7}x≡8(mod15),x≡2(mod7) 设 x=8+15kx = 8 + 15kx=8+15k,代入:8+15k≡2(mod7)⇒15k≡−6≡1(mod7)8 + 15k \equiv 2 \pmod{7} \Rightarrow 15k \equiv -6 \equiv 1 \pmod{7}8+15k≡2(mod7)⇒15k≡−6≡1(mod7)(因为 −6mod 7=1-6 \mod 7 = 1−6mod7=1)。15mod 7=115 \mod 7 = 115mod7=1,所以 1⋅k≡1(mod7)⇒k≡1(mod7)1 \cdot k \equiv 1 \pmod{7} \Rightarrow k \equiv 1 \pmod{7}1⋅k≡1(mod7)⇒k≡1(mod7)。取 k0=1k_0 = 1k0=1,则 x=8+15×1=23x = 8 + 15 \times 1 = 23x=8+15×1=23,合并后 x≡23(mod105)x \equiv 23 \pmod{105}x≡23(mod105)。所以最小的正整数解是23。
2. 新手容易犯的错误
- 忘记检查无解条件:在合并两个方程时,如果 a2−a1a_2 - a_1a2−a1 不能被 m1,m2m_1, m_2m1,m2 的最大公因数整除,则该方程无解。必须检查并返回无解,否则会算出错误答案。
- 模数溢出:当模数较大时,乘积 m1×m2m_1 \times m_2m1×m2 可能超过 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,yx, yx,y 使得 a⋅x+b⋅y=gcd(a,b)a \cdot x + b \cdot y = \gcd(a,b)a⋅x+b⋅y=gcd(a,b)。在合并方程时,我们需要这个特解来求 kkk。merge函数:实现了两个方程的合并公式。- 先用
exgcd求 m1m_1m1 和 m2m_2m2 的最大公因数 ddd。 - 判断差值 a2−a1a_2 - a_1a2−a1 能否被 ddd 整除。不能则返回无解。
- 计算模数约简后的范围
mod = m2 // d,并利用扩欧得到的x0计算 kkk 的一个特解:k = (x0 * (diff/d)) % mod。 - 新模数是最小公倍数
lcm(m1, m2) = m1/d * m2。 - 新余数 =
(a1 + m1 * k) % new_mod,并调整非负。
- 先用
solve_system函数:从第一个方程开始,依次与后续方程调用merge合并。如果某次合并失败,整个方程组无解。- 注意:代码中使用了
long long(C++)或 Python 的大整数,避免乘法溢出。调整非负的操作保证了结果在 [0,new_mod)[0, \text{new_mod})[0,new_mod) 范围内。
5. 相关指引
- 中国剩余定理:当所有模数两两互素时,可以通过构造法直接得到解,无需逐次合并。它是本篇文章方法的特例,效率更高。
- 扩展欧几里得算法:求解形如 a⋅x+b⋅y=gcd(a,b)a \cdot x + b \cdot y = \gcd(a,b)a⋅x+b⋅y=gcd(a,b) 的方程,是解决同余方程和合并方程组的核心工具。
- 模逆元:在解单个同余方程 a⋅x≡b(modm)a \cdot x \equiv b \pmod{m}a⋅x≡b(modm) 时,如果 aaa 与 mmm 互素,可以求逆元直接得到 x≡b⋅a−1(modm)x \equiv b \cdot a^{-1} \pmod{m}x≡b⋅a−1(modm)。这在合并中也会用到。
- 最小公倍数 (LCM):当模数不互素时,合并后的模数是 LCM,而不是乘积。理解 LCM 和 GCD 的关系有助于判断解的存在性。
解同余方程组就像解谜题,把多个条件一步步组合成一个条件。只要掌握了两两合并的技巧,无论多少个方程都能优雅地解决。在实际编程中,我们还需要注意数据类型范围,因为合并后的模数可能会变得很大(例如所有模数的乘积)。下一次你可以学习中国剩余定理,它提供了一种更高效的批量解法,但背后的思路是一样的。