五年级数论：中国剩余定理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的。

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

问物几何？简单点说就是，存在一个数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世纪）数学书《孙子书经》第26期中找到，这被称为“物是物”。

未知”。

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

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

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

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

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

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

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

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

在图21中，将7除以15得到的余数相乘，将它们全部加起来并减去105或105的整数倍，得到的数字就是答案（除以105
得到的余数就是最小答案）。

例如，在上述事物数量未知的问题中，使用上述方法进行计算，根据民谣计算出的结果为23。

中国剩余定理的证明过程摘要：I.引言- 介绍中国剩余定理及其应用背景II.中国剩余定理的数学表述- 阐述中国剩余定理的数学公式及符号表示III.证明过程- 讲解证明中国剩余定理的关键思路和方法- step-by-step 详细阐述证明过程IV.结论- 总结中国剩余定理的证明过程及意义正文：I.引言中国剩余定理，又称孙子定理，是数论中一个重要的定理。

该定理可以帮助我们求解一类模线性方程组的问题，即在模素数p 的意义下，求解形如x_1 ≡ a_1 (mod p), x_2 ≡ a_2 (mod p), ..., x_n ≡ a_n (mod p) 的方程组。

中国剩余定理给出了一个比较简洁的解法，基本思想是将原方程组转化为模p 的同余方程的求解。

II.中国剩余定理的数学表述中国剩余定理的数学表述如下：设p_1, p_2, ..., p_n 是n 个互异的素数，a_1, a_2, ..., a_n 是在模p_i下余数为a_i 的整数（1 ≤ i ≤ n），那么对于任意整数x，同余方程组：x ≡ a_1 (mod p_1)x ≡ a_2 (mod p_2)...x ≡ a_n (mod p_n)有唯一解x ≡ a (mod p)，其中a 是满足以下条件的最小正整数：1.a ≡ a_1 (mod p_1)2.a ≡ a_2 (mod p_2)...3.a ≡ a_n (mod p_n)III.证明过程中国剩余定理的证明过程分为两个关键步骤：1.模p_i 的同余方程求解对于任意素数p_i，设x ≡ a_i (mod p_i)，则有x = a_i + p_i * k_i，其中k_i 是满足0 ≤ k_i < p_i-1 的整数。

2.求解模p 的同余方程根据上述结果，我们可以将原同余方程组转化为模p 的同余方程组：a_1 + p_1 * k_1 ≡ a (mod p)a_2 + p_2 * k_2 ≡ a (mod p)...a_n + p_n * k_n ≡ a (mod p)由于p_1, p_2, ..., p_n 是互异的素数，根据Chinese RemainderTheorem，这个同余方程组有唯一解。

中国剩余定理（crt）和扩展中国剩余定理（excrt）数论守门员⼆号 =。

=中国剩余定理：1.⼀次同余⽅程组：⼀次同余⽅程组是指形如x≡ai(mod mi) (i=1，2，…，k)的同余⽅程构成的组中国剩余定理的主要⽤途是解⼀次同余⽅程组，其中m1,m2,...,mk互质2.中国剩余定理：令M=m1*m2*...*mk（即所有m的lcm）ti为同余⽅程M/mi*ti≡1(mod mi)的最⼩正整数解则存在解x=∑ai*M/mi*ti通解为x+i*M最⼩⾮负整数解为(x%M+M)%M（我承认这段是抄的orz原⽂看起来更⽅便：）M/mi*ti≡1(mod mi)可转化为M/mi*ti+mi*y=1，然后⽤exgcd求ti其中gcd(M/mi, mi)=1，意义为⽅程组⼀定有解3.证明：对于第k个⽅程①当i≠k时，有mk|M/mi，即ai*M/mi*ti≡0(mod mk)②当i=k时，有M/mk*tk≡1(mod mk)，即ak*M/mk*tk≡ak(mod mk)故∑ai*M/mi*ti≡ak(mod mk)4.代码：（其中LL是long long，qcm是快速乘）1 LL crt(){2 LL bwl=0;3for(int i=1;i<=k;++i){4 LL x,y;5 exgcd(M/m[i],m[i],x,y);6if(x<0) x=x%m[i]+m[i];7 bwl=(bwl+qcm(qcm(a[i],M/m[i]),x))%M;8 }9return (bwl+M)%M;10 }View Code5.孙⼦算经：《孙⼦算经》：今有物不知其数，三三数之剩⼆；五五数之剩三；七七数之剩⼆。

问物⼏何？《算法统宗》：三⼈同⾏七⼗稀，五树梅花廿⼀枝，七⼦团圆⽉正半，除百零五便得知。

其中70=7*5*2，70%3=1，21=3*7*1，21%5=1，15（半个⽉）=3*5*1，15%7=1⽤70*2+21*3+15*2=233除3*5*7=105，得到的余数23即为答案70=3*5*2，21=3*7*1，15=3*5*1三式中的最后⼀个乘数2、1、1即为上⽂提到的di 数字还挺吉利的233扩展中国剩余定理：1.⼀次同余⽅程组：扩展中国剩余定理的主要⽤途是解⼀次同余⽅程组，其中m1,m2,...,mn不⼀定互质2.扩展中国剩余定理：令前k-1个⽅程组成的同余⽅程组的⼀个解为x且M为前k-1个模数的lcm则前k-1个⽅程的⽅程组的通解为x+i*M现在将第k个⽅程加⼊只需求⼀个正整数t，使得x+t*M≡ak(mod mk)可以转化为M*t+mk*y=ak-x然后⽤exgcd求出t若此⽅程⽆解，则整个同余⽅程组⽆解否则x+t*M为前k个⽅程的⽅程组的⼀个解（这段也是我抄的，原⽂和上边⼀样orz）3.代码：（其中LL是long long，qcm是快速乘，三个参数分别为两个乘数和模数）1 LL excrt(){2 LL M=m[1],ans=a[1];3for(int i=2;i<=k;++i){4 LL x,y;5 LL d=gcd(M,m[i]);6 LL c=(a[i]-ans%m[i]+m[i])%m[i];7if(c%d) return -1;8 exgcd(M,m[i],x,y);9 x=qcm(x,c/d,m[i]/d);10 ans+=qcm(x,M,M*m[i]);11 M*=m[i]/d;12 ans=(ans%M+M)%M;13 }14return ans;15 }View Code4.细节：1.有些题数字卡得严，必须要⽤快速乘2.快速乘时注意第⼆个乘数必须为正，要⽤通解处理3.每次快速乘的模数不⼀定⼀样，需要好好考虑例题：洛⾕3868 猜数字洛⾕4777 扩展中国剩余定理。

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

是数论中一个重要定理。

又称中国剩余定理。

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

韩信点兵韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝的建立了卓绝的功劳。

据说韩信的数学水平也非常高超，他在点兵的时候，为了保住军事机密，不让敌人知道自己部队的实力，先令士兵从1至3报数，然后记下最后一个士兵所报之数；再令士兵从１至５报数，也记下最后一个士兵所报之数；最后令士兵从1至7报数，又记下最后一个士兵所报之数；这样，他很快就算出了自己部队士兵的总人数，而敌人则始终无法弄清他的部队究竟有多少名士兵。

这个故事中所说的韩信点兵的计算方法，就是现在被称为“中国剩余定理”的一次同余式解法。

它是中国古代数学家的一项重大创造，在世界数学史上具有重要的地位。

我国古代数学名著《孙子算经》有这么一道题：今有物不知其数，三三数之，剩二；五五数之，剩三；七七数之，剩二。

问物几许？它的解法由明代数学家程大位用诗歌给予了解答：三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。

这种解法的意思是，把用3除所得的余数乘以70，加上用5除所得余数乘以21，再加上用7除所得余数乘以15，结果若比105大，就减去105的倍数，便是所求得的数，列成算式为：70×2+21×3+15×2=233，233—105×2=23。

这种方法称之为“中国剩余定理”。

数论中的余数问题，遇到同时被3个数除时，好多同学都不知道如何入手，这里给出了一个非常好的解决方法！例1：有兵一队，若1至3报数，最后一人报数为2；若1至5报数，最后一个报数为3；若1至7报数，最后一人报数为4.这一队士兵最少有多少人？解法一：这道题翻译成数学语言就是，一个数除以3余2，除以5余3，除以7余4，求适合条件的最小自然数。

设士兵有x人，可用同余式表示为：x≡2（mod3），x≡3（mod5），x≡4（mod7）。

可用“枚举法”：因为x≡2（mod3），所以x可能等于2、5、8、11、14、17、20、23、26、29、32、35、38、41、44、47、50、53、56……又因为x≡3（mod5），所以x可能等于3、8、13、18、23、28、33、38、43、48、53、58……又因为x≡4（mod7），所以x可能等于4、11、18、25、32、39、46、53、60……同时出现在上述三个数列中的第一个数是53，所以符合条件的最小自然数是53.解法二：从上面看到同时满足三个条件的数最早出现在第三列，可先考虑被7除余4的数从小到大为4、11、18、25……其中第一个满足被5除余3的数是18，给18加上5与7的最小公倍数35的0倍，1倍，2倍，3倍……，得数列18、53、88，……这个数列的每一个数都满足被7除余4，被5除余3，其中满足被3除余2的第一个数是53，也就是这队士兵最少53人。

中国剩余定理的全部内容我们在此，把中国剩余定理说得清清楚楚，明明白白，方便教师教学，学生学习和理解。

该定理说穿了，是不需要证明的，是因为，每一个剩余数的存在都是必然的，唯一的。

理由如下：1、素数当A，B，C，D，…，H为不同的素数时，有：因它们为不同的素数，所以，它们之间是不能相互整除的。

自然数除以A的余数分为0，1，2，3，…，A-1，共A种不同的选择，除以其它素因子的余数也是一样，分别为B，C，D，…，H种不同的选择。

这些不同的余数按排列组合共为A*B*C*D*…*H种排列，即在除以素数A，B，C，D，…，H中各选择一个余数，为在A*B*C*D*…*H之内的一个具体的数，它们是一一对应的，必然存在的，所以，这是无需证明的。

例，某数为M，M/3余1，M/5余3，M/7余2，M/11余5，求M＝？因为，M在3*5*7*11中是唯一的，所以，我们就采取计算唯一数的方法：（1）、满足除以11余5的数为等差数列5+11N，（2）、将5+11N取7项：5，16，27，38，49，60，71，只有16满足除以7余2，因11*7＝77，得新等差数列16+77N，（3）、将16+77N取5项：16，93，170，247，324，只有93除以5余3，因77*5＝385，得新等差数列93+385N，（4）、将93+385N取3项：93，478，863，得478为满足这些条件的数，因385*3＝1155，即478+1155数列的所有项都满足这些条件。

2、单合数如果，前面所列的素因子中，不包括素数P，S，D，那么，不论是P，S，D，还是P的N次方，S的K次方，D的Z次方都不能被A，B，C，D，…，H整除，那么，自然数除以P的N次方的余数同样有P的N次方个不同的选择，除以S的K次方的余数同样有S的K次方个不同的选择，除以D的Z次方的余数同样D 的Z次方个不同的选择，同样按排列组合在A*B*C*D*…*H*（P的N次方）*（S 的K次方）*（D的Z次方）内，对除以A，B，C，D，…，H，P的N次方，S 的K次方，D的Z次方各选择一个余数，对应这之内的一个数，都是一一对应的，必然存在的。