中国剩余定理

什么是中国剩余定理？剩余定理详细解法中国数学史书上记载：在两千多年前的我国古代算书《孙子算经》中，有这样一个问题及其解法：今有物不知其数，三三数之剩二；五五数之剩三：七七数之剩二。

问物几何？意思是说：现在有一堆东西，不知道它的数量，如果三个三个的数最后剩二个，如果五个五个的数最后剩三个，如果七个七个的数最后剩二个，问这堆东西有多少个？你知道这个数目吗？《孙子算经》这道著名的数学题是我国古代数学思想“大衍求一术”的具体体现，针对这道题给出的解法是：N=70×2＋21×3＋15×2-2×105＝23如此巧妙的解法的关键是数字70、21和15的选择： 70是可以被5、7整除且被3除余1的最小正整数，当70×2时被3除余2 21是可以被3、7整除且被5除余1的最小正整数，当21×3时被5除余3 15是可以被3、5整除且被7除余1的最小正整数，当15×2时被7除余2 通过这种构造方法得到的N就可以满足题目的要求而减去2×105 后得到的是满足这一条件的最小正整数。

韩信点兵又称为中国剩余定理，相传汉高祖刘邦问大将军韩信统御兵士多少，韩信答说，每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人……。

刘邦茫然而不知其数。

我们先考虑下列的问题：假设兵不满一万，每5人一列、9人一列、13人一列、17人一列都剩3人，则兵有多少？首先我们先求5、9、13、17之最小公倍数9945（注：因为5、9、13、17为两两互质的整数，故其最小公倍数为这些数的积），然后再加3，得9948（人）。

中国有一本数学古书「孙子算经」也有类似的问题：「今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？」答曰：「二十三」术曰：「三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之，即得。

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

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

codeforces 中国剩余定理
中国剩余定理（Chinese Remainder Theorem，CRT）是一种数
论定理，用于解决一类同余方程组的问题。

该定理在程序设计竞赛中经常出现，特别在Codeforces竞赛中。

CRT能够高效地求解形如x ≡ a1 (mod m1), x ≡ a2 (mod m2), ..., x ≡ an (mod mn)的同余方程组，其中ai表示余数，mi表示模数。

CRT的基本原理是利用同余方程组中的两个方程，通过求解
线性方程逐个合并为一个方程。

具体步骤如下：
1. 计算mi的乘积M = m1 × m2 × ... × mn。

2. 计算Mi = M / mi，即除去mi的乘积。

3. 计算Mi关于mi的逆元ti，满足Mi × ti ≡ 1 (mod mi)。

4. 计算x = (a1 × Mi × ti + a2 × Mi × ti + ... + an × Mi × ti) % M。

其中%表示取余操作，保证x的值在0到M-1之间。

CRT的时间复杂度为O(nlogM)，其中n表示方程组中的方程
数量，M表示所有模数的乘积。

在Codeforces竞赛中，当遇到有多个方程组成的同余方程组
问题时，需要运用CRT来快速求解x的值，从而提高算法的效率。

中国古代求解一次同余式组（见同余）的方法。

是数论中一个重要定理。

又称中国剩余定理。

注释：三数为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，令素数为A，B，C，D，…，Z，已知M/A余a，M/B余b，M/C余c，M/D余d，…，M/Z余z。

求M=？因为A，B，C，D，…，Z为不同的素数，故，B*C*D*…*Z不可能被A整除，有等差数列（B*C*D*…*Z）+（B*C*D*…*Z）N中取A个连续项，这A个连续项分别除以A的余数必然存在0，1，2，3，…，A-1，所以，从这A个连续项中能寻找到除以A余1的数。

再用除以A余1的这个数*a其积必然除以A余a，这个除以A余a 的数，为能够被素数B*C*D*…*Z整除的数，为第一个数；再按同样的道理，从A*C*D*…*Z的倍数中寻找除以B余b的数,该数具备被素数A，C，D，…，Z整除的特性，为第二个数；因为，第一个数除以A余a，第二个数能被素数A，C，D，…，Z整除，即能被A整除，所以，第一个数+第二个数之和，仍然保持除以A余a；同理，第二个数除以B余b，因第一个数能被B整除，所以，第二个数+第一个数之和，仍然保持除以B余b。

中国剩余定理内涵及其简单应用
中国剩余定理是数论中的一个重要定理，它提供了求解一类线性同余方程组的方法。

所谓线性同余方程组，是指一组形如x ≡ a1 (mod m1), x ≡ a2 (mod m2), …, x ≡ an (mod mn)的方程，其中x是未知数，a1, a2, …, an是已知数，而m1, m2, …, mn是不同的正整数。

中国剩余定理的内涵是：当所给线性同余方程组的模m1, m2, …, mn 两两互素时，存在唯一解x ≡ X (mod M)，其中X是x的一个解，而M = m1 * m2 * … * mn。

简单来说，中国剩余定理告诉我们，当模数两两互素时，我们可以通过对每个方程求解，再通过一定的运算，得到原方程组的解。

中国剩余定理的应用非常广泛，特别是在密码学和计算机科学中。

例如，当我们需要对一个数进行加密和解密时，可以使用中国剩余定理来进行模运算，从而快速计算得到加密后的结果。

此外，在计算机科学中，中国剩余定理也常用于优化算法和并行计算。

由于中国剩余定理能够将一个大问题拆分成多个小问题并行求解，因此可以显著提高计算效率。

总之，中国剩余定理作为数论中的重要定理，不仅具有深刻的理论意义，还具有广泛的实际应用。

通过它，我们可以快速求解线性同余方程组，加密和解密数据，优化算法等，从而提高计算效率和保护数据安全。

中国剩余定理简介在《孙⼦算经》中有这样⼀个问题：“今有物不知其数，三三数之剩⼆（mod3=2），五五数之剩三（mod5=3），七七数之剩⼆(mod7=2），问物⼏何？”这个问题称为“孙⼦问题”，该问题的⼀般解法国际上称为“中国剩余定理”。

具体解法分下⾯三步：1、找出三个数：从3和5的公倍数中找出被7除余1的最⼩数15，从3和7的公倍数中找出被5除余1 的最⼩数21，最后从5和7的公倍数中找出除3余1的最⼩数70。

2、⽤15乘以2（2为最终结果除以7的余数），⽤21乘以3（3为最终结果除以5的余数），同理，⽤70乘以2（2为最终结果除以3的余数），然后把三个乘积相加15∗2+21∗3+70∗215∗2+21∗3+70∗2得到和233。

3、⽤233除以3、5、7的最⼩公倍数105，得到余数23，这个余数23就是符合条件的最⼩数。

很神奇，是吧？我们逐步剖析。

我们第⼀⽬标是求⼀个数n符合条件，⽽不需最⼩。

我们先假设n1是满⾜mod3=2的任意⼀个数，n2是满⾜mod5=3的任意⼀个数，n1是满⾜mod7=2的任意⼀个数。

如果想要(n1+n2)也mod3=2，n2必须是3的倍数（易证）。

如果想要(n1+n2+n3)也mod3=2，n3也得是3的倍数。

归纳得要想(n1+n2+n3)同时满⾜mod3=2,mod5=3,mod7=2，必须有：1. n1mod3=2 && 5|n1 && 7|n12. n2mod5=3 && 3|n2 && 7|n23. n3mod7=5 && 3|n3 && 5|n3于是只需要在5,7的倍数中找⼀个mod3=2的作为n1，在3,7的倍数中找⼀个mod5=3的作为n2，在3,5的倍数中找⼀个mod7=2的作为n3即可。

解决这个⼩问题孙⼦⼜⽤了⼀个⼩技巧。

就是不是先找mod3=2的，⽽是先找mod3=1的再把它乘2⾃然它就mod3=2了。

剩余定理的计算中国剩余定理公式小学如下：1、余数定理（Polynomial remainder theorem）是指一个多项式f(x) 除以一个线性多项式(x-a)的余数是f(a)。

若f(a)=0，则(x-a)为多项式f(x)的因式。

例如，(5x3+4x2-12x+1)/(x-3) 的余式是5·33+4·32-12·3+1=136。

2、多项式f(x)除以(x-a)所得的余数等于f(a)。

3、证明：根据除法的定义及性质可知，被除数=除数×商+余数。

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。

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

解答方法：三人同行七十希，五树梅花廿一枝，七子团圆正半月，除百零五便得知。

意思是:将除以3得余数乘以70，将除以5得余数乘以21，将除以7得余数乘以15，全部加起来后再减去105或105的整倍数，得到的数就是答案。

70X2+21x3+15x2=233=105x2+23，结果就是23。

解法举例：例一：一个数，除以5余1，除以3余2。

问这个数最小是多少？采用通用的方法：逐步满足法把除以5余1的数从小到大排列：1，6，11，16，21，26，……然后从小到大找除以3余2的，发现最小的是11.所以11就是所求的数。

先满足一个条件，再满足另一个条件，所以称之为“逐步满足法”。

例二：一个数除以5余1，除以3也余1。

问这个数最小是多少？（1除外）特殊的方法：最小公倍法除以5余1：说明这个数减去1后是5的倍数。

除以3余1：说明这个数减去1后也是3的倍数。

中国剩余定理简单公式中国剩余定理，又称孙子定理，是一种用来求解一类模线性方程组的方法。

它的基本思想是将一个复杂的方程组化简成一些简单的方程，并通过求解这些简单方程来得到原方程的解。

中国剩余定理的简单公式可以表示为：假设给定一组模数m1, m2, ..., mn，并且这些模数两两互素（即最大公约数为1），同时给定一组余数a1, a2, ..., an，那么存在一个整数x，满足以下条件：x ≡ a1 (mod m1)x ≡ a2 (mod m2)...x ≡ an (mod mn)其中≡表示'同余'关系，即两个数除以某个数的余数相等。

中国剩余定理的求解过程可以按照以下步骤进行：1. 计算模数的乘积M = m1 * m2 * ... * mn。

2. 计算每个模数除以M的余数Mi，即 Mi = M / mi。

3. 计算Mi关于模数mi的乘法逆元ni，即满足 Mi * ni ≡ 1 (mod mi)。

4. 计算解x，即 x = (a1 * Mi * ni + a2 * Mi * ni + ... + an * Mi * ni) % M。

通过以上步骤，就可以得到模线性方程组的解x。

中国剩余定理在密码学、编码理论、计算机科学等领域有着重要的应用。

它可以高效地求解大数模运算问题，同时也可以用来对数据进行加密和解密，保护数据的安全性。

此外，中国剩余定理还可以用来加速计算，提高算法的效率。

总结起来，中国剩余定理是一种非常有用的数学工具，它通过将复杂的方程组转化为简单的方程，大大简化了问题的求解过程。

无论是在理论研究还是实际应用中，中国剩余定理都具有重要的价值和意义。