韓信點兵 (第 6 頁)

　1│2│3│4│5│6　

韓信點兵（第 6 頁）

莫宗堅

首頁 | 搜尋

．原載於科學月刊第一卷第一期
．作者當時任教於普渡大學數學系

‧註釋
‧對外搜尋關鍵字

六、

故事講完了，現在讓我們一起研究一下孫子定理──或者中國剩餘定理。數學的發展和數字的寫法以及公式的表達法有密切的關係。中國古代盛行代數，是受了中國優良的記數法的影響。到了近代，由於人類發明＝,－,＋,×, $\div$ ，以及用抽象符號 x,y,a,b 代表數字，使得代數成為易懂的數學。對於「剩餘」這個概念，我們也要引進一種符號來幫助了解，記憶。

首先「三數剩二」是什麼意思呢？那不過說某一個數 x 被 3 除剩餘 2；換句話，x-2 被3整除。我們用下式表示「三數剩二」

$\begin{displaymath} x \equiv 2 \pmod{3} \end{displaymath}$

定義1：已知 a-b 被 m 整除，我們說「a、b 對模 m 同餘」。用下式（同餘式）表示。

$\begin{displaymath} a \equiv b \pmod{m} \end{displaymath}$

反之，

$\begin{displaymath} a\not\equiv b \pmod{m} \end{displaymath}$

表示「a,b 對模 m 不同餘」；換句話 a-b 不是 m 的倍數。

例1： $25 \equiv -3 \pmod{7}$

例2： $a \equiv 1 \pmod{2}$ 表示 a 是一個奇數。

例3： $a \equiv 0 \pmod{2}$ 表示 a 是一個偶數。

例4：「物不知其數，三三數之剩二，五五數之剩三，七七數之剩二」可用同餘式表示如下。

$\begin{eqnarray*} x & \equiv & 2 \pmod{3} \\ x & \equiv & 3 \pmod{5} \\ x & \equiv & 2 \pmod{7} \end{eqnarray*}$

「韓信點兵問題」就是求一組同餘式的公解。「 $\equiv$ 」與等式「＝」有同樣的運算法則，那就是說：

定理1：已知 $a\equiv b \pmod{m}$ ， $c\equiv d \pmod{m}$ ，那麼， $ac \equiv bd \pmod{m}$ ， $a+c \equiv b+d \pmod{m}$ ， $a-c\equiv b-d \pmod{m}$ ， $-a \equiv -b \pmod{m}$ ， $a \equiv a \pmod{m}$ 。

證明：我們先證 $a+c \equiv b+d \pmod{m}$ ，讀者可以仿照我們的證法，去證明其餘公式。

根據「 $\equiv$ 」的定義，我們知道 a-b = sm，c-d = tm 所以

(a+c) - (b+d) = (a-b)+(c-d) = sm+tm = (s+t)m

那就是說， $a+c \equiv b+d \pmod{m}$ 證完。

在推演孫子定理（中國剩餘定理）的過程中，我們須要一個應用兩數互質（兩數的最大公約數是1）的定理，那就是：

定理2：已知 m,n 適合下式， am+bn=1，那麼 m,n 互質，反過來說，如果 m,n 互質，我們可以找到 a,b，使得

am+bn=1

證明：因為 m,n 的最大公約數可以整除 am+bn，而 am+bn=1，所以 m,n 的最大公約數是1，換句話， m,n 互質。反過來說，如果己知 m,n 互質，讀者可以應用輾轉相除法，求得 a,b 使得 am+bn=1，證完。

應用定理2，我們可以解答漂母數布匹的問題了，那就是下面的定理3:

定理3：己知 m,n 互質，那麼下列一組同餘式：

$\begin{eqnarray*} x & \equiv & 1 \pmod{m} \\ x & \equiv & 0 \pmod{n} \end{eqnarray*}$

有公解。

證明：根據定理2，我們可以找到 a,b 使得 am+bn=1，所以 bn=1-am，那麼 $bn = 1-am \equiv 1 \pmod{m}$ ， $bn \equiv 0 \pmod{n}$ ，換句話，bn 是我們所求的一組公解，證完。

系1：己知 m₁ 與 m₂，m₁ 與 m₃，… m₁ 與 m_t 都互質，那麼下列一組同餘式

$\begin{eqnarray*} x & \equiv & 1 \pmod{m_1} \\ x & \equiv & 0 \pmod{m_2} \\ & \vdots & \\ x & \equiv & 0 \pmod{m_t} \end{eqnarray*}$

有公解。

證明：根據已知條件，我們推論 m₁ 與 $m_2m_3\cdots m_t$ 互質。在應用定理3，我們知道

$\begin{eqnarray*} x & \equiv & 1 \pmod{m_1} \\ x & \equiv & 0 \pmod{m_2m_3 \cdots m_t} \end{eqnarray*}$

有公解。顯然上面那組同餘式的公解就是

$\begin{eqnarray*} x & \equiv & 1 \pmod{m_1} \\ x & \equiv & 0 \pmod{m_2} \\ & \vdots & \\ x & \equiv & 0 \pmod{m_t} \end{eqnarray*}$

的公解，證完。

定理4：己知 m₁,m₂,…,m_t 兩兩互質，並且求出 a₁ 是 $x \equiv 1 \pmod{m_1}$ ， $x \equiv 0 \pmod{m_2}$ ，…， $x \equiv 0 \pmod{m_t}$ 的一個公解，a₂ 是 $x \equiv 0 \pmod{m_1}$ ， $x \equiv 1 \pmod{m_2}$ ， $x \equiv 0 \pmod{m_3}$ ，…， $x \equiv 0 \pmod{m_t}$ 的一個公解，以此類推，求出 a₃,…,a_t。那 $n_1a_1 + n_2a_2 + \cdots + n_ta_t$ 就是下列一組同餘式

$\begin{eqnarray*} x & \equiv & n_1 \pmod{m_1} \\ x & \equiv & n_2 \pmod{m_2} \\ & \vdots & \\ x & \equiv & n_t \pmod{m_t} \end{eqnarray*}$

的一個公解。

證明：我們先證明 $x \equiv n_1 \pmod{m_1}$ ，讀者可以仿照我們的證法，去證明其餘同餘式。

根據己知條件，我們知道 $a_2\equiv 0 \pmod{m_1}$ ， $a_3 \equiv 0 \pmod{m_1}$ ， …， $a_t \equiv 0 \pmod{m_1}$ ，應用定理1，我們得出 $n_2a_2 + n_3a_3 + \cdots + n_ta_t \equiv 0 \pmod{m_1}$ ，並且已知 $a_1 \equiv 1 \pmod{m_1}$ ，所以應用定理1，我們得出 $n_1 a_1 \equiv n_1 \pmod{m_1}$ ，再應用一次定理1，我們證明

$\begin{displaymath} n_1a_1+n_2a_2+\cdots +n_ta_t \equiv n_1 \pmod{m_1} \end{displaymath}$

證完。

上面的定理4事實上就是孫子算經裡的解法。 a₁, a₂,…,a_t 也就是孫子算經裡面提到的「用數」。定理4再加上下面的定理5就合成了數論中的孫子定理。

定理5：己知 m₁,m₂,…,m_t 兩兩互質。並且求出 a,b 是下列一組同餘式

$\begin{eqnarray*} x & \equiv & n_1 \pmod{m_1} \\ x & \equiv & n_2 \pmod{m_2} \\ & \vdots & \\ x & \equiv & n_t \pmod{m_t} \end{eqnarray*}$

的兩個公解。那麼 a-b 一定是 $m_1m_2\cdots m_t$ 的倍數。反過來說， $a\pm cm_1m_2\cdots m_t$ 也是那一組同餘式的公解。

證明：因為 $a\equiv n_1 \pmod{m_1}$ ， $b \equiv n_1 \pmod{m_1}$ ，應用定理1，我們得到 $a-b \equiv n_1-n_1 \equiv 0 \pmod{m_1}$ ，換句話，a-b 被 m₁ 整除。同樣道理 m₂,…,m_t 都可以整除 a-b。根據已知條件，m₁,m₂,…,m_t 兩兩互質，所以 a-b 一定被 $m_1m_2\cdots m_t$ 整除，那就是說，a-b 是 $m_1m_2\cdots m_t$ 的倍數。反過來說，應用定理1， $a\pm cm_1m_2\cdots m_t$ 自然也是一個公解。證完。

上面所談的都是數論的內容。如果我們把上面的定義，定理，系以及證明中的整數 m,n,a,b,m₁,n₁,…，等等都換成一元多項式 m(x), n(x), a(x), b(x), m₁(x), n₁(x), … 等等。我們就得到方程式論中的孫子定理了。

例如定理3可以改寫成：

定理3：已知 m(x), n(x) 互質，那麼下列一組同餘式，

$\begin{eqnarray*} x & \equiv & 1 \pmod{m(x)} \\ x & \equiv & 0 \pmod{n(x)} \end{eqnarray*}$

有公解。

在許多抽象數學的領域中，也有孫子定理。不過，因為牽涉的入門知識太多，這兒也就一言表過不提了。

關於孫子定理，現代數學家已有廣泛透徹的研究。讀者如果有興趣，可以參看一點數論及近代代數的書籍。這篇淺文的主要目的，也就是引起讀者對數學的興趣而已。

習題

習題1：七數剩一，八數剩二，九數剩三，問本數。

習題2：十一數餘三，十二數餘二，十三數餘一，問本數。

習題3：二數餘一，五數餘二，七數餘三，九數餘四，問本數。

（以上三題見楊輝《續古摘奇算法》(1275)）
註：所謂本數就是最小解。

習題4：求一個一元多項式 f(x) 適合下列同餘式：

$\begin{eqnarray*} f(x) & \equiv & x \pmod{x^2+1} \\ f(x) & \equiv & 3x+1 \pmod{x+1} \end{eqnarray*}$

　1│2│3│4│5│6　


	（若有指正、疑問……，可以在此留言或寫信給我們。）

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有

編輯：陳文是

最後修改日期：5/25/2002