# 中国剩余定理

## 物不知数

${\displaystyle 70\times 2+21\times 3+15\times 2=233=2\times 105+23.}$

## 形式描述

${\displaystyle (S):\quad \left\{{\begin{matrix}x\equiv a_{1}{\pmod {m_{1}}}\\x\equiv a_{2}{\pmod {m_{2}}}\\\vdots \qquad \qquad \qquad \\x\equiv a_{n}{\pmod {m_{n}}}\end{matrix}}\right.}$

1. ${\displaystyle M=m_{1}\times m_{2}\times \cdots \times m_{n}=\prod _{i=1}^{n}m_{i}}$是整数m1, m2, ... , mn的乘积，并设${\displaystyle M_{i}=M/m_{i},\;\;\forall i\in \{1,2,\cdots ,n\}}$，即${\displaystyle M_{i}}$是除了mi以外的n − 1个整数的乘积。
2. ${\displaystyle t_{i}=M_{i}^{-1}}$${\displaystyle M_{i}}$${\displaystyle m_{i}}$数论倒数${\displaystyle t_{i}M_{i}\equiv 1{\pmod {m_{i}}},\;\;\forall i\in \{1,2,\cdots ,n\}.}$
3. 方程组${\displaystyle (S)}$的通解形式为：${\displaystyle x=a_{1}t_{1}M_{1}+a_{2}t_{2}M_{2}+\cdots +a_{n}t_{n}M_{n}+kM=kM+\sum _{i=1}^{n}a_{i}t_{i}M_{i},\quad k\in \mathbb {Z} .}$ 在模${\displaystyle M}$的意义下，方程组${\displaystyle (S)}$只有一个解：${\displaystyle x=\sum _{i=1}^{n}a_{i}t_{i}M_{i}.}$

### 证明

${\displaystyle a_{i}t_{i}M_{i}\equiv a_{i}\cdot 1\equiv a_{i}{\pmod {m_{i}}},}$
${\displaystyle \forall j\in \{1,2,\cdots ,n\},\;j\neq i,\;\;a_{i}t_{i}M_{i}\equiv 0{\pmod {m_{j}}}.}$

${\displaystyle \forall i\in \{1,2,\cdots ,n\},\;\;x=a_{i}t_{i}M_{i}+\sum _{j\neq i}a_{j}t_{j}M_{j}\equiv a_{i}+\sum _{j\neq i}0\equiv a_{i}{\pmod {m_{i}}}.}$

${\displaystyle \forall i\in \{1,2,\cdots ,n\},\;\;x_{1}-x_{2}\equiv 0{\pmod {m_{i}}}.}$

${\displaystyle m_{1},m_{2},\ldots ,m_{n}}$两两互质，这说明${\displaystyle M=\prod _{i=1}^{n}m_{i}}$整除${\displaystyle x_{1}-x_{2}}$. 所以方程组${\displaystyle (S)}$的任何两个解之间必然相差${\displaystyle M}$的整数倍。而另一方面，${\displaystyle x=a_{1}t_{1}M_{1}+a_{2}t_{2}M_{2}+\cdots +a_{n}t_{n}M_{n}}$是一个解，同时所有形式为：

${\displaystyle a_{1}t_{1}M_{1}+a_{2}t_{2}M_{2}+\cdots +a_{n}t_{n}M_{n}+kM=kM+\sum _{i=1}^{n}a_{i}t_{i}M_{i},\quad k\in \mathbb {Z} }$

${\displaystyle \{kM+\sum _{i=1}^{n}a_{i}t_{i}M_{i}\;;\quad k\in \mathbb {Z} \}.}$

## 例子

${\displaystyle (S):\quad \left\{{\begin{matrix}x\equiv 2{\pmod {3}}\\x\equiv 3{\pmod {5}}\\x\equiv 2{\pmod {7}}\end{matrix}}\right.}$

${\displaystyle 70=2\times 35\equiv \left\{{\begin{matrix}1{\pmod {3}}\\0{\pmod {5}}\\0{\pmod {7}}\end{matrix}},\right.21=1\times 21\equiv \left\{{\begin{matrix}0{\pmod {3}}\\1{\pmod {5}}\\0{\pmod {7}}\end{matrix}},\right.15=1\times 15\equiv \left\{{\begin{matrix}0{\pmod {3}}\\0{\pmod {5}}\\1{\pmod {7}}\end{matrix}},\right.}$

${\displaystyle 2\times 70+3\times 21+2\times 15\equiv \left\{{\begin{matrix}2\times 1+3\times 0+2\times 0\equiv 2{\pmod {3}}\\2\times 0+3\times 1+2\times 0\equiv 3{\pmod {5}}\\2\times 0+3\times 0+2\times 1\equiv 2{\pmod {7}}\end{matrix}},\right.}$

${\displaystyle x=233+k\times 105,\;k\in \mathbb {Z} .}$

《孙子算经》中实际上给出了最小正整数解，也就是k${\displaystyle =}$-2时的解：x${\displaystyle =}$23.

## 交换环上的推广

### 主理想整环

R是一个主理想整环m1, m2, ... , mk是其中的k个元素，并且两两互质。令M${\displaystyle =}$m1m2...mn为这些元素的乘积，那么可以定义一个从商环R/MR映射到环乘积R/m1R × … × R/mkR同态

${\displaystyle \phi :\;\;\mathrm {R} {\big /}M\mathrm {R} \longrightarrow \mathrm {R} {\big /}m_{1}\mathrm {R} \times \mathrm {R} {\big /}m_{2}\mathrm {R} \times \cdots \times \mathrm {R} {\big /}m_{k}\mathrm {R} }$
${\displaystyle \left.\;\;x+M\mathrm {R} \;\mapsto \;(x+m_{1}\mathrm {R} ,x+m_{2}\mathrm {R} ,\cdots ,x+m_{k}\mathrm {R} )\right.}$

${\displaystyle s_{i}m_{i}+t_{i}M_{i}=1_{\mathrm {R} }.}$

${\displaystyle \varphi :\;\;\mathrm {R} {\big /}m_{1}\mathrm {R} \times \mathrm {R} {\big /}m_{2}\mathrm {R} \times \cdots \times \mathrm {R} {\big /}m_{k}\mathrm {R} \longrightarrow \mathrm {R} {\big /}M\mathrm {R} }$
${\displaystyle \left.\;(a_{1}+m_{1}\mathrm {R} ,a_{2}+m_{2}\mathrm {R} ,\cdots ,a_{k}+m_{k}\mathrm {R} )\;\mapsto \;\sum _{i=1}^{k}a_{i}t_{i}M_{i}+M\mathrm {R} \right.}$

${\displaystyle \mathbb {Z} }$也是一个主理想整环。将以上的R换成${\displaystyle \mathbb {Z} }$，就能得到中国剩余定理。因为

${\displaystyle a_{i}+m_{i}\mathrm {R} =\{x;\;x\;\equiv \;a_{i}{\pmod {m_{i}}}\}}$

### 一般的交换环

R是一个有单位元交换环I1, I2, ... , Ik是为环${\displaystyle \mathbf {R} }$理想，并且当${\displaystyle i\neq j}$时，${\displaystyle I_{i}+I_{j}=\mathbf {R} }$，则有典范的环同构

${\displaystyle \psi :\;\;\mathbf {R} /(I_{1}\cap \cdots \cap I_{k})\longrightarrow \mathbf {R} /I_{1}\times \cdots \times \mathbf {R} /I_{k}}$
${\displaystyle x+I_{1}\cap \cdots \cap I_{n}\longmapsto (x+I_{1},x+I_{2},\cdots ,x+I_{k}).}$

## 模不两两互质的同余式组

84=22×3×7,160=25×5,63=32×7，由推广的孙子定理可得 ${\displaystyle {\begin{cases}x\equiv 23{\pmod {84}}\\x\equiv 7{\pmod {160}}\\x\equiv 2{\pmod {63}}\end{cases}}}$${\displaystyle {\begin{cases}x\equiv 7{\pmod {2^{5}}}\\x\equiv 2{\pmod {3^{2}}}\\x\equiv 7{\pmod {5}}\\x\equiv 23{\pmod {7}}\end{cases}}}$ 同解。[2]

${\displaystyle {\begin{cases}x\equiv 3{\pmod {6}}\\x\equiv 4{\pmod {10}}\\\end{cases}}\Rightarrow {\begin{cases}{\color {Red}x\equiv 1{\pmod {2}}}\\x\equiv 0{\pmod {3}}\\{\color {Red}x\equiv 0{\pmod {2}}}\\x\equiv 4{\pmod {5}}\\\end{cases}}}$

## 参考资料

1. ^ 李俨《大衍求一术的过去和未来》《李俨.钱宝琮科学史全集》卷6 121页《程大位的孙子歌》辽宁教育出版社. 1998
2. ^ 刘古胜 徐东星 余畅. 推广的孙子定理. 高师理科学刊. 2010, (3).