中國剩余定理的另一證明

鄧凌云

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

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

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

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

首 先， 我 們 很 容 易 看 出0，1，2， …，m-1 這m 個數(shù)， 每 個 數(shù) 必 滿 足n 個 同 余 式 組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 中的某一個數(shù)。

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

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

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