Let \(m_1, m_2, \dots, m_k\) be k pairwise coprime positive integers. Define \(m = m_1 m_2 \cdots m_k\), and \(M_i = \frac{m}{m_i}\) for \(1 \leq i \leq k\). Then the system of congruences:

Then the system of congruences:\(\begin{cases} x \equiv b_1 \pmod{m_1} \\ x \equiv b_2 \pmod{m_2} \\ \quad \vdots \\ x \equiv b_k \pmod{m_k} \end{cases}\)has a unique solution modulo m, given by:

x≡∑i=1k​bi​Mi​Mi′​(modm)

where Mi′​ is an integer satisfying Mi​Mi′​≡1(modmi​) (i.e., the modular inverse of Mi​ modulo mi​).

---

Proof

1. Existence of the Solution

Since m1​,m2​,…,mk​ are pairwise coprime, gcd(mi​,mj​)=1 for all i=j. Thus, gcd(Mi​,mi​)=1 (because Mi​=mi​m​ contains no prime factors of mi​).

By Bézout’s Identity (the linear combination representation of the greatest common divisor), since gcd(Mi​,mi​)=1, there exist integers s,t such that sMi​+tmi​=1. Rearranging gives sMi​≡1(modmi​), so we define Mi′​=s, which satisfies Mi​Mi′​≡1(modmi​).

Now verify x=∑i=1k​bi​Mi​Mi′​ is a solution:

For any fixed j∈{1,2,…,k}:

• If i=j, mj​∣Mi​ (since Mi​=mi​m​ includes mj​ as a factor), so bi​Mi​Mi′​≡0(modmj​).
• If i=j, Mj​Mj′​≡1(modmj​), so bj​Mj​Mj′​≡bj​⋅1=bj​(modmj​).

Thus:

x=∑i=1k​bi​Mi​Mi′​≡bj​(modmj​)

This holds for all j, so x satisfies every congruence in the system.

2. Uniqueness of the Solution

Let x1​,x2​ be two solutions to the system. Then for each j, x1​≡bj​(modmj​) and x2​≡bj​(modmj​), so:

x1​≡x2​(modmj​)∀1≤j≤k

Since m1​,m2​,…,mk​ are pairwise coprime, the least common multiple lcm(m1​,m2​,…,mk​)=m1​m2​⋯mk​=m. By the property of congruences, if x1​≡x2​(modmj​) for all j, then x1​≡x2​(modlcm(m1​,…,mk​)). Thus:

x1​≡x2​(modm)

The solution is therefore unique modulo m.

---

二、中文讲义整理（中国剩余定理）

中国剩余定理

定理 2.5.1（中国剩余定理）

设 m1​,m2​,…,mk​ 是 k 个两两互素的正整数，记 m=m1​m2​⋯mk​，且 Mi​=mi​m​ (1≤i≤k)，

则同余方程组：\(\begin{cases} x \equiv b_1 \pmod{m_1} \\ x \equiv b_2 \pmod{m_2} \\ \quad \vdots \\ x \equiv b_k \pmod{m_k} \end{cases}\)

在模 m 下存在唯一解，解为：

x≡∑i=1k​bi​Mi​Mi′​(modm)

其中 Mi′​ 是满足 Mi​Mi′​≡1(modmi​) 的整数（即 Mi​ 在模 mi​ 下的乘法逆元）。

---

证明

1. 解的存在性证明

因为 m1​,m2​,…,mk​ 两两互素，故对任意 i=j，gcd(mi​,mj​)=1。

由 Mi​=mi​m​=m1​m2​⋯mi−1​mi+1​⋯mk​，可知 Mi​ 与 mi​ 互素（Mi​ 不含 mi​ 的素因子），即 gcd(Mi​,mi​)=1。

根据贝祖定理（最大公因数的线性组合表示）：若 gcd(a,b)=1，则存在整数 s,t 使得 sa+tb=1。因此存在整数 Mi′​ 满足：

Mi​Mi′​≡1(modmi​)

接下来验证 x=∑i=1k​bi​Mi​Mi′​ 是方程组的解：

对任意固定的 j (1≤j≤k)，考虑 xmodmj​：

• 当 i=j 时，mj​∣Mi​（Mi​ 包含 mj​ 作为因子），故 bi​Mi​Mi′​≡0(modmj​)；
• 当 i=j 时，Mj​Mj′​≡1(modmj​)，故 bj​Mj​Mj′​≡bj​⋅1=bj​(modmj​)。

因此：

x=∑i=1k​bi​Mi​Mi′​≡bj​(modmj​)

由 j 的任意性，x 满足方程组的所有同余式，故解存在。

2. 解的唯一性证明

设 x1​,x2​ 是方程组的两个解，则对每个 j，有 x1​≡bj​(modmj​) 且 x2​≡bj​(modmj​)，因此：

x1​≡x2​(modmj​)(∀1≤j≤k)

根据同余的推广性质：若 x≡y(moda) 且 x≡y(modb)，且 gcd(a,b)=1，则 x≡y(modab)。由于 m1​,m2​,…,mk​ 两两互素，其最小公倍数 lcm(m1​,m2​,…,mk​)=m1​m2​⋯mk​=m，因此：

x1​≡x2​(modm)

即方程组的解在模 m 下是唯一的。

---

我们来系统讲解模不互素的同余方程组的解法，核心思路是：转化为可使用中国剩余定理（CRT）的形式，主要有两种通用方法，我会结合你给的例子一步步拆解。

---

一、核心前提：为什么不能直接用 CRT？

中国剩余定理（CRT）的适用条件是模两两互素，而你例子中的模 \(10,12,15\) 并不两两互素（如 \(\gcd(10,12)=2\)，\(\gcd(12,15)=3\)），因此必须先处理这些 “不互素” 的部分，消除矛盾或转化为互素的形式。

---

二、方法 1：分解为素数幂（推荐，最通用）

步骤 1：将每个同余式分解为素数幂形式

对每个模 \(m_i\) 做素因数分解：\(m_i = p_1^{k_1} \times p_2^{k_2} \times \dots \times p_n^{k_n}\)，则同余式 \(x \equiv b_i \pmod{m_i}\) 等价于一组同余式：

\(x \equiv b_i \pmod{p_1^{k_1}}, \quad x \equiv b_i \pmod{p_2^{k_2}}, \quad \dots, \quad x \equiv b_i \pmod{p_n^{k_n}}\)

以你的例子为例：\(\begin{cases} x \equiv 6 \pmod{10} \\ x \equiv 10 \pmod{12} \\ x \equiv 1 \pmod{15} \end{cases}\)

• \(10 = 2^1 \times 5^1\)，故 \(x \equiv 6 \pmod{10}\) 等价于：\(x \equiv 6 \equiv 0 \pmod{2}\)，\(x \equiv 6 \equiv 1 \pmod{5}\)
• \(12 = 2^2 \times 3^1\)，故 \(x \equiv 10 \pmod{12}\) 等价于：\(x \equiv 10 \equiv 1 \pmod{3}\)，\(x \equiv 10 \equiv 2 \pmod{4}\)
• \(15 = 3^1 \times 5^1\)，故 \(x \equiv 1 \pmod{15}\) 等价于：\(x \equiv 1 \pmod{3}\)，\(x \equiv 1 \pmod{5}\)

步骤 2：合并同一素数幂的同余式，检查相容性

对每个素数幂 \(p^k\)，收集所有关于它的同余式，判断是否矛盾：

• 若同一素数幂的同余式余数不一致，则方程组无解；
• 若余数一致，或高次幂蕴含低次幂（如 \(x \equiv 2 \pmod{4}\) 自动满足 \(x \equiv 0 \pmod{2}\)），则合并为一个同余式。

对例子中的同余式整理：

素数幂	收集到的同余式	相容性判断与合并
21=2	x≡0(mod2)（来自 10）	被 x≡2(mod4) 蕴含，可删除
22=4	x≡2(mod4)（来自 12）	保留，更严格
31=3	x≡1(mod3)（来自 12）、x≡1(mod3)（来自 15）	一致，合并为 x≡1(mod3)
51=5	x≡1(mod5)（来自 10）、x≡1(mod5)（来自 15）	一致，合并为 x≡1(mod5)

最终得到两两互素的模的方程组：\(\begin{cases} x \equiv 1 \pmod{3} \\ x \equiv 2 \pmod{4} \\ x \equiv 1 \pmod{5} \end{cases}\)

步骤 3：对素数幂方程组应用 CRT

此时模 \(3,4,5\) 两两互素，直接用 CRT 公式：

设 \(m = 3 \times 4 \times 5 = 60\)，定义 \(M_i = \frac{m}{m_i}\)，\(M_i’\) 为 \(M_i\) 在模 \(m_i\) 下的逆元：

• 对 \(m_1=3\)：\(M_1 = 60/3=20\)，求 \(20 \times M_1′ \equiv 1 \pmod{3}\)\(20 \equiv 2 \pmod{3}\)，故 \(2 \times M_1′ \equiv 1 \pmod{3}\)，得 \(M_1’=2\)（因 \(2 \times 2=4 \equiv 1 \pmod{3}\)）
• 对 \(m_2=4\)：\(M_2 = 60/4=15\)，求 \(15 \times M_2′ \equiv 1 \pmod{4}\)\(15 \equiv 3 \pmod{4}\)，故 \(3 \times M_2′ \equiv 1 \pmod{4}\)，得 \(M_2’=3\)（因 \(3 \times 3=9 \equiv 1 \pmod{4}\)）
• 对 \(m_3=5\)：\(M_3 = 60/5=12\)，求 \(12 \times M_3′ \equiv 1 \pmod{5}\)\(12 \equiv 2 \pmod{5}\)，故 \(2 \times M_3′ \equiv 1 \pmod{5}\)，得 \(M_3’=3\)（因 \(2 \times 3=6 \equiv 1 \pmod{5}\)）

代入 CRT 公式 \(x \equiv \sum_{i=1}^3 b_i M_i M_i’ \pmod{m}\)：

\(x \equiv 1 \times 20 \times 2 + 2 \times 15 \times 3 + 1 \times 12 \times 3 \pmod{60}\)

计算：\(40 + 90 + 36 = 166\)，\(166 \div 60 = 2 \text{ 余 } 46\)，故 \(x \equiv 46 \pmod{60}\)。

---

三、方法 2：逐次合并法（两两合并，适合模数量少的情况）

核心思路：每次合并两个同余式，直到只剩一个同余式。合并两个同余式的步骤如下：

合并两个同余式 (\begin{cases} x \equiv a \pmod{m} \ x \equiv b \pmod{n} \end{cases})

1. 设 \(x = mk + a\)，代入第二个式子：\(mk + a \equiv b \pmod{n}\)，整理得 \(mk \equiv b – a \pmod{n}\)；
2. 解关于 k 的一次同余方程：若 \(\gcd(m,n) \nmid (b-a)\)，则无解；若整除，解出 \(k \equiv k_0 \pmod{\frac{n}{\gcd(m,n)}}\)；
3. 回代 \(k = \frac{n}{\gcd(m,n)} t + k_0\)，得 \(x = m \left( \frac{n}{\gcd(m,n)} t + k_0 \right) + a = \frac{mn}{\gcd(m,n)} t + (mk_0 + a)\)，即 \(x \equiv mk_0 + a \pmod{\text{lcm}(m,n)}\)。

用你的例子演示逐次合并：

原方程组：\(\begin{cases} x \equiv 6 \pmod{10} \quad (1) \\ x \equiv 10 \pmod{12} \quad (2) \\ x \equiv 1 \pmod{15} \quad (3) \end{cases}\)

第一步：合并 (1) 和 (2)

设 \(x = 10k + 6\)，代入 (2)：\(10k + 6 \equiv 10 \pmod{12}\)

整理：\(10k \equiv 4 \pmod{12}\)，两边除以 \(\gcd(10,12)=2\)，得 \(5k \equiv 2 \pmod{6}\)

5 在模 6 下的逆元是 5（因 \(5 \times 5=25 \equiv 1 \pmod{6}\)），故 \(k \equiv 2 \times 5 = 10 \equiv 4 \pmod{6}\)

设 \(k = 6t + 4\)，回代得 \(x = 10(6t + 4) + 6 = 60t + 46\)，即 \(x \equiv 46 \pmod{60}\) (4)

第二步：合并 (4) 和 (3)

设 \(x = 60t + 46\)，代入 (3)：\(60t + 46 \equiv 1 \pmod{15}\)

\(60 \equiv 0 \pmod{15}\)，\(46 \div 15 = 3 \text{ 余 } 1\)，故 \(0 + 1 \equiv 1 \pmod{15}\)，恒成立！

因此最终解为 \(x \equiv 46 \pmod{60}\)，与方法 1 结果一致。

---

四、关键注意事项（避坑指南）

1. 优先分解到最高次幂：如 \(12=2^2 \times 3\)，必须分解到 \(\pmod{4}\)，而非仅 \(\pmod{2}\)，否则会丢失约束信息；
2. 相容性检查是核心：若同一素数幂的同余式矛盾（如 \(x \equiv 1 \pmod{2}\) 和 \(x \equiv 0 \pmod{4}\)），直接判定无解；
3. 高次幂蕴含低次幂：如 \(x \equiv 3 \pmod{4}\) 自动满足 \(x \equiv 1 \pmod{2}\)，低次幂的式子可直接删除；
4. 逐次合并时，模会逐渐变大：每次合并后的新模是原两个模的最小公倍数（\(\text{lcm}(m,n)\)），最终模为所有模的最小公倍数。

---

五、矛盾方程组示例（无解情况）

比如：\(\begin{cases} x \equiv 1 \pmod{2} \\ x \equiv 0 \pmod{4} \end{cases}\)

分解后：\(x \equiv 1 \pmod{2}\) 和 \(x \equiv 0 \pmod{4}\)（蕴含 \(x \equiv 0 \pmod{2}\)），矛盾，无解。

---

两种方法各有优劣：分解素数幂适合模多、素数幂少的情况，逻辑清晰；逐次合并适合模少、计算快的情况。你可以根据题目灵活选择。

---

练习题

小学奥数(第011课) 中国剩余定理的相应练习题，余数的相关性质特别重要，希望大家能够重视并且理解和掌握。

①心算

1. 一个两位数除以4余1，除以5余1，除以6余1，那么这个两位数是 。

2.已知一个数除以5余4，除以3余2，那么这个数最小是 。

3.一个数是6的倍数，而且它除以7余2，那么这个数最小是 。

②一个三位数除以30余19，除以40余29，除以50余39，那么这个三位数是多少。

③五年一班所有学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，那么这个班有多少学生。（班级人数不超过100人）

④除以11余5，除以7余6的三位数共有多少个。

⑤韩信点兵：原有士兵人数是1500人，阵亡了四百多人。现在3人一列多2人，5人一列多3人，7人一列多2人，求现在具体还剩下多少士兵。

需要PDF打印版，以及想入群学习的可以关注：沈阳奥数。关于小学奥数，育才少儿班有任何疑问或建议也可以联系刘老师，谢谢大家的支持。会陆续为大家奉献精彩内容。以下是答案与解析，供大家参考。

①心算

1.答案：61

解析：这个数减去1应该是4，5，6的倍数，4，5，6的公倍数(两位数)只有60，所以答案是61。

2.答案：14

解析：5-4=3-2=1，所以这个数加上1应该是5和3的倍数，最小公倍数是15，所以答案是15-1=14

3.答案：30

解析：没有明显特征，逐个验证。6的倍数有0，6，12，18，24，30，36…从小到大验证，30除以7余2。

或者根据余数的和等于和的余数，发现规律6除以7余6，2个6的和除以7余5，余4，3，2(5个6即30)

②答案：589

解析：除数与余数的差都是11，所以这个三位数加上11之后是30，40，50的公倍数。

30，40，50的公倍数最小是600，要求是三位数，所以这个数是600-11=589

③答案：53

解析：除以3余2，除以5余3，除以7余4。

没有余数相同等特征，逐步满足法，7比较大，可以先满足除以7余4

4，11，18，25…发现11满足除以3余2，这时可以用11加上3与7的最小公倍数21来满足除以5余3

11，32，53，74，95，116只有53满足条件。

④答案：12

解析：没有余数相同等特征，逐步满足法，

先看除以11余5

5，16，27，38，…发现27满足除以7余6

11余7的最小公倍数是77，然后用27+77×1=104(符合条件最小的三位数)

符合条件最大的三位数是27+77×12=951

共有12个。

⑤答案：1073

解析：根据题意可知这个数除以3余2，除以5余3，除以7余2。

由于除以3，7的余数相同，可以先算除以3，7余2的数，即2，23，44，65…

经过验证，23即满足除以5余3。所以这个数最小是23

根据题意1500人，阵亡了四百多人，剩下1000多人，即需要满足大于1000小于1100这个条件。3，5，7的最小公倍数是105，即23+105n在1000与1100之间。

易知n=10时，人数是23+105×10=1073