中国剩余定理(孙子问题)

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

问物几何？简单点说就是，存在一个数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.求解同余方程四、中国剩余定理的应用五、结论正文一、引言中国剩余定理，又称孙子定理，是我国古代数学家孙子提出的一个著名数学定理。

该定理描述了这样一个问题：已知一个整数被若干个正整数（除数）除，所得的余数都相同，求这个整数的最小值。

这个问题在古代被称为“物不知其数”，而中国剩余定理则给出了解决这个问题的方法。

二、中国剩余定理的概念和背景中国剩余定理的表述如下：设整数 a、b、c 分别为除数 d1、d2、d3 的余数，且 d1、d2、d3 两两互质，则存在整数 x、y、z 使得：ax ≡ 1 (mod d1)by ≡ 1 (mod d2)其中，x、y、z 为整数，且 x≥1，y≥1，z≥1。

中国剩余定理的背景可以追溯到古代数学家孙子提出的“物不知其数”问题。

孙子问题描述了这样一个情景：有三个牧羊人，他们分别放牧的三群羊总数相同，但每群羊的数量分别除以 3、5、7 的余数相同。

问：至少有多少只羊？三、中国剩余定理的证明过程为了证明中国剩余定理，我们可以采用两种方法：一种是基于数学归纳法和模运算的证明，另一种是基于鸽巢原理（中国剩余定理的另一种称呼）的证明。

1.求解模数首先，根据题意，我们需要求出除数 d1、d2、d3 的最小公倍数 d。

d 即为所求整数的模数。

2.求解余数根据题意，我们可以得到以下同余方程组：ax ≡ 1 (mod d1)by ≡ 1 (mod d2)cz ≡ 1 (mod d3)我们可以通过扩展欧几里得算法求解这个同余方程组，得到 x、y、z 的值。

3.构造同余方程根据求解得到的 x、y、z，我们可以构造如下同余方程：x = 1 + d1 * r1y = 1 + d2 * r2其中，r1、r2、r3 分别为 x、y、z 除以 d1、d2、d3 的余数。

中国剩余定理中国剩余定理：中国剩余定理（孙⼦定理）是⽤于解决⼀次同余⽅程组的⼀种⽅法。

定理的思路是将两个同余⽅程合为⼀个再下⼀个⽅程合并，最后得到答案。

那么先来看看对于两个⽅程的合并：x = a1(mod n1)x = a2(mod n2)将⽅程都转换为乘积与和的形式：x = n1 * T1+a1x = n2 * T2+a2将上述两式合并整理得：n1T1=(a2-a1)+n2T2设gcd(n1,n2) = d,c = a2 - a1,则合并的同余⽅程可变形为(n1/d)*T1 = (c/d)(mod n2/d)T1 =（c/d）*（n1/d)^-1(mod n2/d)不妨设S = （c/d）（n1/d)^-1,则T1=t(n2/d) + S,那么x = n1[t(n2/d)+S]+a1 = (n1n2/d) t + n1S+a1,即x = n1S+a1(mod n1n2/d)那么在带⼊求解时新的a3 = n1S + a1，n3 = n1n2/d,最终，其中最⼩的x就是最后剩余的⽅程的a(mod n)#include"iostream"using namespace std;typedef long long LL;LL r[1001],m[1001],N;LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}LL ex_gcd(LL a,LL b,LL &x,LL &y){if(b == 0){x = 1;y = 0;return a;}LL d = ex_gcd(b,a%b,x,y);LL t = x;x = y;y = t -(a/b)*y;return d;}LL Inv(LL a,LL b){LL d = gcd(a,b);if(d!=1)return -1;LL x,y;ex_gcd(a,b,x,y);return (x%b+b)%b;}bool megre(LL r1,LL m1,LL r2,LL m2,LL &r3,LL &m3){LL d = gcd(m1,m2);LL r = r2-r1;if(r%d)return 0;r = (r%m2+m2)%m2;m1/=d;m2/=d;r/=d;r*=Inv(m1,m2);r%=m2;r*=m1*d;r+=r1;m3 = m1*m2*d;r3 = (r%m3+m3)%m3;return 1;}LL CRT(){LL A1 = r[1],B1 = m[1];for(int i = 2;i <= N;i++){LL A2 = r[i],B2 = m[i];LL A3,B3;if(!megre(A1,B1,A2,B2,A3,B3))return -1;A1 = A3;B1 = B3;}return (A1%B1+B1)%B1;}int main(){cin >> N;for(int i = 1;i <= N;i++)cin >> m[i];for(int i = 1;i<= N;i++)cin >> r[i];cout <<CRT(); return 0;}。

中国剩余定理我国古代著名的数学书《孙子算经》中有这样一道名题“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物有几何？”此乃就是著名的“孙子问题”，俗称“韩信点兵”。

关于它的解法就是享誉国内外的“孙子定律”或“孙子定理”。

外国人称之为“中国剩余定理”。

一、“孙子定理”某数除以3余2，除以5余3，除以7余2。

这个数最小是多少？它的解题思路是：除以3余2的数要在5和7的公倍数数中去找。

5和7的最小公倍数是35.35÷3=11 (2)35符合除以3余2的条件。

除以5余3的数要在3和7的公倍数中去找，3和7的最小公倍数是21。

但21÷5=4 (1)条件要求是除以5余3，如果是21，余数只能是1，要满足余数是3的条件，就必须使被除数、除数、商、余数同时扩大3倍。

21×3=63则63÷5=12 (3)63符合除以5余3的条件。

除以7余2的数，要在3和5的公倍数中去找。

3和5的最小公倍数是15，条件要求除以7余2，如果是15，余数只能是1，要满足余数是2的条件，被除数、除数、商、余数，必须扩大2倍。

15×2=3030÷7=4 (2)30符合除以7余2的条件。

把1、2、3式的被除数和起来，35+63+30=128加得的结果128符合题目中所提的全部条件。

因为35加上的都是3的倍数，所以它们的和128，除以3的余数，不会改变；对63来讲，它所加上的数都是5的倍数。

因此，它们的和除以5的余数，也不会改变；对30来讲，它所加上的都是7的倍数，因此，它们的和除以7的余数，也不会改变。

由于3、5、7的最小公倍数是105，题目中要求的是满足条件的最小的数，因此128-105=23，这所得的差，除以3、5、7的余数也没变，所以23符合题目中所有条件的最小的一个数。

这就是著名的“孙子定理”，世界称之为“中国剩余定理”。

二、“变更被除数法”约定：将“N”分别除以n1,n2…nk所得的余数依次为r1、r2…rk。

行测技巧：速解中国剩余定理余数问题在行测考试中考察频率都非常高，而且以不同的形式考察，比如说对余数基本定义的考察，以及同余数特性题型的考察。

掌握好解余数问题的一些技巧，对考生来说至关重要。

今天主要来说说中国剩余定理的解题方法。

中国剩余定理有着千年的文化历史，早在春秋时期就出现过，是我国悠久历史的象征，中国剩余定理是一个大的数学体系，而今天主要是学习现有的公职类考试中常见题型的考察形式，以及解题方法。

一、什么是中国剩余定理：中国剩余定理最早出现在《孙子算经》中，又名物不知数问题。

今有物不知其数，三三数之剩二(除以3余2)，五五数之剩三(除以5余3)，七七数之剩二(除以7余2)，问物几何?”这个问题称为“孙子问题”，后经宋朝人传入西方，引起西方广大关注，以至于后来该问题的一般解法国际上称为“中国剩余定理”。

二、中国剩余定理的通用形式：M除以A得到余数a;M除以B得到余数b;M除以C得到余数c;求M为多少?三、中国剩余定理的解法:1.余同加余：M÷3 (1)M÷4 (1)当M除以不同的除数得到余数相同时，此时M的值为除数的最小公倍数的倍数加一，如下：M=12N+12.和同加和：M÷3 (2)M÷4 (1)当M除以不同的除数得到余数与除数的加和相同时，此时M的值为除数的最小公倍数的倍数加上余数与除数的相应的和，如下：M=12N+53. 差同减差：M÷5 (2)M÷4 (1)当M除以不同的除数得到除数与余数的差相同时，此时M的值为除数的最小公倍数的倍数减去除数与余数的差，如下：M=12N-34. 逐步满足法：根据条件从除数最小的式子用数逐步满足题目要求，试探的找出答案。

5. 带入排除法：将答案依次带到题目中，判断那个选项符合要求。

第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】设。

中国剩余定理一、中国剩余定理的由来原始问题 据记载最先来源于《孙子算经》中的题目：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？ 《孙子算经》中的解法：三三数之，取数七十，与余数二相乘；五五数之，取数二十一，与余数三相乘；七七数之，取数十五，与余数二相乘。

将诸乘积相加，然后减去一百零五的倍数。

我们就要问解法中的三个关键数70，21，15，如何来的，有何性质呢?为什么分别与余数2，3，2相乘呢？分析：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而得到最小的正数解，其中a 、b 、c 都是正整数，下同。

即题目的最小正整数答案为70×2+21×3+15×2=140+63+30=233233-2×105=23满足题目的所有答案为：70a+21b+15c-105n （n 为使结果为正数的整数，可正、负、为0）推广问题《孙子算经》中的题目几几数之剩几都是一个确定的数，而且是用三个数来数的。

假如用n 个数来数，每个数都是参数，余数也是参数，那么问题有解吗？有没有通解呢？我们可将问题变为有一个数除正整数i a 余正整数i R （i=1，2……k ），即(mod )i i N a R ，那么问题有解吗，有没有通解呢？中国古代求解一次同余式组（见同余）的方法。

是数论中一个重要定理。

又称中国剩余定理。

中国剩余定理的结论：令任意固定整数为M，当M/A余a，M/B余b，M/C余c，M/D余d，…，M/Z余z时，这里的A，B，C，D，…，Z为除数，除数为任意自然数（不包括0和1）时；余数a，b，c，d，z为自然整数时。

行测数量关系技巧：中国剩余定理行测数量关系技巧：中国剩余定理各位考生，很多同学在备考的过程中遇到中国剩余定理的题目除了代入排除这一种方法就有些不知所措，其实，中国剩余定理问题备考起来还是比较容易掌握的，下面就跟着来一块学习这部分的内容吧。

什么是中国剩余定理呢，中国剩余定理最早出现在《孙子算经》中，又名“物不知数问题”，有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何?即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。

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

中国剩余定理的通用形式是：M除以A得到余数a;除以B得到余数b;M除以C得到余数c;求M为多少?在其中也有一些特殊模型如下：一、余同加余，例如：M÷3…1，M÷4…1，则M=12n+1下面来看一个例题：例1. 一个大于10的正整数，除以3余2，除以4余2，除以5余2。

问这个数最小是多少?A.60B.61C.62D.63（答案）C。

解析：一个数M除以A得到余数a;除以B得到余数b;除以C得到余数c，求这个数的形式，符合中国剩余定理。

而且余数都为2，符合余同加余的模型。

这道题目当中符合题意的数应是3，4，5的公倍数加2，所有这样的数可表示为60n+2n为整数，因为这个数大于10，当n取1时，这个数最小为62。

选C。

二、差同减差，例如：M÷5…2，M÷4…1，则M=20n-3下面来看一个例题：例2.一个小于200的正整数P除以11余8，除以13余10，那么P是多少?A.139B.140C.141D.142（答案）B。

解析：这道题目是小于二百的数除以11余8，除以13余10，求这个数的形式，符合中国剩余定理。

11-8=3，13-10=3，除数与余数的差都为3，且11、13 的最小公倍数为143，根据差同减差可知，P=143n-3，那么在小于200的数中，P的值为140。

汉语余数定理，也称为汉语余数定理，是一个数论中关于一个变量的线性同余方程的定理，它解释了一个变量的线性同余方程的判据和解。

又称“孙子定理”，有“韩新兵”，“孙子定理”，“求术”（宋申国），“鬼谷计算”（宋周密），“隔墙”等古代名称。

计算”（宋周密），“切管”（宋阳辉），“秦王暗中战士”和“无数事物”。

一个变量的线性一致等式的问题最早可以在中国南北朝（公元5世纪）数学书《孙子书经》第26期中找到，这被称为“物是物”。

未知”。

原文如下：未知的事物，三到三个剩下两个，五到五个剩下三个，七到七个剩下两个。

问事物的几何形状？也就是说，将一个整数除以三分之二，五分之三和七分之二以找到该整数。

孙子的《佛经》首次提到了全等式问题和上述特定问题的解决方案。

因此，中国余数定理在中国数学文献中也将称为“孙子定理”。

1247年，宋代数学家秦久绍对“物不知数”问题给出了完整而系统的回答。

明代数学家程大为将解决方案汇编成《孙子的歌》，很容易赶上：三个人一起走了七十次，五棵树有二十一朵梅花，七个儿子团聚了半个半月。

除了一百零五，我们知道这首歌给出了秦绍的全同方程的模3、5和7的解。

意思是：将3除以70得到的余数，再乘以5除以得到的余数。

在图21中，将7除以15得到的余数相乘，将它们全部加起来并减去105或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。