2孙子定理

中国剩余定理（孙子定理）问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。

问物几何？简单点说就是，存在一个数x，除以3余2，除以5余三，除以7余二，然后求这个数。

上面给出了解法。

再明白这个解法的原理之前，需要先知道一下两个定理。

定理1：几个数相加，如果存在一个加数，不能被整数a整除，那么它们的和，就不能被整数a整除。

定理2：两数不能整除，若除数扩大（或缩小）了几倍，而被除数不变，则其商和余数也同时扩大（或缩小）相同的倍数（余数必小于除数）。

以上两个定理随便个例子即可证明！现给出求解该问题的具体步骤：1、求出最小公倍数lcm=3*5*7=1052、求各个数所对应的基础数（1）105÷3=3535÷3=11......2 //基础数35（2）105÷5=2121÷5=4 (1)定理2把1扩大3倍得到3，那么被除数也扩大3倍，得到21*3=63//基础数633、105÷7=1515÷7=2 (1)定理2把1扩大2倍得到2，那么被除数也扩大2倍，得到15*2=30//基础数30把得到的基础数加和（注意：基础数不一定就是正数）35+63+30=1284、减去最小公倍数lcm（在比最小公倍数大的情况下）x=128-105=23那么满足题意得最小的数就是23了。

一共有四个步骤。

下面详细解释每一步的原因。

（1）最小公倍数就不解释了，跳过（记住，这里讨论的都是两两互质的情况）（2）观察求每个数对应的基础数时候的步骤，比如第一个。

105÷3=35。

显然这个35是除了当前这个数不能整除以外都能够被其他数整除，就是其他数的最小公倍数。

相当于找到了最小的起始值，用它去除以3发现正好余2。

那么这个基础数就是35。

记住35的特征，可以整除其他数但是不能被3整除，并且余数是2。

体现的还不够明显，再看下5对应的基础数。

21是其他数的最小公倍数，但是不能被5整除，用21除以5得到的余数是1，而要求的数除以5应该是余1的。

中国剩余定理（孙⼦定理）详解问题：今有物不知其数，三三数之剩⼆，五五数之剩三，七七数之剩⼆。

问物⼏何？简单点说就是，存在⼀个数x，除以3余2，除以5余三，除以7余⼆，然后求这个数。

上⾯给出了解法。

再明⽩这个解法的原理之前，需要先知道⼀下两个定理。

定理1：两个数相加，如果存在⼀个加数，不能被整数a整除，那么它们的和，就不能被整数a整除。

定理2：两数不能整除，若除数扩⼤（或缩⼩）了⼏倍，⽽被除数不变，则其商和余数也同时扩⼤（或缩⼩）相同的倍数（余数必⼩于除数）。

以上两个定理随便个例⼦即可证明！现给出求解该问题的具体步骤：1、求出最⼩公倍数lcm=3*5*7=1052、求各个数所对应的基础数（1）105÷3=3535÷3=11......2 //基础数35（2）105÷5=2121÷5=4 (1)定理2把1扩⼤3倍得到3，那么被除数也扩⼤3倍，得到21*3=63//基础数633、105÷7=1515÷7=2 (1)定理2把1扩⼤2倍得到2，那么被除数也扩⼤2倍，得到15*2=30//基础数30把得到的基础数加和（注意：基础数不⼀定就是正数）35+63+30=1284、减去最⼩公倍数lcm（在⽐最⼩公倍数⼤的情况下）x=128-105=23那么满⾜题意得最⼩的数就是23了。

⼀共有四个步骤。

下⾯详细解释每⼀步的原因。

（1）最⼩公倍数就不解释了，跳过（记住，这⾥讨论的都是两两互质的情况）（2）观察求每个数对应的基础数时候的步骤，⽐如第⼀个。

105÷3=35。

显然这个35是除了当前这个数不能整除以外都能够被其他数整除，就是其他数的最⼩公倍数。

相当于找到了最⼩的起始值，⽤它去除以3发现正好余2。

那么这个基础数就是35。

记住35的特征，可以整除其他数但是不能被3整除，并且余数是2。

体现的还不够明显，再看下5对应的基础数。

21是其他数的最⼩公倍数，但是不能被5整除，⽤21除以5得到的余数是1，⽽要求的数除以5应该是余1的。

㊀㊀㊀㊀㊀１４６㊀详析孙子定理详析孙子定理Һ赵云平㊀（滇西科技师范学院数理学院，云南㊀临沧㊀６７７０９９）㊀㊀ʌ摘要ɔ孙子定理在各版本的初等数论教材中均有介绍，但细节不够明确，使读者在学习过程中产生很多疑问，本文在给出孙子定理的基础上，通过实例详细分析了孙子定理的算法，让更多的读者受益．ʌ关键词ɔ孙子定理；同余式；一次同余式组孙子定理在数论及近世代数学领域是非常重要的理论，起着基础作用，所解决的问题是求未知量的系数为１，模两两互质的一次同余式的解．它在国际上被称为中国剩余定理或中国余数定理，是数论中一个重要定理，定理的构造值得仔细推敲．求解一个未知数联立同余式组，通常应用 孙子定理 ，这是初等数论教材中介绍的主要算法．１㊀基本概念定义１［１］㊀给定一个正整数ｍ，把它叫作模．如果用ｍ去除任意两个整数ａ和ｂ，所得余数相同，称ａ与ｂ关于模ｍ同余，记作ａʉｂ（ｍｏｄｍ）．若余数不同，称ａ与ｂ关于模ｍ不同余，记作ａʂｂ（ｍｏｄｍ）．定义２［２］㊀设ｆ（ｘ）＝ａｎｘｎ＋ａｎ－１ｘｎ－１＋ ＋ａ０，其中ａｉ是整数，ｍ是一个正整数，就把ｆ（ｘ）＝ａｎｘｎ＋ａｎ－１ｘｎ－１＋ ＋ａ０ʉ０（ｍｏｄｍ）叫作模ｍ的同余式，ｎ就叫作这个同余式的次数．定理１［２］㊀一次同余式ａｘʉｂ（ｍｏｄｍ），当（ａ，ｍ）＝１时，有唯一解．定理２［２］㊀（ａ，ｂ）＝１⇔存在整数ｓ，ｔ，使ａｓ＋ｂｔ＝１．定理３（传递性）［４］㊀如果ａʉｂ（ｍｏｄｍ），ｂʉｃ（ｍｏｄｍ）⇒ａʉｃ（ｍｏｄｍ）．２㊀孙子定理定理４（孙子定理）［１－６］㊀设ｍ１，ｍ２， ，ｍｋ是ｋ个两两互质的正整数，Ｍ＝ｍ１ｍ２㊃ ㊃ｍｋ＝ᵑｋｉ＝１ｍｉ，Ｍｉ＝Ｍｍｉ，ｉ＝１，２， ，ｋ，则同余式组ｘʉｂ１（ｍｏｄｍ１），ｘʉｂ２（ｍｏｄｍ２）， ，ｘʉｂｋ（ｍｏｄｍｋ）的解是ｘʉＭᶄ１Ｍ１ｂ１＋Ｍᶄ２Ｍ２ｂ２＋ ＋ＭᶄｋＭｋｂｋ（ｍｏｄｍ），其中ＭｉᶄＭｉʉ１（ｍｏｄｍｉ），ｉ＝１，２， ，ｋ．列表如下：除数余数最小公倍数衍数乘率各总答数ｍ１ｂ１ｍ２ｂ２︙︙ｍｋｂｋｍ＝ｍ１㊃ｍ２㊃ ㊃ｍｋＭ１Ｍ１ᶄＭ１ᶄＭ１ｂ１Ｍ２Ｍ２ᶄＭ２ᶄＭ２ｂ２︙︙︙ＭｋＭｋᶄＭｋᶄＭｋｂｋｘʉðｋｉ＝１ＭｉᶄＭｉ㊃ｂｉ（ｍｏｄｍ）这个孙子定理就给出了求解一次同余式组的一般算法，这是关于模ｍ的运算．３㊀具体算法与实例这个方法具体是什么呢？来看几个例子．例１㊀求解同余式组ｘʉ１（ｍｏｄ３），ｘʉ－２（ｍｏｄ５），ｘʉ４（ｍｏｄ１１）．分析㊀把它列成一个表，大体上就是这样一个算法．除数余数最小公倍数衍数乘率各总答数最小答数３１５－２１１４３ˑ５ˑ１１＝１６５５ˑ１１＝５５１５５ˑ１ˑ１＝５５３ˑ１１＝３３２３３ˑ２ˑ（－２）＝－１３２３ˑ５＝１５３１５ˑ３ˑ４＝１８０５５＋（－１３２）＋１８０＝１０３１０３它有这样几项，除数㊁余数㊁最小公倍数㊁衍数㊁乘率㊁各总㊁答数，最后还可以求出最小答数．这里除数分成三个，除数分别是３，５，１１，余数分别是１，－２，４，衍数是什么呢？如果对应除数３，那就是另外两个除数相乘，那就是５ˑ１１，对应除数５的就是３ˑ１１，对应除数１１的就是３ˑ５；来看这个乘率，就是１，２，３，这个所谓乘率是什么呢？求乘率稍麻烦一点，就是让衍数５ˑ１１＝５５乘上ｘ关于模３余１的解，即５５ｘʉ１（ｍｏｄ３），这个式子的解怎么求？因为（５５，３）＝１，１｜１有解，实际上就是转化为求二元一次不定方程５５ｓ＋３ｔ＝１的解，这种方法过程不够简便，那这个一次同余式里边，怎么方便地求出ｘ呢？首先把５５除以３，商１８余１，所以５５ｘʉ１（ｍｏｄ３）就变成了ｘʉ１（ｍｏｄ３），这是因为５５ʉ１（ｍｏｄ３），又ｘʉｘ（ｍｏｄ３），有５５ｘʉｘ（ｍｏｄ３），又根据同余的传递性，所以ｘʉ１（ｍｏｄ３）；另一种处理同余式５５ｘʉ１（ｍｏｄ３）的方法，就是当模不是太大的时候，可以把小于模３的３个整数０，１，２分别代入同余式试一下，看谁满足，所以可以推出ｘʉ１（ｍｏｄ３），所以除数３对应的乘率是１．再看下一个３ˑ１１＝３３，３３ｘʉ１（ｍｏｄ５），把３３除以５，商６余３，所以３３ｘʉ１（ｍｏｄ５），就变成了３ｘʉ１（ｍｏｄ５），模５不是很大可把小于模５的整数０，１，２，３，４这５个整数分别代入，容易得出ｘʉ２（ｍｏｄ５），除此之外还有一种处理方式，就是想办法把ｘ的系数变成１，通过把ｘ的系数变到和模５越来越接近，比如５和４，６很接近，比如３ｘʉ１（ｍｏｄ５），两边乘上２，６ｘʉ２（ｍｏｄ５），又６ʉ１（ｍｏｄ５），所以６ｘʉｘ（ｍｏｄ５）⇒ｘʉ２（ｍｏｄ５），所以除数５对应的乘率是２，在解同余式的过程中根据具体题目多种方法融入使用更加简便．同样地，３ˑ５＝１５，１５ｘʉ１（ｍｏｄ１１），１５ʉ４（ｍｏｄ１１），得４ｘʉ１（ｍｏｄ１１），两边同乘３，１２ｘʉ３（ｍｏｄ１１），１２ʉ１（ｍｏｄ１１），所以ｘʉ３（ｍｏｄ㊀㊀㊀１４７㊀㊀１１），除数１１对应的乘率是３．然后是各总，各总是什么呢？各总就是衍数㊁乘率㊁余数的乘积，５５ˑ１ˑ１＝５５，３３ˑ２ˑ（－２）＝－１３２，１５ˑ３ˑ４＝１８０，答数就是５５＋（－１３２）＋１８０＝１０３，也就是各总之和，那么这个答数可能会比较大，而且大于最小公倍数，要求它是最小的正整数，则这个最小答数就是用答数除以最小公倍数求余数，或答数减去最小公倍数的倍数．算出最小答数代回同余式组验证一下是否满足，如果在验证的过程中不满足某一个，说明该行可能算错了，经检验１０３是最小答数，这是孙子定理的算法．对于同余式组来说，要求出所有的解，也是很容易的，刚才在求最小答数的时候是减去最小公倍数的若干倍，现在是加上１６５的若干倍，所有解ｘʉ１０３＋１６５ｋ，ｋɪＺ．解㊀ȵ３，５，１１两两互质，由孙子定理得ｍ＝３ˑ５ˑ１１＝１６５，Ｍ１＝５ˑ１１，５ˑ１１ˑＭᶄ１ʉ１（ｍｏｄ３），Ｍᶄ１＝１，Ｍ２＝３ˑ１１，３ˑ１１ˑＭᶄ２ʉ１（ｍｏｄ５），Ｍᶄ２＝２，Ｍ３＝３ˑ５，３ˑ５ˑＭᶄ３ʉ１（ｍｏｄ１１），Ｍᶄ３＝３，ʑｘʉ５ˑ１１ˑ１ˑ１＋３ˑ１１ˑ２ˑ（－２）＋３ˑ５ˑ３ˑ４（ｍｏｄ１６５）ʉ１０３（ｍｏｄ１６５）．例２㊀求解同余式组ｘʉ５（ｍｏｄ７），ｘʉ３（ｍｏｄ１２），ｘʉ１７（ｍｏｄ５５）．分析㊀要求这个同余式组，列表如下：除数余数最小公倍数衍数乘率各总答数最小答数７５１２３５５１７７ˑ１２ˑ５５＝４６２０１２ˑ５５＝６６０４１３２００７ˑ５５＝３８５１１１５５７ˑ１２＝８４９２７１３２１３２００＋１１５５＋２７１３２＝４１４８７４５２７其中乘率，求６６０ｘʉ１（ｍｏｄ７）的解，（６６０，７）＝１，１｜１有解，这个解怎么来求呢？实际上就是求６６０ｓ＋７ｔ＝１．来看怎么方便快捷地求出ｘ，首先我们把６６０除以７，商９４余２，所以６６０ｘʉ１（ｍｏｄ７）就变成了２ｘʉ１（ｍｏｄ７），为什么６６０可以写成被７除的余数２呢？因为６６０ʉ２（ｍｏｄ７），两边同乘ｘ，６６０ｘʉ２ｘ（ｍｏｄ７），要找６６０ｘʉ１（ｍｏｄ７），由同余的传递性，有２ｘʉ１（ｍｏｄ７）．所以由６６０ｘʉ１（ｍｏｄ７）就推出２ｘʉ１（ｍｏｄ７），那返回去怎么办呢？返回去实际上也是一样的，因为６６０ｘ与２ｘ同余，２ｘ与１同余，由传递性，所以６６０ｘ与１同余，因此６６０ｘʉ１（ｍｏｄ７）⇔２ｘʉ１（ｍｏｄ７），然后从２ｘʉ１（ｍｏｄ７）里边找ｘ，怎么找呢？因为（２，７）＝１，所以它只有１个解，现在我们要求２ｓ＋７ｔ＝１很容易．或当模不是太大的时候，我们也可以从０到６一个一个代进去试一下，看谁满足，所以可以推出ｘ＝４，因此除数７对应的乘率是４．在这里还有一种解法，就是想办法把ｘ的系数变成１，通过把ｘ的系数变到和７越来越接近，比如６和８与７很接近，比如在２ｘʉ１（ｍｏｄ７）两边乘上３，得６ｘʉ３（ｍｏｄ７），因６模７余－１，所以－ｘʉ３（ｍｏｄ７），两边乘－１，ｘʉ－３（ｍｏｄ７），－３被７除，因－３＝－１ˑ７＋４，找最小正整数，就是４，所以ｘ＝４，或者在式子２ｘʉ１（ｍｏｄ７）两边乘４，得８ｘʉ４（ｍｏｄ７），又８模７余１，ｘʉ４（ｍｏｄ７），所以得到的也是４，这是乘率．这个除数和余数根据同余式组可以直接写出来，最小公倍数的计算也简单．衍数呢？在除数里边，除了这一行所在的数，把其他几个除数乘起来便可．乘率稍稍麻烦一点，要把它们解出来，对于模７，４是第一个乘率．对于模１２的乘率，就是要找３８５ｘʉ１（ｍｏｄ１２）的解，现在我们还是按刚才的办法，３８５太大，把它变小，就是３８５被１２除找余数，３８５除以１２，商３２余１，原同余式等价于ｘʉ１（ｍｏｄ１２），所以１２对应的乘率为１，最后一个乘率，找８４ｘʉ１（ｍｏｄ５５）的解，当然我们还是用８４被５５除，来看它的余数，２９ｘʉ１（ｍｏｄ５５），下面我们再让它接近５５，然后再去掉５５的倍数，上式两边乘２，得５８ｘʉ２（ｍｏｄ５５），再模一个５５，得３ｘʉ２（ｍｏｄ５５），再让３与５５接近，式子两边同时乘１８，５４ｘʉ３６（ｍｏｄ５５），又５４＝１ˑ５５－１，５４模５５余－１，有－ｘʉ３６（ｍｏｄ５５），式子两边乘－１，ｘʉ－３６（ｍｏｄ５５），取最小正整数１９，当然也不一定找最小的正整数，只是为了和古代的孙子算经对应，里面找的就是最小正整数．下面就要算各总，各总就是将表格每一行里边的衍数㊁乘率㊁余数这３个数乘起来，它们依次为６６０ˑ４ˑ５＝１３２００，３８５ˑ１ˑ３＝１１５５，８４ˑ１９ˑ１７＝２７１３２，答数就是把各数加起来得４１４８７，最小答数就是用答数除以最小公倍数，求余数，４１４８７ː４６２０＝８ ４５２７，最小答数为４５２７．算出最小答数代回同余式组验证一下是否满足，如果在验证的过程中不满足某一个，说明该行可能算错了．经检验４５２７是最小答数，这就是孙子算经的算法．对于同余式组来说，要求出所有的解也是很容易的，所有的解为ｘ＝４５２７＋４６２０ｋ．我们在求最小答数的时候是去掉４６２０的若干倍，而所有的解是加上４６２０的若干倍．４㊀结论中国著名数学著作‘孙子算经“中记载 物不知数 问题，就是孙子定理的体现，给出了求解一般同余式组的方法，成为解决特定一次同余式组的主要模式．文章对孙子定理进行了阐述，并通过实例对孙子定理问题的算法进行了详细的分析．但孙子定理也有一定缺陷，求解同余式㊁同余式组并不完善，有一定的局限性，要求模必须两两互素，且解法唯一．文章仅分析了一些简单的例子，以帮助学者更好地理解并掌握算法，相关问题有待进一步探讨．ʌ参考文献ɔ［１］潘承洞，潘承彪．初等数论（第二版）［Ｍ］．北京：北京大学出版社，２００３．［２］闵嗣鹤，严士健．初等数论（第三版）［Ｍ］．北京：高等教育出版社，２００３．［３］课程教材研究所，数学课程教材研究开发中心．初等数论［Ｍ］．北京：人民教育出版社，２００６．［４］胡典顺，徐汉文．初等数论（第二版）［Ｍ］．科学出版社，２０１７．［５］边红平．初等数论［Ｍ］．浙江大学出版社，２００７．［６］柯召，孙琦．数论讲义（第二版）［Ｍ］．北京：高等教育出版社，２００１．。

孙子定理解同余方程组（最新版）目录1.同余方程组的概念及孙子定理的背景2.孙子定理的概述3.同余方程组的求解方法4.中国剩余定理的证明5.孙子定理的应用及意义正文一、同余方程组的概念及孙子定理的背景同余方程组是数论中的一个重要概念，它是指一组包含多个同余方程的方程组。

例如，"物不知数"问题就是一道典型的同余方程组问题。

中国古代数学家孙子在《孙子算经》中提出了著名的"物不知数"问题，从而引出了同余方程组和孙子定理的研究。

二、孙子定理的概述孙子定理，又称中国剩余定理，是数论中的一个重要定理。

它是指对于一个同余方程组，如果其中某一个方程的解已知，则可以求出其他所有方程的解。

这个定理在我国古代数学中被誉为"孙子定理"，是中国古代数学的一项重要成果。

三、同余方程组的求解方法同余方程组的求解方法主要有两种，一种是基于孙子定理的解法，另一种是基于代数的解法。

基于孙子定理的解法是先求出其中一个方程的解，然后利用孙子定理求出其他方程的解。

而基于代数的解法则是利用代数的方法，通过一系列的运算和推导，求出同余方程组的解。

四、中国剩余定理的证明中国剩余定理的证明是基于数学归纳法的。

首先，对于一个简单的同余方程组，可以通过直接求解得到它的解。

然后，假设对于任意的 n-1 个同余方程，都可以通过孙子定理求出它的解，接下来需要证明当有 n 个同余方程时，也可以通过孙子定理求出它的解。

五、孙子定理的应用及意义孙子定理在数学中有着广泛的应用，它不仅被用于解决同余方程组问题，还被用于解决代数方程组、数论问题等领域。

同余（九）——孙子定理（中国剩余定理）往期文章同余（一）同余（二）同余（三）同余（四）—书籍书号的小秘密同余（五）——费马小定理同余（六）——斐波那契数列同余（七）——密码学中的应用同余（八）——欧拉定理整数与整除问题导读孙子定理是中国古代求解一次同余式组的方法。

是数论中四大定理之一。

又称中国剩余定理。

在数学著作《孙子算经》中，提到一个“物不知数”问题，原文如下：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。

问物几何？孙子算经《孙子算经》的作者生平和编写年不详，一般认为是东晋时期的作品，比孙武的《孙子兵法》要晚很多。

用我们现在学习的数学语言来描述“物不知数”问题：算经中给出答案是23，23是满足同余方程组的最小正整数。

并给出了上述问题的一般解法。

宋代数学家秦九韶在其名著《数书九章》中考虑了更一般化同余方程组的解法。

最终他得到了下面的定理。

孙子定理定理假设整数m1,m2, ... ,m n两两互质，则对任意的整数：a1,a2, ... ,a n,上述同余方程组有唯一解。

其中证明从假设可知，（m i,M i）=1，故存在整数使得另一方面，对i≠j , m j|M i, 因此所以满足又若x1,x2,是方程组的两个解，则x1≡x2（mod m i）1≤i≤n考虑到（m i,m j）=1(i≠j), 即可知x1≡x2（mod m）所以解是唯一的。

□定理应用例子1（韩信点兵）有兵一队，若列成5行纵队，则末行1人；成6行纵队，则末行5人；成7行纵队，则末行4人；成11行纵队，则末行10人，求兵数？解此时m=5×6×7×11=2310M1=462，M2=385，M3=330，M4=210.解得到t1=3，t2=t3=t4=1,, 在根据定理得到x≡2111（mod 2310）. 注：这个例子说明，在秦朝末年时期，就有了孙子定理的特例。

定理故事孙子定理是中国古代数学史上最值得骄傲的结论，国内外每一本数论书中都有此定理。

孙子定理公式孙子定理，又称中国剩余定理，这可是数学世界里一颗璀璨的明珠！咱先来说说啥是孙子定理。

简单来讲，就是在解决一类同余式组问题时的超级神器。

比如说，有一堆东西，除以 3 余 2，除以 5 余 3，除以 7 余 2，问这堆东西最少有多少？这时候孙子定理就派上用场啦。

那孙子定理的公式是啥样呢？咱来瞧瞧。

设 m1, m2,..., mk 是两两互质的正整数，M = m1 × m2 ×... × mk，Mi = M / mi ，ti 是满足Mi × ti ≡1 (mod mi) 的整数，则同余式组x ≡ a1 (mod m1) ，x ≡ a2 (modm2) ，... ，x ≡ ak (mod mk) 的解为x ≡ a1 × M1 × t1 + a2 × M2 × t2 +... + ak × Mk × tk (mod M) 。

是不是有点晕乎？别着急，我给您举个例子就清楚了。

有一天，我在课堂上讲这个孙子定理。

我问同学们：“假设一堆苹果，除以 5 余 2，除以 7 余 3，那最少有多少个苹果呀？”这时候，教室里安静得连根针掉地上都能听见。

大家都皱着眉头，苦思冥想。

我看着他们的样子，心里也有点着急。

不过我还是耐着性子，一步一步引导他们。

“咱们先算算 M 是多少呀？5×7=35，所以 M 就是 35。

那 M1 呢？就是 35÷5 = 7，M2 就是 35÷7 = 5。

接下来，咱们要找到满足7×t1 ≡ 1 (mod 5) 和5×t2 ≡ 1 (mod 7) 的 t1 和 t2 。

”这时候，有个平时挺机灵的同学小声说：“老师，t1 是不是 3 啊？因为 7×3 = 21，21 除以 5 余 1 。

”我一听，特别高兴，赶紧表扬他：“对啦，真聪明！那 t2 呢？”大家又陷入了思考。

§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）的解。

孙子定理的定义1. 引言孙子定理是数学中一个重要的几何定理，它与三角形的边长和角度之间的关系密切相关。

孙子定理起源于中国古代数学家孙子，被广泛应用于解决三角形相关问题。

2. 孙子定理的表述孙子定理可以通过以下方式表述：对于一个任意三角形ABC，其边长分别为a、b、c，对应的内角分别为A、B、C。

那么，可以得到以下等式关系：a/sinA = b/sinB = c/sinC3. 推导过程现在我们来推导一下孙子定理。

首先，根据正弦定理，我们可以得到以下等式：sinA/a = sinB/b = sinC/c将等式两边取倒数，并且交换分子和分母位置，得到：a/sinA = b/sinB = c/sinC这就是孙子定理的表述。

4. 孙子定理的应用孙子定理在解决三角形相关问题时非常有用。

下面我们将介绍一些常见的应用场景。

4.1 求解缺失边长或角度当我们已知一个三角形的两个边长和它们夹角的情况下，可以使用孙子定理来求解第三边的长度。

例如，已知一个三角形的边长a=5，b=7，夹角C=60°。

我们可以通过孙子定理来求解边长c。

根据孙子定理，我们有：c/sinC = a/sinA代入已知数据：c/sin60° = 5/sinA通过简单计算，我们可以得到sinA = (5/7) * sin60°。

然后，通过反正弦函数计算得到A的值。

最后，再利用三角函数关系求解出c的值。

4.2 判断三角形类型孙子定理也可以用于判断三角形的类型。

根据孙子定理中等式两边之间的比例关系，我们可以得到以下结论：•如果a=b=c，则三角形为等边三角形。

•如果a=b或b=c或c=a，则三角形为等腰三角形。

•如果a^2 + b^2 = c^2，则三角形为直角三角形。

•如果a^2 + b^2 < c^2，则三角形为钝角三角形。

•如果a^2 + b^2 > c^2，则三角形为锐角三角形。

4.3 解决几何问题除了上述应用外，孙子定理还能够帮助我们解决其他几何问题。

中国剩余定理（孙子定理）定义中国古代求解一次同余式组（见同余）的方法。

是数论中一个重要定理。

又称中国剩余定理。

编辑本段内容1、分别找出能任两个数整除，而满足被第三个整除余几的数。

2、将三个未知数加起来，减去这三个数的最小公倍数的整数倍。

N≡R1(mod d1) ≡R2(mod d2)≡R3(mod d3)则N=k1d2d3R1+k2d1d3R2+k3d1d2R3±d1d2d3P其中P为任意非负整数k1是满足k1d2d3≡1(mod d1)的最小正整数k2是满足k2d1d3≡1(mod d2)的最小正整数k3是满足k3d1d2≡1(mod d3)的最小正整数编辑本段解法解法中的三个关键数70，21，15，有何妙用，有何性质呢?首先70是3除余1而5与7都除得尽的数，所以70a是3除余a,而5与7都除得尽的数，21是5除余1，而3与7都除得尽的数，所以21b是5除余b，而3与7除得尽的数。

同理，15c是7除余c，3与5除得尽的数，总加起来 70a+21b+15c 是3除余a，5除余b ，7除余c的数，也就是可能答案之一，但可能不是最小的，这数加减105(105=3*5*7)仍有这样性质，可以多次减去105而得到最小的正数解。

附：如70，其实是要找余2的，但只要找到了余1的再乘2即余二了。

孙子问题的解法，以现代的说法，是找出三个关键数70，21，15。

解法的意思就是用70乘3除所得的余数，21乘5除所得的余数，15乘7除所得的余数，然后总加起来，除以105的余数就是答案。

即题目的答案为70×2+21×3+15×2=140+63+30=233233-2×105=23公式：70a+21b+15c-105n题中有三个数，分别为3、5、7，5*7/3余数为2，取35；3*7/5余数为1，要使余数为3，只需将3*7扩大3倍变成63即可；同样3*5/7的余数为1，要使余数为2，则将3*5扩大2倍，变成30。

孙子定理公式详解孙子定理，也称为中国剩余定理，是数论中的一个重要定理。

这定理听起来是不是有点高大上，让人感觉摸不着头脑？别担心，咱一步步来把它弄明白。

先来说说孙子定理到底是个啥。

想象一下，你有一堆苹果，要分给几个小伙伴。

但是呢，你只知道这些苹果除以某个数会余几，除以另一个数又会余几，然后你想知道到底有多少个苹果。

这时候孙子定理就派上用场啦！比如说，有一堆物品，除以 3 余 2，除以 5 余 3，除以 7 余 2，那这堆物品最少有多少个？这就是孙子定理能解决的问题。

咱们来看看孙子定理的公式。

假设整数 m1，m2，... ，mk 两两互质，M = m1 × m2 ×... × mk，Mi = M / mi（i = 1，2，... ，k），则同余方程组：x ≡ a1（mod m1）x ≡ a2（mod m2）...x ≡ ak（mod mk）的解为：x = （a1M1y1 + a2M2y2 +... + akMkyk）mod M ，其中 yi满足Miyi ≡ 1 （mod mi）（i = 1，2，... ，k）。

哎呀，这公式是不是看起来有点复杂？别着急，咱们通过一个具体的例子来理解。

就拿前面说的那堆物品的例子，除以 3 余 2，除以 5 余 3，除以 7余 2。

首先，3、5、7 两两互质，M = 3×5×7 = 105。

M1 = 105÷3 = 35，M2 = 105÷5 = 21，M3 = 105÷7 = 15。

接下来要找 y1、y2、y3，使得35y1 ≡ 1 （mod 3），21y2 ≡ 1（mod 5），15y3 ≡ 1 （mod 7）。

对于35y1 ≡ 1 （mod 3），因为 35 = 3×11 + 2，2×2 ≡ 1 （mod 3），所以 y1 = 2。

对于21y2 ≡ 1 （mod 5），因为 21 = 5×4 + 1，所以 y2 = 1。

【中国剩余定理（孙⼦定理）】中国剩余定理，⼜称孙⼦定理（什么名字啊）是中国古代求解⼀次同余式组（见同余）的⽅法。

是数论中⼀个重要定理。

⾸先来⼀个⼩！例！题！吧！注释：三数为a b c，余数分别为 m1 m2 m3，%为求今年余计算，&&是“且”运算。

1、分别找出能被两个数整除，⽽满⾜被第三个整除余⼀的最⼩的数。

k1%b==k1%c==0 && k1%a==1;k2%a==k2%c==0 && k2%b==1;k3%a==k3%b==0 && k3%c==1;2、将三个未知数乘对应数字的余数再加起来，减去这三个数的最⼩公倍数的整数倍即得结果。

Answer = k1×m1 + k2×m2 + k3×m3 - P×(a×b×c);P为满⾜Answer > 0的最⼤整数；或者 Answer = (k1×m1 + k2×m2 + k3×m3)%(a×b×c) ;我们来⼩⼩的证明⼀波　设M=m1*m2*......*mn Mi=M/mi 设Mi的逆元为Mi^(-1)(mod mi) 有Mi*Mi^(-1)≡1(mod mi) ai*Mi*Mi^(-1)≡ai(mod mi) 对于所有的j不等于i ai*Mi*Mi^(-1)≡0(mod mj) 所以答案就是所有ai*Mi*Mi^(-1)（mod p）的值1 #include<bits/stdc++.h>2using namespace std;3long long x,y;4long long a[15],b[15];5long long n;6void exgcd(long long A,long long B)7{8if(B==0)9 {10 x=1;11 y=0;12return;13 }14 exgcd(B,A%B);15long long z=x;16 x=y;17 y=z-(A/B)*y;18}19long long fast(long long a1,long long b1,long long mod)20{21long long ans=0;22 a1%=mod;23 b1%=mod;24while(b1)25 {26if(b1&1)27 {28 ans=(ans+a1)%mod;29 }30 b1>>=1;31 a1=(a1+a1)%mod;32 }33return ans;34}35long long china()36{37long long ans=0;38long long M=1;39for(long long i=1;i<=n;i++)40 M*=b[i];41for(long long i=1;i<=n;i++)42 {43long long m=M/b[i];44 exgcd(m,b[i]);45while(x<0)46 x+=b[i];47 x%=b[i];48 ans=(ans+fast(x,fast(m,(a[i]+M)%M,M),M)+M)%M;49 }50return ans;51}52int main()53{54 cin>>n;55for(long long i=1;i<=n;i++)56 {57 scanf("%lld",&a[i]);58 }59for(long long i=1;i<=n;i++)60 {61 scanf("%lld",&b[i]);62 }63 cout<<china();64return0;65 }。

孙子定理的探讨与应用
孙子定理又叫孙子康复定理，是由中国古代数学家孙子的《九章算术》中提出来的一条定理，也是中国古代数学的标志性理论，孙子定理是“水平分割叉形”的形象表示，说明“三角形端点相接时，最大边的长度平方等于左右两条斜边的平方和”。

孙子定理有着极强的实用性，被广泛用于早期测量距离和计算面积等日常工作中。

比如在鱼雷发射计算时，海军司令部可以以此定理计算出发射和收回路径的最短路程，从而使得鱼雷的使用更加有效。

在登山或做飞机模型玩具时，人们可以用孙子定理来计算出最合适的几何形状，从而使得整个结构更加牢固。

除此之外，孙子定理还在日常教学中发挥作用。

学生们可以通过实际操作来学习孙子定理，比如可以利用纸片切割出叉形，然后通过相接三角形端点来验证孙子定理是否正确。

另外，学生们也可以利用信息技术来帮助计算，从而更好地理解孙子定理的实质及其应用。

总之，孙子定理有着深远的历史也是备受尊敬的一项定理，但孙子定理不仅仅是一个历史纪念，它仍在日常生活中发挥重要作用，并且有着更新现代应用。

孙子定理高斯定理
孙子定理和高斯定理是数学中的两个定理，分别用于解决几何问题和物理问题。

1. 孙子定理（也称为圆周角定理）：它是几何中的一个重要定理，用于计算三角形的三个内角和。

该定理表明，任意三角形的三个内角和等于180度（或π弧度）。

具体公式为：α + β + γ = 180°（或π rad），其中α、β、γ分别表示三角形的三个内角。

2. 高斯定理（也称为散度定理）：它是物理学中的一个重要定理，描述了矢量场在闭合曲面上的流出和流入之间的关系。

根据高斯定理，对于一个闭合曲面S，通过该曲面的矢量场的流出量等于该矢量场在曲面内部的散度的体积分。

具体公式为：∮S F·dA = ∭V (∇·F) dV，其中S表示闭合曲面，F表示矢量场，dA表示曲面微元面积，dV 表示体积微元，∮表示曲面积分，∭表示体积积分，∇·表示散度运算。

这两个定理在几何和物理领域有广泛的应用，能够帮助我们解决各种相关问题。

简述孙子定理
孙子定理是中国古代数学家孙子提出的一个定理，它是中国古代数学史上最重要的定理之一。

孙子定理指出，在一个三角形中，如果一条边的长度是另外两条边的和，那么这个三
角形的内角之和等于180度。

孙子定理的历史可以追溯到公元前3世纪，当时孙子在《九章算术》中提出了这个定理。

孙子定理的推导是基于古希腊数学家几何学家赫拉克利特的定理，即在一个三角形中，如果一条边的长度是另外两条边的积，那么这个三角形的内角之和等于120度。

孙子定理的推导是基于这个定理，他把赫拉克利特的定理推广到一般的三角形，即在一个三角形中，
如果一条边的长度是另外两条边的和，那么这个三角形的内角之和等于180度。

孙子定理的推导是基于几何学的基本原理，即三角形的内角之和等于180度。

孙子定理的推导过程是：首先，假设一个三角形ABC，其中AB=BC+AC，即一条边的长度是另外两条边的和；然后，画出一个辅助线，使得辅助线与边AB和边BC形成一个直角三角形；最后，根据直角三角形的内角之和等于180度的原理，可以得出三角形ABC的内角之和也
等于180度。

孙子定理是中国古代数学史上最重要的定理之一，它的推导过程是基于几何学的基本原理，即三角形的内角之和等于180度。

孙子定理的推导过程简单明了，但它的结论却是深刻的，它为数学家们提供了一种新的思路，为后来的数学发展奠定了基础。

孙子定理简单理解
孙子定理可以说是初中数学中的重要定理之一，它是一个用于计
算三角形面积的公式，也叫做海伦公式。

它的应用范围广泛，可以在
建筑、地理测量、物理等多个领域中找到它的踪迹。

所谓的孙子定理，是由中国古代著名军事家孙武所提出的，因此
得名。

这个公式可以用来快速地计算出三角形的面积，而无需准确地
测量三角形的边长和高度等参数。

因此，在进行一些基本的测量时，
孙子定理能够为我们节省很多时间和成本。

孙子定理的公式如下：S = √p(p - a)(p - b)(p - c)。

其中，S
代表三角形的面积，p表示半周长，即p = (a + b + c) / 2，而a、b、c则分别代表三角形的三条边长。

从公式中可以看出，孙子定理的精髓就在于能够快速算出半周长p 以及三角形的三边长。

通过使用计算器或手算，我们可以简单地使用
这个公式来计算出一个任意三角形的面积。

然而，在实际应用中，我们还需要掌握一些技巧性的计算方法，
才能充分利用好孙子定理。

例如，当我们只知道三角形的三个顶点坐
标时，如何用孙子定理来计算出它的面积呢？
我们可以通过勾股定理计算出三条边的长度，然后代入孙子定理
公式中得出面积。

计算出三条边长之后，我们还可以应用海伦公式求
解三角形高度，或是运用余弦定理求解角度等进一步问题。

总之，孙子定理虽然看似简单，但在实际运用中需要综合运用多个定理和技巧。

只有学好了三角形相关的数学知识和技巧，才能为我们在实际生活和工作中提供帮助，让我们更好地应对复杂的问题。

中国剩余定理（孙⼦定理） 中国剩余定理，也叫孙⼦定理，是数论中的⼜⼀个重要定理，那么它是⼲什么⽤的呢？简单来说，这是⼀个⽤来求⼀元线性同余⽅程组的定理。

叫做孙⼦定理的原因就是该定理最早可见于南北朝时期的著作《孙⼦算经》卷下第⼆⼗六题，叫做“物不知数”问题，原⽂如下： 有物不知其数，三三数之剩⼆，五五数之剩三，七七数之剩⼆。

问物⼏何？ 翻译⼀下，就是说，⼀个数除以三余⼆，除以五余三，除以七余⼆，求这个整数。

接下来，我们把这⼀道题作为例题，探究⼀下如何利⽤孙⼦定理搞定同余⽅程组例1： 求解⼀元线性同余⽅程组： x ≡ 2 ( mod 3 ) x ≡ 3 ( mod 5 ) x ≡ 2 ( mod 7 ) 解： 做题依据： 当p1 , p2 , ……互质的时候，有 x ≡（a1 q1 q1-1+ a2 q2 q2-1+……）mod P 其中P = p1 p2……， q i = p / p i ，q i-1为 q i 在模p i 意义下的逆元 对于这道题，x ≡（2 * 35 * 2 + 3 * 21 * 1+ 2 * 15 * 1）mod 105 = 23例2： 求解⼀元线性同余⽅程组： x ≡ 3（mod 12） x ≡ 2（mod 18） 解： 做题依据 当p不互质时，有x ≡ a1 ( mod p1 ) = = > x = a1 + p1 b1, x ≡ a2 ( mod p2 ) = = > x = a2 + p2 b2 所以p1 b1 - p2 b2 = a2 - a1 ⽤扩展欧⼏⾥得得解 因此不断合并⽅程即可2019-04-09 11:39:10。

"孙子定理"是数论中的一个重要定理，也叫做中国剩余定理（Chinese Remainder Theorem，CRT）。

它涉及到模同余方程组的解法，特别是在中国古代的数学发展中得以广泛应用，因此得名中国剩余定理。

这个定理在数论、密码学、编码等领域有重要的应用。

下面是孙子定理（中国剩余定理）的定义：
定理： 设n1, n2, ..., nk 是两两互质的正整数，a1, a2, ..., ak 是任意整数，那么对于给定的模数 n = n1 * n2 * ... * nk，存在一个整数 x，满足以下同余方程组：
x ≡ a1 (mod n1)
x ≡ a2 (mod n2)
...
x ≡ ak (mod nk)
换句话说，定理保证在给定的一系列两两互质的模数下，可以找到一个整数 x，使得 x 在每个模数下与给定的余数 ai 同余。

要注意的是，这个定理的前提是所涉及的模数两两互质。

如果模数之间不互质，这个定理就不一定成立。

孙子定理的应用范围很广，特别是在计算机科学领域，例如在密码学中的一些加密算法和解密算法，以及在编码和通信中的纠错码等技术中都有应用。

【关键字】精品孙子算经●“”《孙子算经》共三卷，完成于公元四-五世纪。

卷下第31题，是后世“”题的始祖，后来传到，变成“鹤龟算”。

书中是这样叙述的：“今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？这四句话的意思是：有若干只鸡兔同在一个笼子里，从上面数，有35个头；从下面数，有94只脚。

求笼中各有几只鸡和兔？趣题1：巍巍古寺在山林，不知寺内几多僧。

三百六十四只碗，看看用尽不差争。

三人共食一碗饭，四人共吃一碗羹。

请问先生明算者，算来寺内几多僧？●“荡杯问题”“今有妇人河上荡杯。

津吏问曰：‘杯何以多？’妇人曰：‘有客。

’津吏曰：‘客几何？’妇人曰：‘二人共饭，三人共羹，四人共肉，凡用杯六十五。

不知客几何？”“术曰：置六十五杯，以一十二乘之，得七百八十，以十三除之，即得”。

这里告诉我们这次洗碗事件，要处理的是65个碗共有多少人的问题。

其中有能了解客数的信息是2人共碗饭，3人共碗羹，4人共碗肉。

通过这几个数值，很自然就能解决客数问题。

因为客数是固定值，因此将其列成今式为N/2+N/3+N/4=65，易得客数六十人。

●“孙子定理”（中国剩余定理--一次同余论）《孙子算经》具有重大意义的是卷下第26题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：『二十三』”这个问题也被称为“物不知数”问题。

西方数学史将其称为“中国剩余定理”（Chinese remainder theorem）。

与上面的荡杯问题相比较，可以发现主要区别在于这里出现了余数，而不是整除。

此题相当于求大概方程组N=3x+2, N=5y+3, N=7z+2 ---三个方程式，4个未知数，比较难解。

孙子算经给出了算法：N=70×2+21×3+15×2－2×105=23。

这里105是模数3、5、7的最小公倍数。

这里给出的是符合条件的最小正整数。

对于一般余数的情形，只要把上述算法中的余数2、3、2分别换成新的余数就行了。