§ 2孙子定理孙子定理是数论中的一个重要定理， 在数论中的应用非常广泛。
孙子定理给出了在一定 条件下同余式组x b^ mod m i ,x b 2 mod% J||,x d modm k .（ 1）的解的个数，以及求解的方法。
在公元四、五世纪的《孙子算经》中的 物不知数”问题： “今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何 ？”答案为：“23”。
这个问题也就是求解 同余式组x 2 mod3 ,x 3 mod5 ,x 2 mod7 .明朝程大位根据孙子算经里所用的方法用歌谣给出了该题的解法： 三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。
"即解为x 2 70 3 21 2 15 233 23 mod105 .在西方，与《孙子算经》同类的算法，最早见于 1202年意大利数学家斐波那契的《算经》。
1801年，德国数学家高斯的《算术探究》中，才明确写出了这一问题 的求法。
把孙子算经给出的结果加以推广，就得到了如下定理。
定理1 （孙子定理） 设m 1,m 2,川，m k 是k 个两两互质的正整数，m i M i ,i则同余式组（1）的解是其中M i M i 1 modm ,i 1,2,卅,k. M i ,m 1,i 1,2j||,k 于是，对每一个 M i ，必有整数 M j 使得M j M j 1 modm i另外，因 m m j ,i j,故M j M j b j M j M j b b i mod m i , i 1,2^ |, k.j 1即（2 ）为（1）的解。
k若令X 。
M j M j b j ,则x o 是适合（1 ）的一个整数。
任取一个整数捲，若j 1x x 0 modm ，则x M 1 M 1b 1M 2M 2b 2 ||| M k M k b k modm ,(2)证因g, m 2,川,m k 两两互质，故X i X o b modm ,i 0,lJ||,k.即X i 也是适合（1）的一个整数。
反之，若X i 是适合（1 ）的任意一个整数，则2.1. 1.2 1 213 1 15 2 23 mod105 例2解同余式组X b mod5 , X b 2 mod6 , X Q mod7解 这里m 1 5,m 2 6, m 3 7, m 4 11,它们两两互质。
m 5 6 7 11 2310,M 1 6 7 11 462, M 25 7 11 385,M 35 6 11 330,M 45 6 7 210.下面由辗转相除法求出满足462M 1 1 mod5的一个整数 M 1。
因462 5 92 2, 5 2 2 1, 2 1 2,故1 52 25 462 5 9224622 5 185, 于是 4622 5 185,46221 mod5 ,4623 1 mod5 .取x 1 x 0 mod m ,i12 川,k.1,i j,故N X o modm ,于是同余式1 ）仅有解（2 ）。
例1解同余式组X 2 mod3 ,X 3 mod5 ,X 2 mod7 (3)解这里m 13, m 2 5, m 3 7，它们两两互质。
b 12,b 2 1,b 3 2.易得，3 721,M 33 5 15.求出满足35M 1 1 mod3的一个整数 M 1求出满足 21M 2 1 mod5 的一个整数 M 2求出满足 15M 31 mod7 的一个整数M 3由孙子定理得，同余式组（ 3）的解为X b 4 mod11 .m 3 5 7105, M 1 5 735, MX M 1 M 1b 1 M 2 M 2b 2 M 3 M 3b 3 2 35因385 6 64 1,故385 1 1 mod6 . 取M2 1.因330 7 49 1,故330 1 1 mod7 . 取M3 1..取M4因210 11 19 1,故210 1 1 mod11于是x 1386b, 385b2 33Cb3 210b4 mod2310 .定理2设叶，口2,川，m k是k个两两互质的正整数，m m1m2 |||m k,m rni i MJ 1,2,|||,k,M i 是满足M i M i 1 mod m 的一个整数，i 1,2j||,k , b.,b2,川，b k分别过模m1,m2I，m k 的一个完全剩余系，则M1 M1b） M2M2b2 ||| M k M k b<通过模m的一个完全剩余系。
证设x M1 M1b1 M2M2b2川M k M k b k,则当D,b2,1”，b k分别过模m1, m2,川，m k的一个完全剩余系时，x通过m个整数。
下证这m个整数对模m两两不同余。
若M1 M1b1 M2M2b2川M k M k QM1 M1b1M2M2b2||| M k M k b k modm ,其中M j ,M j都是b i所通过的模m i的完全剩余系中的数，i 1,2,|||,k，贝UM i M i b i M i M i b i mod m ,i 1,2，卅，k.因M i M i,m i 1,i 1,2,|||,k,故b b mod m i ,i 1,2，川,k.又因b ,b 都是模m i的同一完全剩余系中的数，故b i b ,i 1,2，川，k.故这m个整数对模m两两不同余，从而作成模m的一个完全剩余系。
补充定理（详见抚州师专学报自然科学版1996年第三期）设mh,m 2,川，m k 是k 个两两互质的正整数，则同余式组（1）有解x m^ |||m< i C k i m ||卜 25 2 卅 EG其中m m i |||m k ,c 1^|,c k 1为满足同余式组m 1Ci bi b 2 mod m 2 m 1 m 2c 2 gq b i b 3 mod m 3的k 1个整数。
例3解同余式组x 1 mod2 , x 1 mod7 , x 2 mod11 , x 2 mod15 ,x 3 mod17 , x 3 mod19 .解 因2,7,11,15,17,19两两互质，故可以用补充定理来解该同余式组。
为方便，我们把同余式组（5）改写为x 3 mod19 , x 3 mod17 , x 2 mod15 , （6）x 2 mod11 , x 1 mod 7 , x 1 mod2 .取满足19c 1 3 3 mod17的一个整数c 13,则19c 1 354.取满足 19 17c 2 54 2 mod15 即323c 2 542 mod15bi mod m ,||| m^ b 1b k mod m k(5)mmj||m k 2C k 2的一个整数c27, 则323c2 54 2207.取满足323 15c3 2207 2 mod11 即4845c3 2207 2 mod11的一个整数c3 4, 则4845c3 2207 17173.取满足4845 11c4 17173 1 mod7 即53295c4 17173 1 mod7的一个整数c4 4, 则53295c4 17173 70468.取满足53295 2c5 70468 1 mod2 即373065c5 70468 1 mod2的一个整数c5 1, 则373065c5 70468 443533.易知，373065 2 746130.故由补充定理得，所给同余式组的解为x 443533 mod746130 .习题1. 试解下列各题：(i)^一数之余三，七二数之余一，十三数之余一，问本数。
(ii)二数余一，五数余二，七数余三，九数余四，问本数。
(杨辉：续古摘奇算法( 1275)) 解(i)此题相当于解同余式组x 2 mod72 ,x 1 mod13 , ( 7 )x 3 mod11 .m1 72,m2 13,m3 11,b1 2,b2 1,b3 3. 由72c1 2 1 mod13取c 1 2, 则72c 1 2 142.由72 13c 2 142 即936c 2 142 3 mod11取 c 22,则 963c 2 142 1730.易知， 936 11 10296.故同余式组( 7)的解为 x 1730 mod10296 . 最小解答为 1730.(ii)此题相当于解同余式组：9c 1 4 31.由63c 2 31 2 mod5 取 c 2 2 ，则63c 2 31 157.由 315c 3 157 1 mod2 取 c 3 0. 则315c 3 157 157.故同余式组( 8)的解为x 157 mod630 .最小解答为 157.x 2 mod5 ,( 8 )x 1 mod 2 .m 1 9,m 2 7,m 3 5,m 4 2,b 14,b 2 3,b 3 m 1m 2 63,m 1m 2 m 3315, m 1m 2m 3 m 4 630.由9c 1 4 3 mod7 取c 1 3,则x 4 mod9 , x 3 mod 7 ,2,b 4 1,2. (i)设m i ,m 2,m 3是三个正整数，证明mi, m 3 , m 2, m 3m^m b ,讥.(ii)设d (m i ,m 2)，证明：同余式组x “(modg), x b 2(modm 2 )(9)有解的充分必要条件是 d b 1 b 2.在有解的情况下，适合(9)的一切整数可由下式求出：x x 1,2(mod m^m ? ,(10)其中勺2是适合(9)的一个整数。
(iii)应用(i) , (ii)证明同余式组x b i (mod m i ), i 12|||,k(11)有解的充分与必要条件是(m,m j )(b b j ), i, j 1,2，卅,k.(12)并且在有解的情况下，适合(11)的一切整数可由下式求出：x X 1,2,|||,k mod m 1,m h ,|||皿(13)x 1,2, ,k 其中是适合(11)的一个整数。
容易证明m 22p2P,2 '2 1 '2 1其中, P l , P 2,|||, P k 为互不相同的素数。
则0,叫，min 1, 1min 2,2min k , k P k ,m 1,m 3P 1P 2min 1, 1min 2 ■,2min k , k Pk,m 2, m 3 P 1 P 2m ,m 2max 1, 1P1 1 1max 2P 2,q|(P k max k,k ,max min 1, 1 ,min1, 1 max min 2, 2 ,min2,2max min k , k ,min k , kPkm 2, m 3 P 1P 2gm ,m )31,1,1min maxP lmin max P 2k ， k ，k2,2,2min maxp kmax min ,min min max (14) (不妨设•分三种情形①；②；③•易证(14)式成立。