详析孙子定理

赵云平

【摘要】孙子定理在各版本的初等数论教材中均有介绍，但细节不够明确，使读者在学习过程中产生很多疑问，本文在给出孙子定理的基础上，通过实例详细分析了孙子定理的算法，让更多的读者受益.

【关键词】孙子定理;同余式;一次同余式组

孙子定理在数论及近世代数学领域是非常重要的理论，起着基础作用，所解决的问题是求未知量的系数为1，模两两互质的一次同余式的解.它在国际上被称为中国剩余定理或中国余数定理，是数论中一个重要定理，定理的构造值得仔细推敲.求解一个未知数联立同余式组，通常应用“孙子定理”，这是初等数论教材中介绍的主要算法.

1 基本概念

定义1[1] 给定一个正整数m，把它叫作模.如果用m去除任意两个整数a和b，所得余数相同，称a与b关于模m同余，记作a≡b（mod m）.若余数不同，称a与b关于模m不同余，记作a≠b（mod m）.

定义2[2] 设f（x）=anxn+an-1xn-1+…+a0，其中ai是整数，m是一个正整数，就把f（x）=anxn+an-1xn-1+…+a0≡0（mod m）叫作模m的同余式，n就叫作这个同余式的次数.

定理1[2] 一次同余式ax≡b（mod m），当（a，m）=1时，有唯一解.

定理2[2] （a，b）=1存在整数s，t，使as+bt=1.

定理3（传递性）[4] 如果a≡b（mod m），b≡c（mod m）a≡c（mod m）.

2 孙子定理

定理4（孙子定理）[1-6] 设m1，m2，…，mk是k个两两互质的正整数，

M=m1m2·…·mk=∏ki=1mi，Mi=Mmi，i=1，2，…，k，则同余式组x≡b1（mod m1），x≡b2（mod m2），…，x≡bk（mod mk）的解是x≡M′1M1b1+M′2M2b2+…+M′kMkbk（mod m），其中Mi′Mi≡1（mod mi），i=1，2，…，k.列表如下：

这个孙子定理就给出了求解一次同余式组的一般算法，这是关于模m的运算.

3 具体算法与实例

这个方法具体是什么呢？来看几个例子.

例1 求解同余式组

x≡1（mod 3），x≡-2（mod 5），x≡4（mod 11）.

分析 把它列成一个表，大体上就是这样一个算法.

它有这样几项，除数、余数、最小公倍数、衍数、乘率、各总、答数，最后还可以求出最小答數.这里除数分成三个，除数分别是3，5，11，余数分别是1，-2，4，衍数是什么呢？如果对应除数3，那就是另外两个除数相乘，那就是5×11，对应除数5的就是3×11，对应除数11的就是3×5;来看这个乘率，就是1，2，3，这个所谓乘率是什么呢？求乘率稍麻烦一点，就是让衍数5×11=55乘上x关于模3余1的解，即55x≡1（mod 3），这个式子的解怎么求？因为（55，3）=1，1|1有解，实际上就是转化为求二元一次不定方程55s+3t=1的解，这种方法过程不够简便，那这个一次同余式里边，怎么方便地求出x呢？首先把55除以3，商18余1，所以55x≡1（mod 3）就变成了x≡1（mod 3），这是因为55≡1（mod 3），又x≡x（mod 3），有55x≡x（mod 3），又根据同余的传递性，所以x≡1（mod 3）;另一种处理同余式55x≡1（mod 3）的方法，就是当模不是太大的时候，可以把小于模3的3个整数0，1，2分别代入同余式试一下，看谁满足，所以可以推出x≡1（mod 3），所以除数3对应的乘率是1.再看下一个3×11=33，33x≡1（mod 5），把33除以5，商6余3，所以33x≡1（mod 5），就变成了3x≡1（mod 5），模5不是很大可把小于模5的整数0，1，2，3，4这5个整数分别代入，容易得出x≡2（mod 5），除此之外还有一种处理方式，就是想办法把x的系数变成1，通过把x的系数变到和模5越来越接近，比如5和4，6很接近，比如3x≡1（mod 5），两边乘上2，6x≡2（mod 5），又6≡1（mod 5），所以6x≡x（mod 5）x≡2（mod 5），所以除数5对应的乘率是2，在解同余式的过程中根据具体题目多种方法融入使用更加简便.同样地，3×5=15，15x≡1（mod 11），15≡4（mod 11），得4x≡1（mod 11），两边同乘3，12x≡3（mod 11），12≡1（mod 11），所以x≡3（mod 11），除数11对应的乘率是3.然后是各总，各总是什么呢？各总就是衍数、乘率、余数的乘积，55×1×1=55，33×2×（-2）=-132，15×3×4=180，答数就是55+（-132）+180=103，也就是各总之和，那么这个答数可能会比较大，而且大于最小公倍数，要求它是最小的正整数，则这个最小答数就是用答数除以最小公倍数求余数，或答数减去最小公倍数的倍数.算出最小答数代回同余式组验证一下是否满足，如果在验证的过程中不满足某一个，说明该行可能算错了，经检验103是最小答数，这是孙子定理的算法.对于同余式组来说，要求出所有的解，也是很容易的，刚才在求最小答数的时候是减去最小公倍数的若干倍，现在是加上165的若干倍，所有解x≡103+165k，k∈Z.

解 ∵ 3，5，11两两互质，由孙子定理得

m=3×5×11=165，

M1=5×11，5×11×M′1≡1（mod 3），M′1=1，

M2=3×11，3×11×M′2≡1（mod 5），M′2=2，

M3=3×5，3×5×M′3≡1（mod 11），M′3=3，

∴x≡5×11×1×1+3×11×2×（-2）+3×5×3×4（mod 165）

≡103（mod 165）.

例2 求解同余式组x≡5（mod 7），x≡3（mod 12），x≡17（mod 55）.

分析 要求这个同余式组，列表如下：

其中乘率，求660x≡1（mod 7）的解，（660，7）=1，1|1有解，这个解怎么来求呢？實际上就是求660s+7t=1.来看怎么方便快捷地求出x，首先我们把660除以7，商94余2，所以660x≡1（mod 7）就变成了2x≡1（mod 7），为什么660可以写成被7除的余数2呢？因为660≡2（mod 7），两边同乘x，660x≡2x（mod 7），要找660x≡1（mod 7），由同余的传递性，有2x≡1（mod 7）.所以由660x≡1（mod 7）就推出2x≡1（mod 7），那返回去怎么办呢？返回去实际上也是一样的，因为660x与2x同余，2x与1同余，由传递性，所以660x与1同余，因此660x≡1（mod 7）2x≡1（mod 7），然后从2x≡1（mod 7）里边找x，怎么找呢？因为（2，7）=1，所以它只有1个解，现在我们要求2s+7t=1很容易.或当模不是太大的时候，我们也可以从0到6一个一个代进去试一下，看谁满足，所以可以推出x=4，因此除数7对应的乘率是4.在这里还有一种解法，就是想办法把x的系数变成1，通过把x的系数变到和7越来越接近，比如6和8与7很接近，比如在2x≡1（mod 7）两边乘上3，得6x≡3（mod 7），因6模7余-1，所以-x≡3（mod 7），两边乘-1，x≡-3（mod 7），-3被7除，因-3=-1×7+4，找最小正整数，就是4，所以x=4，或者在式子2x≡1（mod 7）两边乘4，得8x≡4（mod 7），又8模7余1，x≡4（mod 7），所以得到的也是4，这是乘率.这个除数和余数根据同余式组可以直接写出来，最小公倍数的计算也简单.衍数呢？在除数里边，除了这一行所在的数，把其他几个除数乘起来便可.乘率稍稍麻烦一点，要把它们解出来，对于模7，4是第一个乘率.对于模12的乘率，就是要找385x≡1（mod 12）的解，现在我们还是按刚才的办法，385太大，把它变小，就是385被12除找余数，385除以12，商32余1，原同余式等价于x≡1（mod 12），所以12对应的乘率为1，最后一个乘率，找84x≡1（mod 55）的解，当然我们还是用84被55除，来看它的余数，29x≡1（mod 55），下面我们再让它接近55，然后再去掉55的倍数，上式两边乘2，得58x≡2（mod 55），再模一个55，得3x≡2（mod 55），再让3与55接近，式子两边同时乘18，54x≡36（mod 55），又54=1×55-1，54模55余-1，有-x≡36（mod 55），式子两边乘-1，x≡-36（mod 55），取最小正整数19，当然也不一定找最小的正整数，只是为了和古代的孙子算经对应，里面找的就是最小正整数.下面就要算各总，各总就是将表格每一行里边的衍数、乘率、余数这3个数乘起来，它们依次为660×4×5=13200，385×1×3=1155，84×19×17=27132，答数就是把各数加起来得41487，最小答数就是用答数除以最小公倍数，求余数，41487÷4620=8……4527，最小答数为4527.

算出最小答数代回同余式组验证一下是否满足，如果在验证的过程中不满足某一个，说明该行可能算错了.经检验4527是最小答数，这就是孙子算经的算法.对于同余式组来说，要求出所有的解也是很容易的，所有的解为x=4527+4620k.我们在求最小答数的时候是去掉4620的若干倍，而所有的解是加上4620的若干倍.

4 结论

中国著名数学著作《孙子算经》中记载“物不知数”问题，就是孙子定理的体现，给出了求解一般同余式组的方法，成为解决特定一次同余式组的主要模式.文章对孙子定理进行了阐述，并通过实例对孙子定理问题的算法进行了详细的分析.但孙子定理也有一定缺陷，求解同余式、同余式组并不完善，有一定的局限性，要求模必须两两互素，且解法唯一.文章仅分析了一些简单的例子，以帮助学者更好地理解并掌握算法，相关问题有待进一步探讨.

【参考文献】

[1]潘承洞，潘承彪.初等数论（第二版）[M].北京：北京大学出版社，2003.

[2]闵嗣鹤，严士健.初等数论（第三版）[M].北京：高等教育出版社，2003.

[3]课程教材研究所，数学课程教材研究开发中心.初等数论 [M].北京：人民教育出版社，2006.

[4]胡典顺，徐汉文.初等数论（第二版）[M].科学出版社，2017.

[5]边红平.初等数论[M].浙江大学出版社，2007.

[6] 柯召，孙琦.数论讲义（第二版）[M].北京：高等教育出版社，2001.