中國(guó)剩余定理的另一證明

鄧凌云

（貴州財(cái)經(jīng)大學(xué)管科學(xué)院城市管理專業(yè)2015 級(jí)，貴州 貴陽(yáng) 550025）

國(guó)外把我們的孫子定理稱為中國(guó)剩余定理（The Chinese Remainder theorem）。 它的具體內(nèi)容為：m1,m2,…mn是n 個(gè)兩兩互素的正整數(shù)，則同余式組x=a1(mod m1),x≡a2(mod m2)，…，x≡an(mod mn)有唯一解，modm,m=m1m2…mn。這里 modm 是指在模 m 的一個(gè)完全剩余系中， 如0，1，2，…，m-1 是模m 的一個(gè)完全剩余系。

孫子定理可以用數(shù)學(xué)歸納法證明，如文[1]、[2]。更多的是用構(gòu)造法具體給出同余式組的解， 再證明唯一性，如文[3]、[4]、[5]。 本文打算用整體思維的方法，給出一個(gè)存在性的證明（包括唯一性）。

要 證 明 孫 子 定 理， 只 需 證 明： 當(dāng)0 ≤ai≤mi-1，i=1,2,…,n 的情況，結(jié)論成立即可。

首 先， 我 們 很 容 易 看 出0，1，2， …，m-1 這m 個(gè)數(shù)， 每 個(gè) 數(shù) 必 滿 足n 個(gè) 同 余 式 組x ≡b1(mod m1)，x ≡b2(mod m2)， …，x ≡bn(mod mn)， 這 里b1,b2, …bn分 別 是0，1，2， … ，m1-1；0，1，2， … ，m2-1； … ；0，1，2， … ，mn-1 中的某一個(gè)數(shù)。

其次，我們可以證明在0，1，2，…，m-1 這m 個(gè)數(shù)不可能有兩個(gè)數(shù)同時(shí)滿足同一個(gè)同余式組。 否則，有兩 個(gè) 數(shù)x1，x2，x1

從以上兩個(gè)方面， 我們可以根據(jù)用反證法證明的類似于抽屜原理的命題 “把m 個(gè)物體放入m 個(gè)抽屜里， 每個(gè)抽屜最多放一個(gè)， 那么每個(gè)抽屜恰好有一個(gè)物 體。 ”得 出：m(=m1m2…mn)個(gè) 同 余 式 組x ≡b1(mod m1)，x ≡b2(mod m2)，… ，x ≡bn(mod mn)，其 中b1通 過(guò)0，1，2，…，m1-1；b2通過(guò)0，1，2，…m2-1；…；bn通過(guò)0，1，2，…，mn-1，每個(gè)同余式組恰好有一個(gè)解在0，1，2，…，m-1 中。

這就證明了：若m1，m2，…，mn是n 個(gè)兩兩互素的正整數(shù),則對(duì)任意的n 個(gè)整數(shù)aj，0 ≤ai≤mi-1，i=1，2，…，n，同 余 式 組x ≡a1(mod m1)，x ≡a2(mod m2)，…，x ≡an(mod mn)有唯一解mod m。 很明顯，對(duì)一般ai取消限制條件0 ≤ai≤mi-1 定理也成立。