中国剩余定理

维基百科，自由的百科全书

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

[编辑] 物不知数

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

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

即，一個整數除以三餘二，除以五餘三，除以七餘二，求這個整數。中国数学家秦九韶于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。

[编辑] 形式描述

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

一般地，中國剩餘定理是指若有一些两两互质的整数 $m_1, m_2, \ldots, m_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}$ 用一个常用函数 $ζ i, j$ 表示,称之为克罗内克符号(Kronecker).定义:

- 如果 $i = j$ ,则 $ζ i, j = 1$
- 如果 $i\ne j$ ,则 $ζ i, j = 0$

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

对每个1ik,先求出正整数b_i满足b_iζ_i,j(mod m_i),即所求的b_i满足条件:b_i除以m_i餘1,但被每个m_i(ij)整除.其求法如下:
- 记 $r i$ = $m i - 1$ $m i + 1$ … $m k$ ,根据条件 $m 1$ ,…, $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(mod $m i$ ).由此表明 $b i$ 即为所求.
对于前述所求的 $b i$ ,令 $x 0$ = $\sum_{i=1}^k a_ib_i$ ,则