§2 孙子定理孙子定理是数论中的一个重要定理，在数论中的应用非常广泛。

孙子定理给出了在一定条件下同余式组()()()1122mod ,mod ,,mod .k k x b m x b m x b m ≡≡≡ （1）的解的个数，以及求解的方法。

在公元四、五世纪的《孙子算经》中的“物不知数”问题： “今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何?”答案为：“23”。

这个问题也就是求解同余式组()()()2mod3,3mod5,2mod7.x x x ≡≡≡明朝程大位根据孙子算经里所用的方法用歌谣给出了该题的解法：“三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。

”即解为()27032121523323mod105.x ≡⨯+⨯+⨯≡≡在西方，与《孙子算经》同类的算法，最早见于1202年意大利数学家斐波那契的《算经》。

1801年，德国数学家高斯的《算术探究》中，才明确写出了这一问题的求法。

把孙子算经给出的结果加以推广，就得到了如下定理。

定理1（孙子定理）设12,,,k m m m 是k 个两两互质的正整数，12,,1,2,,,k i i m m m m m m M i k ===则同余式组（1）的解是()111222mod ,k k k x M M b M M b M M b m '''≡+++ （2）其中()1mod ,1,2,,.i i i M M m i k '≡=证 因12,,,k m m m 两两互质，故(),1,1,2,,i i M m i k ==于是，对每一个i M ，必有整数i M '使得()1mod .i i i M M m '≡另外，因,,i j m m i j ≠故()1mod ,1,2,,.kjjji i i i i j M M bM M b b m i k =''≡≡=∑即（2）为（1）的解。

若令01kjjjj x M M b='=∑,则0x 是适合（1）的一个整数。

任取一个整数1x ，若()10mod x x m ≡，则()10mod ,0,1,,.i i x x b m i k ≡≡=即1x 也是适合（1）的一个整数。

反之，若1x 是适合（1）的任意一个整数，则()10mod ,1,2,,.i x x m i k ≡=因(),1,,i j m m i j =≠故()10mod ,x x m ≡于是同余式（1）仅有解（2）。

例1 解同余式组()()()2mod3,3mod5,2mod7x x x ≡≡≡ （3）解 这里1233,5,7m m m ===，它们两两互质。

1232,1, 2.b b b ===易得，123357105,5735,3721,3515.m M M M =⨯⨯==⨯==⨯==⨯=求出满足()1351mod3M '≡的一个整数1 2.M '= 求出满足()2211mod5M ≡的一个整数2 1.M '= 求出满足()3151mod7M ≡的一个整数3 1.M '= 由孙子定理得，同余式组（3）的解为()11122233323521213115223mod105.x M M b M M b M M b '''≡++=⨯⨯+⨯⨯+⨯⨯≡ 例2 解同余式组()()()()1234mod5,mod6,mod7,mod11.x b x b x b x b ≡≡≡≡ (4) 解 这里12345,6,7,11,m m m m ====它们两两互质。

1234567112310,6711462,5711385,5611330,567210.m M M M M =⨯⨯⨯==⨯⨯==⨯⨯==⨯⨯==⨯⨯=下面由辗转相除法求出满足()14621mod5M '≡的一个整数1M '。

因4625922,5221,212,=⨯+=⨯+=⨯ 故()()()()15225462592246225185,=+⨯-=+-⨯⨯-=⨯-+⨯于是()()()()46225185,46221mod5,46231mod5.⨯-+⨯⨯-≡⨯≡取1 3.M '=因3856641,=⨯+故()38511mod6.⨯≡取2 1.M '= 因3307491,=⨯+故()33011mod7.⨯≡取3 1.M '= 因21011191,=⨯+故()21011mod11.⨯≡取4 1.M '=于是()12341386385330210mod2310.x b b b b ≡+++ 定理2设12,,,k m m m 是k 个两两互质的正整数， 12,,1,2,,,k i i m m m m m m M i k ===i M '是满足()1mod i i i M M m '≡的一个整数，1,2,,i k =，12,,,k b b b 分别过模12,,,k m m m 的一个完全剩余系，则111222k k k M M b M M b M M b '''+++通过模m 的一个完全剩余系。

证 设111222,k k k x M M b M M b M M b '''=+++则当12,,,k b b b 分别过模12,,,k m m m 的一个完全剩余系时，x 通过m 个整数。

下证这m 个整数对模m 两两不同余。

若()111222111222mod ,k k k k k k M M b M M b M M b M M b M M b M M b m ''''''+++'''''''''≡+++其中,i i M M '''都是i b 所通过的模i m 的完全剩余系中的数，1,2,,i k =，则()mod ,1,2,,.i i i i i i i M M b M M b m i k '''''≡=因(),1,1,2,,,i i i M M m i k '==故()mod ,1,2,,.i i i b b m i k '''≡=又因,i i b b '''都是模i m 的同一完全剩余系中的数，故,1,2,,.i i b b i k '''== 故这m 个整数对模m 两两不同余，从而作成模m 的一个完全剩余系。

补充定理（详见抚州师专学报自然科学版1996年第三期）设12,,,k m m m 是k 个两两互质的正整数，则同余式组（1）有解()111122111mod ,k k k k x m m c m m c m c b m ----≡++++其中111,,,k k m m m c c -=为满足同余式组()()()1112212211133111122111mod ,mod ,mod k k k k k k m c b b m m m c m c b b m m m c m m c m c b b m ----+≡⎧⎪++≡⎪⎨⎪⎪++++≡⎩ 的1k -个整数。

例3 解同余式组()()()()()()1mod 2,1mod 7,2mod11,2mod15,3mod17,3mod19.x x x x x x ≡⎧⎪≡-⎪⎪≡⎪⎨≡-⎪⎪≡⎪⎪≡-⎩（5） 解 因2,7,11,15,17,19两两互质，故可以用补充定理来解该同余式组。

为方便，我们把同余式组（5）改写为()()()()()()3mod19,3mod17,2mod15,2mod11,1mod 7,1mod 2.x x x x x x ≡-⎧⎪≡⎪⎪≡-⎪⎨≡⎪⎪≡-⎪⎪≡⎩（6） 取满足()11933mod17c -≡的一个整数13,c =则119354.c -=取满足()21917542mod15c ⨯+≡-即()2323542mod15c +≡-的一个整数27,c =-则2323542207.c +=-取满足()33231522072mod11c ⨯-≡即()3484522072mod11c -≡的一个整数34,c =则34845220717173.c -=取满足()4484511171731mod7c ⨯+≡-即()453295171731mod7c +≡-的一个整数44,c =则4532951717370468.c += 取满足()5532952704681mod2c ⨯+≡即()5373065704681mod2c +≡的一个整数51,c =则537306570468443533.c +=易知，3730652746130.⨯=故由补充定理得，所给同余式组的解为()443533mod746130.x ≡习题1. 试解下列各题：（ⅰ）十一数之余三，七二数之余一，十三数之余一，问本数。

（ⅱ）二数余一，五数余二，七数余三，九数余四，问本数。

（杨辉：续古摘奇算法（1275）） 解（ⅰ）此题相当于解同余式组()()()2mod 72,1mod13,3mod11.x x x ≡⎧⎪≡⎨⎪≡⎩ （7） 12312372,13,11,2,1, 3.m m m b b b ======由()17221mod13c +≡取12,c =-则1722142.c +=-由27213142c ⨯-即()29361423mod11c -≡取22,c =-则29631421730.c -=易知，9361110296.⨯=故同余式组（7）的解为()1730mod10296.x ≡最小解答为1730.（ⅱ）此题相当于解同余式组：()()()()4mod9,3mod 7,2mod5,1mod 2.x x x x ≡⎧⎪≡⎪⎨≡⎪⎪≡⎩（8） 123412341212312349,7,5,2,4,3,2,1,63,315,630.m m m m b b b b m m m m m m m m m ===========由()1943mod7c +≡ 取13,c =则19431.c +=由()263312mod5c +≡取22c =，则26331157.c +=由()33151571mod2c +≡取30.c =则3315157157.c +=故同余式组（8）的解为()157mod630.x ≡最小解答为157.2.（ⅰ）设123,,m m m 是三个正整数，证明()()[]()1323123,,,,,.m m m m m m m =⎡⎤⎣⎦（ⅱ）设12(,)d m m =，证明：同余式组1122(mod ),(mod )x b m x b m ≡≡ （9）有解的充分必要条件是12.d b b -在有解的情况下，适合（9）的一切整数可由下式求出：[]1,212(mod ,,x x m m ≡（10） 其中1,2x 是适合（9）的一个整数。