# 中國剩餘定理

## 物不知數

${\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} }$

《孫子算經》中實際上給出了最小正整數解，也就是 ${\displaystyle k=-2}$ 時的解：${\displaystyle x=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).