孙子定理

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

问物几何？简单点说就是，存在一个数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的。

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

是数论中一个重要定理。

又称中国余数定理。

一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。

问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。

《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。

问物几何？
即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。

《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

宋朝数学家秦九韶于1247年《数书九章》卷一、二《大衍类》对“物不知数”问题做出了完整系统的解答。

明朝数学家程大位将解法编成易于上口的《孙子歌诀》：
三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五使得知
这个歌诀给出了模数为3、5、7时候的同余方程的秦九韶解法。

意思是：将除以3得到的余数乘以70，将除以5得到的余数乘以21，将除以7得到的余数乘以15，全部加起来后除以105（或者105的倍数），得到的余数就是答案。

比如说在以上的物不知数问题里面，按歌诀求出的结果就是23。

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

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

比如说，有一堆东西，除以 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 呢？”大家又陷入了思考。

第13讲孙子定理第一关求被除数【知识点】1 .孙子定理的含义：也叫中国剩余定理.《孙子算经》中“物不知数”问题说：“今有物，不知其数，三三数之剩二，五五数∙∙之剩三，七七数之剩二，问物几何？”即被三除余二，被五除余三，被七除余二的最小整数.这个问题称作孙子问题，俗称韩信点兵.其正确解法叫做孙子剩余定理.2 .中国轲余定理的结论：令任意固定整数为M,当M/A余a,MZB余b,M/C余c,M/D余d,…，M/Z余Z时，这里的A,B,C,D,…，Z为除数，除数为任意自然数（如果为。

，没有任何意义，如果为1,在孙子定理中没有计算和探讨的价值，所以，不包括O和1）时；余数a,b,c,d,Z为自然整数时.1 .当命题正确时，在这些除数的最小公倍数内有解，有唯一的解，每一个最小公倍数内都有唯一的解；当命题错误时，在整个自然数范围内都无解.2 .当M在两个或两-个以上的除数的最小公倍数内时，这两个或两个以上的除数和余数可以定位M在最小公倍数内的具体位置，也就是M的大小.3 .正确的命题，指没有矛盾的命题：分别除以A,B,C,D,…，Z不同的余数组合个数=A,B,C,D,…，Z的最小公倍数二不同的余数组合的循环周期.【例1】有一个整数，除以3余数是2,除以5余数是3,除以7余数是4,这个数可能是多少？A.67B.73C.158D.22【答案】C【例2】一个自然数除以13余6,除以29余7,这个自然数最小是多少？【答案】123【例3】一个数除以4余3,•除以5余2,除以6余1,这个数最小是多少？【答案】7【例4】有一个数除以3余2,除以5余3,除以7余4,除以9余5.这个数至少是多少？【答案】158【例5】被4除余1,被5除余2,被6除余3的最小自然数是多少？【答案】57【例6】一个数被2,3,7除结果都余1,这个数最小是多少？【例7】被3除余2,被5除余4,被7除余4的最小自然数是多少？【答案】74【例8】一个数，它除以11余8,除以13余10,被3除余1,这个数最小是多少？【答案】283【例9】某数用6除余3,用7除余5,用8除余1,这个数最小是几？【答案】33【例10】一个数除以5余2,除以6余2,除以7余3,求能漏足这三个条件的最小自然数是多少？【答案】122【例11】一个自然数除以3余2,除以5余4,除以7余6,这个自然数最小是多少？【答案】104【例12】一个数能被3、5、7整除，若用11去除则余1,这个数最小是多少？【答案】210【例13】•筐橘子，三三数之余一，五五数之余四，七七数之余二，筐里最少有多少个橘子？【答案】79【例14】一堆糖.分给A、B、C三个班级的小朋友（每班人数互不相同），如果A班每人6颗，则多3颗；乙班每人7颗，则少3.颗；丙班每人8颗，则少7颗，问这堆糖至少有多少颗？【答案.】81【例15】有一筐苹果，甲班分，每人3个还剩11个；乙班分，每人4个还剩10个；丙班分，每人5个还剩12个.那么这筐苹果至少有多少个？【答案】62【例16】有一盒乒乓球，每次8个8个地数，10个10个地数，12个12个地数，最后总是剩下3个.这盒,乒乓球至少有多少个？【答案】123【例17】一筐苹果，如果按5个一堆放，最后多出3个.如果按6个一堆放，最后多出4个.如果按7个一堆放，还多出1个.这筐苹果至少有多少个？【答案】148【例18】五年级的学生排队做操，如果10人一行则余2人，如果12人一行则余4人，如果16人一行则余8人，那么五年级最少有多少人？【答案】232【例19】一个三位数被3除余1,被5除余3,被7除余5,这个数最大是多少？【答案】943【例20】设。

中国剩余定理一般指孙子定理。

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

是数论中一个重要定理。

又称中国余数定理。

一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。

问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。

《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。

问物几何？
即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。

《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

宋朝数学家秦九韶于1247年《数书九章》卷一、二《大衍类》对“物不知数”问题做出了完整系统的解答。

明朝数学家程大位将解法编成易于上口的《孙子歌诀》：
三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五使得知
这个歌诀给出了模数为3、5、7时候的同余方程的秦九韶解法。

意思是：将除以3得到的余数乘以70，将除以5得到的余数乘以21，将除以7得到的余数乘以15，全部加起来后除以105（或者105的倍数），得到的余数就是答案。

比如说在以上的物不知数问题里面，按歌诀求出的结果就是23。

中国剩余定理计算过程摘要：一、引言二、中国剩余定理的概念和基本原理三、中国剩余定理的算法实现四、中国剩余定理的应用案例五、结论正文：一、引言中国剩余定理，又称孙子定理，是我国古代数学家孙子提出的一个著名数学定理。

该定理指出，对于一组互素的正整数，给定任意整数k，若将这k 个整数分别除以这组正整数，所得的余数构成一个同余方程组，那么这个同余方程组必有解。

中国剩余定理在数学、密码学等领域有着广泛的应用，本文将详细介绍中国剩余定理的计算过程。

二、中国剩余定理的概念和基本原理中国剩余定理的定义：设有m 个正整数a1, a2,..., am，它们两两互素，即最大公约数为1。

给定任意整数k，将整数ki 分别除以这m 个正整数，所得的余数为r1, r2,..., rm。

若同余方程组：x ≡ r1 (mod a1)x ≡ r2 (mod a2)...x ≡ rm (mod am)有解，那么这个同余方程组必至少有一个解x 满足：0 ≤ x < a1 * a2 *...* am中国剩余定理的基本原理是基于数学的模运算和欧几里得算法。

通过模运算，可以将同余方程组转化为一个模某个正整数的方程组。

而欧几里得算法可以用来求解模某个正整数的方程组。

三、中国剩余定理的算法实现中国剩余定理的算法实现可以分为两个主要步骤：判断正整数是否两两互素和计算同余方程组的解。

1.判断正整数是否两两互素要判断正整数是否两两互素，可以使用辗转相除法。

对于给定的两个正整数a 和b，如果它们的最大公约数为1，则它们是互素的。

辗转相除法的基本原理是：两个整数的最大公约数等于其中较小的整数和两整数差的最大公约数。

通过不断用较小的整数去除两整数差，直到两整数差为1，就可以判断两个整数是否互素。

2.计算同余方程组的解计算同余方程组的解可以使用欧几里得算法。

欧几里得算法的基本思想是：对于两个整数a 和b，如果它们的最大公约数为d，则存在整数x 和y，使得ax + by = d。

“物不知数”——孙子定理有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二.问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数.《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理.孙子问题的解法，以现代的说法，是找出三个关键数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关键是找出70 21 15宋朝数学家秦九韶于1247年《数书九章》卷一、二《大衍类》对“物不知数”问题做出了完整系统的解答.明朝数学家程大位将解法编成易于上口的《孙子歌诀》：三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五使得知这个歌诀给出了模数为3、5、7时候的同余方程的秦九韶解法.意思是：将除以3得到的余数乘以70，将除以5得到的余数乘以21，将除以7得到的余数乘以15，全部加起来后减去105（或者105的倍数），得到的余数就是答案.比如说在以上的物不知数问题里面，按歌诀求出的结果就是23.又例今有一类数，除以3余数是2，除以5余数是3，除以7余数是4.试问这类数中最小的正整数是多少？35+63+60-105=5353第一步：在 5,7的公倍数中找出“除以3余数是2”的数；35第二步：在 3,7的公倍数中找出“除以5余数是3”的数；21,42, 63第三步：在 3,5的公倍数中找出“除以7余数是4”的数，15,30,45, 6035+63+60=158,158肯定是符合“除以3余数是2，除以5余数是3，除以7余数是4”的，但不一定最小，去掉若干个3,5,7的最小公倍数，使之变成最小的正整数。

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

是数论中一个重要定理。

又称中国剩余定理。

编辑本段内容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。

孙子定理的发展应用孙子定理又称中国剩余定理，是数论中非常重要的定理，是学习数论和近世代数的基础。

据此，论述了孙子定理的发展及其在赋值理论和密码学等方面的应用，给出了简单的证明。

标签：中国剩余定理；发展；应用doi：10.19311/ki.16723198.2017.30.074孙子定理又被称为中国剩余定理，是数论中的重要定理，在中国数学史上具有相当高的地位。

孙子定理给出了求解同余方程的一般方法，剩余问题在数论和近世代数中都有广泛的应用。

1孙子定理的发展我国古代就流传着许多传说，譬如“隔墙算”、“剪管术”、“物不知其数”、“韩信点兵”、“鬼谷算”等。

古代人民口口相传中的这些传说在现在看来就是一些趣味十足的数字游戏，它们的文字描述不尽相同，但所表达的数学意义是一致的，它们从不同的方面为我们列举出了“剩余问题”的解法。

这在我国古代的数学史上的影响非常大，孫子定理在密码学、多项式、赋值理论等方面也被广泛应用。

《孙子算经》是最早记录这类算法的书，十三世纪后期，数学家秦九韶在这方面取得了重大突破，他发现了一种新的算法，命名为“大衍求一术”。

古代流传着一首歌诀：“今有物，不知其数，三三数之，剩二；五五数之，剩三；七七数之，剩二”。

问物几何？歌诀的意思是：有批物品，三个为一组的数，剩余两个；五个为一组的数，剩余三个；七个为一组的数，剩余两个。

问这批物品有多少？我们将这首歌诀称为“物不知数”问题。

明代数学家程大位在《算法统宗》中如此描述：“三人同行七十稀，五树梅花廿一，七子团圆月正半，除百零五便得知”。

意为：把用3除所得的余数乘以70，加上用5除所得的余数乘以21，再加上用7除所得的余数乘以15，如果所得的数大于105，就减去105的倍数，即得所求的数。

用数学表达式解释为：2×7+3×21+2×15=233，233-105×2=23。

这是早期给出的同余方程组的解法。

下面介绍孙子定理的内容。

中国剩余定理【定理概述】 中国剩余定理（孙⼦定理）是中国古代求解⼀次同余式组的⽅法。

是数论中⼀个重要定理。

⼀元线性同余⽅程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙⼦算经》卷下第⼆⼗六题，叫做“物不知数”问题，原⽂如下：有物不知其数，三三数之剩⼆，五五数之剩三，七七数之剩⼆。

问物⼏何？即，⼀个整数除以三余⼆，除以五余三，除以七余⼆，求这个整数。

《孙⼦算经》中⾸次提到了同余⽅程组问题，以及以上具体问题的解法，因此在中⽂数学⽂献中也会将中国剩余定理称为孙⼦定理。

【求逆元】逆元的含义：模p意义下，1个数a如果有逆元x，那么除以a相当于乘以x。

ax≡1(mod p)。

⼀个数有逆元的充分必要条件是gcd(a,p)=1，此时逆元唯⼀存在，注意这⾥的唯⼀是指在群中唯⼀。

其实如果求出⼀个逆元x0，那么x0 + p*k都会满⾜上⾯的等式，但是我只取p内的正整数x0.【证明】由ax≡1(mod p)等价于这样⼀个⽅程a*x + p*y = 1 ，或者说这个⽅程x有解的话x必然满⾜ ax≡1(mod p)这个⽅程什么时候有解呢？很显然，当gcd(a,p) | 1时有解，所以gcd(a,p)只能是1，即a,p互质，证明完毕。

由此还可以得到⼀个结论，如果要求逆元，可以⽤扩展欧⼏⾥得求⼀组解（x,y），再求出x的最⼩正整数（x+p）%p,x就是a的唯⼀逆元。

⽅法1：费马⼩定理求逆元，p是，且gcd(a,p)=1在模为素数p的情况下，有费马⼩定理a p-1 ≡ 1（mod p）则a * a p-2 ≡ 1（mod p）所以a的逆元就是a p-2，⽤快速幂求即可。

#include<iostream>using namespace std;long long gcd(long long a, long long b){if(b == 0) return a;return gcd(b , a%b);}long long qPow(long long a ,long long n,long long mod){long long ans = 1;//如果n的⼆进制最后⼀位是1 结果参与运算//因为如果是0，那么幂运算之后该项是1,1乘任何数还是那个数，对结果不影响while(n > 0){if(n & 1)ans = (ans* a) % mod;a = (a*a) % mod;//底数加倍n >>= 1;//移位}return ans;}//long long invEle(long long a, long long mod){ //如果a 和模数不互质则必然不存在逆元if(gcd(a,mod) != 1 || mod < 2) return -1; return qPow(a,mod-2,mod);}int main(){long long a,b;int x,y;while(cin>>a>>b){cout<<invEle(a,b)<<endl;}}⽅法2：扩展欧⼏⾥得求逆元（⾼效）typedef long long ll;void extgcd(ll a,ll b,ll& d,ll& x,ll& y){if(!b){ d=a; x=1; y=0;}else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }}ll inverse(ll a,ll n){ll d,x,y;extgcd(a,n,d,x,y);return d==1?(x+n)%n:-1;}⽅法3：欧拉定理求逆元（很少⽤到）模p不是素数的时候需要⽤到欧拉定理逆元打表：typedef long long ll;const int N = 1e5 + 5;int inv[N];void inverse(int n, int p) {inv[1] = 1;for (int i=2; i<=n; ++i) {inv[i] = (ll) (p - p / i) * inv[p%i] % p;}}【解⽅程组】根据定理概述以及解法，得到以下⽅法int CRT(int a[],int m[],int n){int M = 1;int ans = 0;for(int i=1; i<=n; i++)M *= m[i];for(int i=1; i<=n; i++){int x, y;int Mi = M / m[i];extend_Euclid(Mi, m[i], x, y);ans = (ans + Mi * x * a[i]) % M;}if(ans < 0) ans += M;return ans;}【扩展中国剩余定理】当模数mi两两互质时有以上解法，当模数不确定是否两两互质呢？摘⾃博客:https:///acdreamers/article/details/8050018这种情况就采⽤两两合并的思想，假设要合并如下两个⽅程那么得到在利⽤扩展欧⼏⾥得算法解出的最⼩正整数解，再带⼊得到后合并为⼀个⽅程的结果为这样⼀直合并下去，最终可以求得同余⽅程组的解。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

"孙子定理"是数论中的一个重要定理，也叫做中国剩余定理（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分别换成新的余数就行了。

孙子定理学习的教育价值和意义
孙子定理是古代数学家孙子提出的一个定理，它是中国古代数学的重要组成部分，也是中国古代数学的重要组成部分。

孙子定理的学习对于学生来说具有重要的教育意义和价值。

首先，孙子定理的学习可以培养学生的抽象思维能力。

孙子定理是一个抽象的
数学定理，它要求学生从实际问题中抽象出抽象的概念，从而推导出定理。

这种抽象思维能力可以帮助学生更好地理解和掌握数学知识，并且可以帮助学生更好地应用数学知识解决实际问题。

其次，孙子定理的学习可以培养学生的逻辑思维能力。

孙子定理是一个比较复
杂的数学定理，它要求学生从一系列的数学公式中推导出定理，这就要求学生具备良好的逻辑思维能力。

这种逻辑思维能力可以帮助学生更好地理解和掌握数学知识，并且可以帮助学生更好地应用数学知识解决实际问题。

最后，孙子定理的学习可以培养学生的创新能力。

孙子定理是一个比较复杂的
数学定理，它要求学生从一系列的数学公式中推导出定理，这就要求学生具备良好的创新能力。

这种创新能力可以帮助学生更好地理解和掌握数学知识，并且可以帮助学生更好地应用数学知识解决实际问题。

总之，孙子定理的学习具有重要的教育意义和价值，它可以培养学生的抽象思
维能力、逻辑思维能力和创新能力，从而帮助学生更好地理解和掌握数学知识，并且可以帮助学生更好地应用数学知识解决实际问题。

孙子剩余定理
摘要：
一、孙子剩余定理的概念
二、孙子剩余定理的公式表示
三、孙子剩余定理的应用领域
四、我国对孙子剩余定理的研究与贡献
正文：
一、孙子剩余定理的概念
孙子剩余定理，又称孙子问题，是数论中一个有关同余方程组解的问题。

它是由我国古代数学家孙子（孙武）提出的一个著名数学问题，也是我国古代数学成就的一部分。

二、孙子剩余定理的公式表示
孙子剩余定理可以用以下公式表示：
a_1^m ≡ a_2^m (mod n)
a_1^n ≡ a_2^n (mod m)
其中，a_1、a_2为整数，m、n为正整数，且m、n互质。

三、孙子剩余定理的应用领域
孙子剩余定理在现代数学领域具有广泛的应用，尤其在密码学、计算机科学、通信技术等方面具有重要意义。

它在解决许多同余方程组问题、简化计算过程、提高计算效率等方面发挥着关键作用。

四、我国对孙子剩余定理的研究与贡献
作为孙子剩余定理的发源地，我国对这一定理的研究历史悠久，成果丰硕。

许多数学家为孙子剩余定理的发展作出了巨大贡献，如秦九韶、李冶、朱世杰等。

孙⼦定理孙⼦定理孙⼦定理，⼜称之为中国剩余定理（Chinese Remainder Theorem, CRT ）可以求解如下形式的⼀元线性同余⽅程组（其中n 1,n 2,…,n k 两两互质）。

x ≡a 1(mod n 1)x ≡a 2(mod n 2)⋮x ≡a k (mod n k )中国剩余定理说明：假设整数m 1,m 2,…,m n 两两互质，则对任意的整数：a 1,a 2,…,a n ，⽅程组有解，并且我们可以⽤如下⽅式构造得到：设M =m 1×m 2×⋯×m n =∏n i =1m i 是整数m 1,m 2,…,m n 的乘积，并设M i =M m i ,∀i ∈{1,2,3,…,n }是除了m i 以外的n −1个整数的乘积。

设t i 是M i 模m i 下的，则⽅程组的通解形式为：x =a 1t 1M 1+a 2t 2M 2+⋯+a n t n M n +kM =kM +∑n i =1a i t i M i ,k ∈Z 。

所以在模M 的意义下，⽅程组的只有⼀个解：x =(∑n i =1a i t i M i )(mod M )。

算法流程：1. 计算所有模数的积n ；(有的上⾯说计算它们的最⼩公倍数，其实都⼀样它们两两互质)2. 对于第i 个⽅程：1. 计算m i =nn i ;2. 计算m i 在模n i 意义下的逆元m −1i ；3. 计算C i =m i ×m −1i （不要对n i 取模）；3. ⽅程组的唯⼀解为：a =∑k i =1a i ×c i (mod n )。

下⾯我们来通过⼀道题，加深对孙⼦定理的运⽤现有两组数字，每组k 个，第⼀组中的数字分别⽤a 1,a 2,…,a k 表⽰，第⼆组中的数字分别⽤b 1,b 2,…,b k 表⽰。

其中第⼆组的数字是两两互素的。

求最⼩的n ∈N ，满⾜对于∀i ∈[i ,k ]，有b i |(n −a i )。

孙子定理的定义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．学会运用孙子定理解决一些具体问题。

3．掌握孙子定理的证明思想。

【学习重难点】重点：理解并掌握孙子定理。

难点：孙子定理的证明思想、孙子定理的应用。

【学习过程】一、新课学习知识点一：孙子定理。

在我国古代著名的数学著作《孙子算经》里提出了这样一个问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”“答曰：二十三。

”孙子给出解法：“术曰：三三数之剩二，置百四十；五五数之剩三，置六十三；七七数之剩二，置三十，并之，得二百三十三，以二百一十减之即得。

”所谓“孙子定理”，便是蕴涵在这解法中的数学原理。

根据前面的知识做一做：练习：1．孙子定理又称为_____。

2．三三数之剩二，五五数之剩三，七七数之剩二。

问物几何？知识点二：孙子定理的应用。

设12k m m m ，，，是两两互素的正整数，那么，对任意整数1k a a ，，，一次同余方程组()()mod 1j j x a m j k ≡，≤≤必有唯一解。

根据前面的知识做一做：练习：1．解同余方程。

()256490 60x x mod ++≡2．一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班有多少学生？二、课程总结1．这节课我们主要学习了哪些知识？2．它们在解题中具体怎么应用？三、习题检测1．一个数，除以5余1，除以3余2。

问这个数最小是多少？2．有兵一队，若列成五行纵队，则末行1人；若列成六行纵队，则末行5人；若列成七行纵队，则末行4人；若列成十一行纵队，则末行10人。

求兵数。

3．一个数被5除余2，被6除少2，被7除少3，这个数最小是多少？。