中国剩余定理

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

问物几何？意思是说：现在有一堆东西，不知道它的数量，如果三个三个的数最后剩二个，如果五个五个的数最后剩三个，如果七个七个的数最后剩二个，问这堆东西有多少个？你知道这个数目吗？《孙子算经》这道著名的数学题是我国古代数学思想“大衍求一术”的具体体现，针对这道题给出的解法是：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（人）。

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

中国剩余定理的证明过程（原创实用版）目录一、引言二、中国剩余定理的概念和背景三、中国剩余定理的证明过程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 m1)，x ≡ a2 (mod m2)，...，x ≡ an (mod mn)，其中a1，a2，...，an是给定的整数，m1，m2，...，mn是给定的互质的正整数。

我们的目标是求解出x 的解。

二、中国剩余定理的原理中国剩余定理的核心思想是通过一系列的同余方程组的解来得到整个同余方程组的解。

其原理可以简要概括为以下三个步骤：1. 求出同余方程组中所有模数的乘积n = m1 * m2 * ... * mn；2. 对于每个同余方程，计算mi关于n/mi的乘法逆元Mi；3. 计算解x = (a1 * M1 * n1 + a2 * M2 * n2 + ... + an * Mn * nn) % n，其中ni = n / mi。

三、中国剩余定理的计算过程下面通过一个具体的例子来演示中国剩余定理的计算过程。

例子：求解同余方程组x ≡ 2 (mod 3)，x ≡ 3 (mod 4)，x ≡ 2 (mod 5)。

1. 计算n = 3 * 4 * 5 = 60；2. 分别计算Mi和ni：M1 = n / m1 = 60 / 3 = 20，n1 = M1^-1 ≡ 20^-1 ≡ 2 (mod 3)；M2 = n / m2 = 60 / 4 = 15，n2 = M2^-1 ≡ 15^-1 ≡ 3 (mod 4)；M3 = n / m3 = 60 / 5 = 12，n3 = M3^-1 ≡ 12^-1 ≡ 2 (mod 5)；3. 计算解x：x = (2 * 20 * 2 + 3 * 15 * 3 + 2 * 12 * 2) % 60 = 68 % 60 = 8。

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

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

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

一、“孙子定理”某数除以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。

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

是数论中一个重要定理。

又称中国剩余定理。

注释：三数为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了。

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

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

中国剩余定理的简单公式可以表示为：假设给定一组模数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。

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

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

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

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

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

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

是数论中⼀个重要定理。

⾸先来⼀个⼩！例！题！吧！注释：三数为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 }。

ctf 中国剩余定理
摘要：
1.中国剩余定理的背景和定义
2.中国剩余定理的求解方法
3.中国剩余定理的应用实例
4.中国剩余定理的历史和影响
正文：
中国剩余定理，也被称为中国古代数学的瑰宝，是我国古代数学家在代数学领域中的一项杰出贡献。

这一定理最早出现在《孙子算经》中，后来被南宋数学家秦九韶命名为“中国剩余定理”。

中国剩余定理的定义是：已知n 个整数a1, a2,..., an 和n 个模数m1, m2,..., mn，如果存在整数x1, x2,..., xn，使得
ax1 ≡ a (mod m1),
ax2 ≡ a (mod m2),
...
axn ≡ a (mod mn),
则称a 关于模数m1, m2,..., mn 的中国剩余定理解为x1, x2,..., xn。

中国剩余定理的求解方法主要有两种：一种是基于迭代的算法，另一种是基于矩阵的方法。

基于迭代的算法是利用已知的解，通过迭代的方式求解新的解。

而基于矩阵的方法是将中国剩余定理转化为线性方程组，然后利用矩阵的逆来求解。

中国剩余定理在现代密码学、计算机科学等领域有着广泛的应用。

例如，在公钥密码系统中，中国剩余定理可以用来求解加密后的密文，从而实现解密。

中国剩余定理的历史可以追溯到2000 多年前的我国古代数学。

中国剩余定理一、中国古代趣题中国数学名著《孙子算经》里有这样的问题：“今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？”答曰：“二十三。

”此类问题我们可以称为“物不知其数”类型，又被称为“韩信点兵”。

（相传汉高祖刘邦问大将军韩信统御兵士多少，韩信答说，每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人……。

刘邦茫然而不知其数。

）孙子算经的作者及确实著作年代均不可考，不过根据考证，著作年代不会在晋朝之后，以这个考证来说上面这种问题的解法，中国人发现得比西方早，所以这个问题的推广及其解法，被称为中国剩余定理。

中国剩余定理（ChineseRemainder Theorem）在近代抽象代数学中占有一席非常重要的地位。

我国明朝有位大数学家叫程大位，他在解答“物不知其数”问题（即：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？）时用四句诗概括出这类问题的优秀解法：“三人同行七十稀，五树梅花廿一枝，七子团圆正月半，除百零五便得知。

”诗中的每一句话都表示一个步骤：三人同行七十稀，是说除以3所得的余数用70乘；五树梅花廿一枝，是说除以5所得的余数用21乘；七子团圆正月半，是说除以7所得的余数用15乘；除百零五便得知，是说把上面乘得的3个积加起来，减去105的倍数，减得差就是所求的数。

此题的中国剩余定理的解法是：用70乘3除所得的余数，21乘5除所得的余数，15乘7除所得的余数，把这3个结果加起来，如果它大于105，则减去105，所得的差如果仍比105大，则继续减去105，最后所得的整数就是所求．也就是2×70+3×21+2×15=233，233-105=128，128-105=23。

70，21，15，105是从何而来？先看70，21，15，105的性质：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整除的数，105是3，5，7的最小公倍数。

数论中中国剩余定理的含义
中国剩余定理是数论中的一个重要定理，它描述了当给定的一个数论问题中的条件得到满足时，问题成立的概率。

具体来说，中国剩余定理是一个关于质数分布的定理，它指出当任意两个整数 a 和 b 含有同一个素因子时，a 的 n 次方除以 b 的 n 次方的余数为 n。

中国剩余定理的几何意义在于，它描述了一个闭子集不相交的空间。

函数环的理想对应着空间的闭子集，素理想对应着不可约的闭子集，极大理想对应着单点集，理想互素对应着闭子集不相交，两个单点集当然不相交，对应着极大理想。

因此，中国剩余定理可以看作是闭子集不相交的几何表述。

此外，中国剩余定理还有一个重要应用，就是它在密码学中的重要性。

由于中国剩余定理可以用来预测任意素数 p 的 n 次方模 q 的余数，因此它被广泛应用于密码破解和加密算法中。

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

是数论中一个重要定理。

又称中国余数定理。

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

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

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

数论是纯粹数学的分支之一，主要研究整数的性质。

按研究方法来看，数论大致可分为初等数论和高等数论。

初等数论是用初等方法研究的数论，它的研究方法本质上说，就是利用整数环的整除性质，主要包括整除理论、同余理论、连分数理论。

高等数论则包括了更为深刻的数学研究工具。

它大致包括代数数论、解析数论、计算数论等等。

初等数论主要就是研究整数环的整除理论及同余理论。

此外它也包括了连分数理论和少许不定方程的问题。

本质上说，初等数论的研究手段局限在整除性质上。

初等数论中经典的结论包括算术基本定理、欧几里得的质数无限证明、中国剩余定理、欧拉定理（其特例是费马小定理）、高斯的二次互反律，勾股方程的商高定理、佩尔方程的连分数求解法等等。