中国剩余定理 中国剩余定理，又称孙子定理或中国余数定理，是数论中的一个关于一元线性同余方程组的定理，说明了一元线性同余方程组有解的准则以及求解方法。该定理在中国古代也被称为「韩信点兵」、「求一术」（宋 沈括）、「鬼谷算」（宋 周密）、「隔-{zh-cn:墙;zh-tw:墙;}-算」（宋 周密）、「剪管术」（宋 杨辉）、「秦王暗点兵」、「物不知数」等。 物不知数. 一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下： 有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？ 即，一个整数除以三-{zh-cn:余;zh-tw:余;}-二，除以五-{zh-cn:余;zh-tw:余;}-三，除以七-{zh-cn:余;zh-tw:余;}-二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。孙子没正式证明，但后来印度数学家及天文学家阿耶波多给出具体过程，彻底解决了此定理的任何给定实例。 最初对“物不知数”问题作出完整系统解答的是宋朝数学家秦九韶，载于1247年《数书九章》卷一、二《大衍类》中，从而使这一问题变为定理。明朝数学家程大位在《算法统宗》中将解法编成易于上口的《孙子歌诀》： 三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知 这个歌诀给出了模数为3、5、7时候的同余方程的秦九韶解法。意思是：将除以3得到的余数乘以70，将除以5得到的余数乘以21，将除以7得到的余数乘以15，全部加起来后再减去105或者105的整数倍，得到的数就是答案（除以105得到的余数则为最小答案）。比如说在以上的物不知数问题里面，使用以上的方法计算就得到 formula_1 因此按歌诀求出的结果就是23。 《数书九章》最初由伟烈亚力在19世纪初译为英文，而西方世界最早的完整系统解法由高斯在1801年提出。 形式描述. 用现代数学的语言来说明的话，中国剩余定理给出了以下的一元线性同余方程组： formula_2 有解的判定条件，并用构造法给出了在有解情况下解的具体形式。 中国剩余定理说明：假设整数"m"1, "m"2, ... , "m"n其中任两数互质，则对任意的整数："a"1, "a"2, ... , "a"n，方程组formula_3有解，并且通解可以用如下方式构造得到： 证明. 从假设可知，对任何formula_16，由于formula_17，所以formula_18 这说明存在整数formula_19使得formula_20 这样的formula_19叫做formula_6模formula_9的数论倒数。观察乘积formula_24可知： formula_25 formula_26 所以formula_27满足： formula_28 这说明formula_29就是方程组formula_3的一个解。 另外，假设formula_31和formula_32都是方程组formula_3的解，那么： formula_34 而formula_35两两互质，这说明formula_36整除formula_37. 所以方程组formula_3的任何两个解之间必然相差formula_13的整数倍。而另一方面，formula_27是一个解，同时所有形式为： formula_41 的整数也是方程组formula_3的解。所以方程组formula_3所有的解的集合就是： formula_44 例子. 使用中国剩余定理来求解上面的“物不知数”问题，便可以理解《孙子歌诀》中的数字含义。这里的线性同余方程组是： formula_45 三个模数 "m"1formula_463, "m"2formula_465, "m"3formula_467 的乘积是 "M"formula_46105，对应的 "M"1formula_4635, "M"2formula_4621, "M"3formula_4615. 而可以计算出相应的数论倒数："t"1formula_462, "t"2formula_461, "t"3formula_461. 所以《孙子歌诀》中的 70、21 和 15 其实是这个“物不知数”问题的基础解： formula_56 而将原方程组中的余数相应地乘到这三个基础解上，再加起来，其和就是原方程组的解： formula_57 这个和是 233，实际上原方程组的通解公式为： formula_58 《孙子算经》中实际上给出了最小正整数解，也就是 formula_59 时的解：formula_60。 交换环上的推广. 主理想整环. 设R是一个主理想整环，m1, m2, ... , mk是其中的k个元素，并且两两互质。令Mformula_46m1m2...mn为这些元素的乘积，那么可以定义一个从商环R/"M"R映射到环乘积R/"m"1R × … × R/"m"kR的同态： formula_62 formula_63 并且formula_64是一个环同构。因此formula_64的逆映射也存在。而这个逆映射的构造方式就如同中国剩余定理构造一元线性同余方程组的解一样。由于mi和Miformula_46M/mi互质，所以存在"s"i和"t"i使得 formula_67 而映射 formula_68 formula_69 就是formula_64的逆映射。 formula_71也是一个主理想整环。将以上的R换成formula_71，就能得到中国剩余定理。因为 formula_73 一般的交换环. 设R是一个有单位元的交换环，"I"1, "I"2, ... , "I"k是为环formula_74的理想，并且当formula_75时，formula_76，则有典范的环同构： formula_77 formula_78 模不两两互质的同余式组. 模不两两互质的同余式组可化为模两两互质的同余式组，再用孙子定理直接求解。 84=22×3×7,160=25×5,63=32×7，由推广的孙子定理可得 formula_79 与 formula_80 同解。 解法 formula_80 formula_82 formula_83 formula_82 formula_85 formula_86以及formula_87 formula_88，取数论倒数formula_89 formula_90，因formula_91 ，故两边可同除以32， 取数论倒数formula_92 formula_93 formula_94 所以最小正整数解为formula_95，通解为formula_96。 注意求解过程中应先检查同余式组上是否存在矛盾，存在矛盾的同余式组无解。 formula_97