．孙子定理（中国剩余定理）

如何解下面重要的同余式组
X≡bl(modm1)， x≡b2 (mod m2)，…，
X≡bk(mod mk)．
在我国古代的《孙子算经》(纪元前后)里已经提出了这种
形式的问题，并且很好地解决了它．《孙子算经》里所提出的
问题之一如下： ．
“今有物不知其数，三三数之剩二，五五数之剃三，七七数
之剩二，问物几何?”“答日二十三”(译：有一堆东西不知道有
．多少个，用三来除这堆东西的个数时所得到的余数是二，用五
来除这堆东西的个数时所得到的余数是三，用七来除这堆东
西的个数时所得到的余数是二，问这堆东西共有多少个?答
案是二十三个．)
把这个问题的提法用同余式的式子来表达，它可以被写
成下面的形式：
解同余式组(设x是所求物数)
x≡2(mod 3)，x≡3(mod 5)，x≡2（mod7）
关于解一般的同余式组
X≡a(mod 3)，x≡b(mod 5)，x≡c（mod）
则有
X≡70a+21b+15c(mod 105)．
关于这个一般的解法，在明朝程大位的《算法统宗》(1 593)里
有一首歌，就是：
三人同行七十稀，
五树梅花廿一枝，
七子团圆整半月，
除百零五便得知．
(译：三个人共同走路，其中有七十岁以上的老年人的可能性
很少，五棵梅花树总共二十一枝，七个孩子当正月十五日时在
家中团圆，把一百零五的某个倍数减去，就得到答案．)所以关
于解同余式组的问题，在我国古代有极光辉的研究成果．我
国古代数学家孙子发明了下面的中外驰名的定理．
定理I如果k≥2，而
ml，m2，…mk
是二二互素的是个正整数，也就是说，在这k个正整数中任意
取出二个正整数来，则这二个正整数是互素的．令
M=m1m2m3..mk=m1M1=m2M2=….mkMk
则同时满足同余式组
X≡bl(modmi)， x≡(mod m2)，…，
X≡bk(modmk)
的正整数解是
X≡blM1'Ml十b2M2'M 2+…+bkMk'Mk(modM)．
这里M：是满足同余式
Mi'Mj≡1(modmk)
的正整数解，i=1，2，…，k．
证因为m1，m2，m3，…，mk是二二互素的，所以当i≠j
时，则有(mi，mj)=1．由于Mi=M/mi，得至 (Mi，mi)=1，
所以
(M1，m1)=(M2，m2)=…=(Mk，mk)=1．
由(M1，m1)=1和引理1，我们知道存在有二个整数
M1'，n1。使得M1M1'+m1n1=1．所以存在有一个M1'使得
M1Ml'≡l(modml)
成立．用同样方法知道对于每一个Mi，一定存在有一个正
整数Mi?使得
MiMi?≡1(modmi)． (47)
另一方面，当i≠j时，则由(mi，mj)=1和Mj=M/mj
得到mi∣ Mj．所以有
． bjMjMj'≡0(modmi)． (48)
由(47)式和(48)式我们有
b1M'Ml+b2M'2M3+…+bkMk'Mk≡biMi'Mi
≡bi（modmi） (49)
由ml，m2，m3：，…，mk是二二互素的和(49)式，知道(46)式是
满足(43)式的正整数解．如果y也能同时满足(43)式，则

由于(46)式是满足(43)式的正整数解，则得
X≡Y(modm1)，x≡y (mod m2)，…，
X≡y，(modmk)，
也就是m1︱(x-y)，m2︱ (x-y)，…，mk︱(x-y)．因为
M1，m2，m3…..mk是二二互素的，所以有M ︱(x-y)，也就是
X≡y(modM)．
所以x≡blM1'MI+b2M2'M 2+…+bkMk'Mk(mod M)是
满足(43)式的唯一正整数解．因此定理1得证．