中国剩余定理

跳过字词转换说明

中國剩餘定理，又称为中国余数定理、孫子剩餘定理，古有「韓信點兵」、「孫子定理」、「鬼谷算」、「隔墻算」、「剪管術」、「秦王暗點兵」、「物不知數」之名，是數論中的一個重要命題。

物不知数

在中國古代著名數學著作《孫子算經》中，有一道題目叫做“物不知數”，原文如下：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

即，一個整數除以三餘二，除以五餘三，除以七餘二，求這個整數。

中国数学家秦九韶于1247年做出了完整的解答，口訣如下

三人同行七十希，五樹梅花廿一支，七子團圓正半月，除百零五使得知

這個解法實際上是，首先利用秦九韶發明的大衍求一術求出5和7的最小公倍數35的倍數中除以3餘數為1的最小一個70（這個稱爲35相對于3的數論倒數），3和7的最小公倍數21相對于5的數論倒數21，3和5的最小公倍數15相對于7的數論倒數15。然後

$70 \times 2 + 21 \times 3 + 15 \times 2 = 233$

233便是可能的解之一。它加減3、5、7的最小公倍數105的若干倍仍然是解，因此最小的解為233除以105的餘數23。

附注：这个解法并非最简，因为实际上35就符合除3余2的特性，所以最小解是：$35 \times 1 + 21 \times 3 + 15 \times 2- 3 \times 5 \times 7 = 128 - 105 = 23$ 最小解加上105的正整数倍都是解。

形式描述

以上解法若推廣到一般情況，便得到了中國剩餘定理的一個構造性證明。

一般地，中國剩餘定理是指若有一些两两互质的整数 $m_1, m_2, \ldots, m_n$，则对任意的整数：$a_1, a_2,...a_n$，以下联立同餘方程组对模 $m_1 m_2 \cdots m_n$ 有公解：

$\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.$

克罗内克符号

为了便于表述，对任意的正整数$\mathbf{i,j}$用一个常用函数$\zeta_{i,j}$表示，称之为克罗内克符号(Kronecker).定义：

$\zeta_{i,j} =\begin{cases} 1, \; i=j \\ 0, \; i \ne j \end{cases}$

使用该符号，即可给出上述一般同餘方程组的求解过程，分两步完成

• 对每个$1 \le i \le k$，先求出正整数$b_i$满足$b_i \equiv \zeta_{i,j} \pmod {m_j}$，即所求的$b_i$满足条件：$b_i \equiv 1 \pmod {m_i}$，但被每个$m_j(i\ne j)$整除。其求法如下：记$r_i =m_{1} \cdots m_{i-1} m_{i+1} \cdots m_k$，根据条件$m_1 ,\cdots,m_k$两两互素，可知$r_i$和$m_i$也互素，故存在整数$c_i$和$d_i$使得$r_i c_i + m_i d_i=1$.令$b_i = r_i c_i$，则对每个$i \ne j$，相对应的$m_j$显然整除$b_i$，并且$b_i \equiv 1 \pmod {m_i}$。由此表明$b_i$即为所求。
• 对于前述所求的$b_i$，令$x_0 = \sum_{i=1}^k a_ib_i$，则$x_0 \equiv a_i b_i \equiv a_i \pmod {m_i}$，这说明$x_0$为上述同餘方程组的一个解，从而所有的解可表示为$x = x_0 + n \prod_{i=1}^k m_i$，其中的n可以取遍所有的整数。

近世交换环及推广

设$\mathbf{R}$为有单位元的交换环，$I_1,\cdots,I_n$为环$\mathbf{R}$的理想，并且当$i \ne j$时，$I_i + I_j = \mathbf{R}$，则有典范的环同构$\mathbf{R} /( I_1 \cap \cdots \cap I_n \cong \mathbf{R} / I_1 \times \cdots \times \mathbf{R} I_n$，其中环同构由映射$\alpha + I_1 \cap \cdots \cap I_n \rightarrow (\alpha + I_1 , \alpha + I_2 ,\cdots, \alpha + I_n$）给出。

应用

埃拉托斯特尼筛法

孙子定理与埃拉托斯特尼篩法结合成为一个素数公式（《品数学》5页。清华大学出版社）

公元前250年埃拉托斯特尼创造了一种筛法：

1. “要得到不大于某个自然数n的所有素数，只要在2—n中将不大于$\sqrt{n}$素数的倍数全部划去即可”。《自然杂志》1991年11期 淑生（即已故浙江大学数学家沈康身）著
2. 我们可以将1.的内容等价转换成为：“如果n是合数，则它有一个因子d满足1<d≤$\sqrt{n}$。参见《初等数论》13页U杜德利著，上海科技出版社。
3. 我们可以把2.的内容等价转换成为：“若自然数n不能被不大于$\sqrt{n}$任何素数整除，则n是一个素数”。代数学辞典 上海教育出版社 1985年 259页。这句话本身就是一个公式。这个公式可以一个不漏地产生所有素数，而不会混入一个合数。
4. 我们可以把3的汉字内容等价转换成为英语字母表示：

$n=p_{1}m_{1}+a_{1}=p_{2}m_{2}+a_{2}=\dots=p_{k}m_{k}+a_{k}.$(1)

其中 $p_{1},p_{2},\dots,p_{k}$表示顺序素数2，3，5，....。a≠0。若$n<P^{2}_{k+1}$,则n是一个素数。

1. 我们可以把（1）式内容等价转换成为同余式组表示：

$n \equiv a_1 \pmod{p_1}, n \equiv a_2 \pmod{p_2}, \dots, n \equiv a_k \pmod{p_k}$（2）

由于（2）的模$p_{1}$,$p_{2}$,...,$p_{k}$ 两两互素，根据孙子定理 (中国剩余定理）知，对于给定的a值，（2）式在$p_{1}$$p_{2}$...$p_{k}$范围内有唯一解。

范例

例如： k=1时，$n=2m_{1}+1$，解得n=3，5，7。求得了（3，3²）区间的全部素数。

k=2时，$n=2m_{1}+1=3m_{2}+1$，解得n=7，13，19；

$n=2m_{1}+1=3m_{2}+2$，解得n=5，11，17，23。 求得了（5，5²）区间的全部素数。

k=3时	$5m_{3}+1$	$5m_{3}+2$	$5m_{3}+3$	$5m_{3}+4$
$n=2m_{1}+1=3m_{2}+1=$	31	7,37	13,43	19
$n=2m_{1}+1=3m_{2}+2=$	11,41	17,47	23	29

求得了（7，7²）区间的全部素数。

仿此下去可以求得任意大的数以内的全部素数。并且一个不漏地求得。由孙子定理知，对于所有可能的 $a_{1}, a_{2} \cdot , a_{k}$值，(1)和(2)式在$p_{1}$$p_{2}$...$p_{k}$范围内，有（$p_{1}-1$）（$p_{2}-1$） ($p_{3}-1$)...（$p_{k}-1$）个解. 两个古代定理与方法融合在一起，使人感到真是：落霞与孤鹜齐飞，秋水共长天一色。

参见

• 埃拉托斯特尼筛法
• 素性判定法则
• 希尔伯特第十问题
• 哥德巴赫猜想
• 孪生素数猜想

参考资料

脚注

参考书目

数学的100个基本问题，靳平 主编，ISBN 7-5377-2171-8