中國剩餘定理又稱孫子定理,數學著作《孫子算經》卷下第二十六題,叫做「物不知數」問題,原文如下:
有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二。問物幾何?即,一個整數除以三餘二,除以五餘三,除以七餘二,求這個整數。《孫子算經》中首次提到了同餘方程組問題,以及以上具體問題的解法,因此在中文數學文獻中也會將中國剩餘定理稱為孫子定理。其實,南宋數學家秦九韶在其著作《數書九章》中,系統的提出並證明了這一類問題的解法,因此這個定理也可以稱為孫子秦九韶定理。
明朝數學家程大位將解法編成易於上口的《孫子歌訣》:
三人同行七十稀,五樹梅花廿一支,七子團圓正半月,除百零五使得知
這個歌訣給出了模數為3、5、7時候的同餘方程的秦九韶解法。意思是:將除以3得到的餘數乘以70,將除以5得到的餘數乘以21,將除以7得到的餘數乘以15,全部加起來後除以105(或者105的倍數),得到的餘數就是答案。比如說在以上的物不知數問題裡面,按歌訣求出的結果就是23。
中國剩餘定理的理論證明比較複雜,這裡就不做敘述,只就如何應用中國剩餘定理做講解。首先,中國剩餘定理應用的題型必須要求除數兩兩互質,這樣才能方便的用中國剩餘定理,否則要做一些變化處理。
例1、一個數被5除餘2,被6除餘4,被7除餘3,這個數最少是多少?
解:第一步:判斷5,6,7兩兩互餘。
第二步:計算5,6,7的最小公倍數,得5×6×7=210。
第三步:計算各除數的逆元。將5去掉,計算6×7=42,42÷5=8……2,將餘數2適當的擴大倍數,使除以5的餘數是1,很顯然這個倍數是3,也就是逆元是3;將6去掉,計算5×7=35,35÷6=5……5,將餘數5適當的擴大倍數,使除以6的餘數是1,很顯然這個倍數是5,也就是逆元是5;將7去掉,計算5×6=30,30÷7=4……2,將餘數2適當的擴大倍數,使除以7的餘數是1,很顯然這個倍數是4,也就是逆元是4;
第四步:將餘數和逆元和最小公倍數除以該數的商相乘,然後將各個結果相加,再除以最小公倍數所得的餘數即為所求。計算42×3×2+35×5×4+30×4×3=1312,1312÷210=6……52,因此這個最小的數就是52。
例2、一個數被3除餘1,被5除餘2,被7除餘3,被8除餘4,這個數最少是多少?
解:第一步:判斷3,5,7,8兩兩互餘。
第二步:計算3,5,7,8的最小公倍數,得3×5×7×8=840。
第三步:計算各除數的逆元。將3去掉,計算5×7×8=280,280÷3=93……1,餘數已經是1了,就不用擴大倍數了,或者說倍數是1,也就是逆元是1;將5去掉,計算3×7×8=168,168÷5=33……3,將餘數3擴大適當的倍數,使除以5的餘數是1,很顯然這個倍數是2,也就是逆元是2;將7去掉,計算3×5×8=120,120÷7=17……1,餘數已經是1了,就不用擴大倍數了,或者說倍數是1,也就是逆元是1;將8去掉,計算3×5×7=105,105÷8=13……1,餘數已經是1了,就不用擴大倍數了,或者說倍數是1,也就是逆元是1;
第四步:將餘數和逆元和最小公倍數除以該數的商相乘,然後將各個結果相加,再除以最小公倍數所得的餘數即為所求。計算280×1×1+168×2×2+120×1×3+105×1×4=1732,1732÷840=52,因此這個最小的數是52。
例3、一個數被5除餘1,被6除餘5,被7除餘4,被11除餘9,這個數最小是多少?
解:第一步:判斷5,6,7,11兩兩互餘。
第二步:計算5,6,7,11的最小公倍數,得5×6×7×11=2310。
第三步:計算各除數的逆元。將5去掉,計算6×7×11=462,462÷5=92……2,將餘數2適當的擴大倍數,使除以5的餘數是1,很顯然這個倍數是3,也就是逆元是3;將6去掉,計算5×7×11=385,385÷6=64……1,餘數已經是1了,這樣逆元就是1;將7去掉,計算5×6×11=330,330÷7=47……1,餘數已經是1了,這樣逆元就是1;將11去掉,計算5×6×7=210,210÷11=19……1,餘數已經是1了,這樣逆元就是1。
第四步:將餘數和逆元和最小公倍數除以該數的商相乘,然後將各個結果相加,再除以最小公倍數所得的餘數即為所求。計算462×3×1+385×1×5+330×1×4+210×1×9=6521,6521÷2310=2……1901,因此這個數就是1901。
總結:應用中國餘數定理時,思路簡單,按照題目所示步驟進行計算就可以了,但計算過程稍顯複雜,若題目具有一定的特殊性,我們也可以採用其他的方法。