当前位置：文档之家 › 中国剩余定理

中国剩余定理

  • 格式：ppt
  • 大小：131.00 KB
  • 文档页数：27

下载文档原格式

  / 27

合集下载

什么是中国剩余定理

什么是中国剩余定理

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

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

中国剩余定理

中国剩余定理
中国剩余定理
扩展欧几里德定理
看过《射雕英雄传》的同学应该记得，当年黄蓉身中奇毒， 郭靖将她送到瑛姑那里救治，进入瑛姑茅舍，瑛姑就给他 们出了一题：
“今有物不知其数，三三数之剩二；五五数
之剩三：七七数之剩二。问物几何？”
黄蓉天资聪慧，哪里难得住她，她略微思考，答：23。
大家是不是很好奇，黄蓉是怎么解出这道 题的呢？
现在人的解法：
用各除数的“基础数”法解。
基础数的条件：
（1）此数必须符合除数自身的余数条件；
（2）此数必须是其他所有各除数的公倍数。
第一步： 求各除数的最小公倍数 ［3，5，71）［3］ 105÷3＝35 ［35］÷3＝11……2 （2）［5］ 105 ÷ 5＝21 21÷5＝4……1（当于3） ∵ 1× 3＝ 3 21×3＝［63］ （3）［7] 105 ÷ 7＝15 15 ÷ 7＝2……1（当于2） ∵ 1× 2＝ 2 ∴15×2＝［30］
其实，这就是享誉中外的《中国剩余定理》。
一、剩余问题 在整数除法里，一个数同时除以几个 数，整数商后，均有剩余；已知各除数及 其对应的余数，从而要求出适合条件的这 个被除数的问题，叫做剩余问题。
古代人的解法：
凡三三数之剩一，则置七十；五五数之剩 一，则置二十一；七七数之剩一则置十五； 一百六以上，以一百零五减之即得。 依定理译成算式解为： 70×2＋21×3＋15×2＝233 233－105×2＝23
第三步： 求各基础数的和 35+63+30＝128 第四步： 求基准数（最小的，只有一个） 128-105=23 第五步： 求适合条件的数X X＝23+105K（K是整数）

中国剩余定理

中国剩余定理

m1 3
m2 5
取
M1 1
M2 1
M3 1
则唯一解为
x 35 (1) 2 211 3 15 1 2 (mod 105) 23
例2 求最小的正整数 n, 使得 n 被 3,5,11 除的 余数分别是 2,3,5
解 对 x 2(mod 3),x 3(mod 5), x 5(mod 11)
x bk (mod mk ) 则 (*) 有解 (mi , m j ) | ai a j
(*)
x 2(mod 3), x 3(mod 5), x 2(mod 7)
a 2 (mod 3), a 0 (mod 5), a 0 (mod 7) b 0 (mod 3), b 3 (mod 5), b 0 (mod 7) c 0 (mod 3), c 0 (mod 5), c 2 (mod 7)
设 因此
g i ( x) (ai a1 )(ai ai 1 )(ai ai 1 )(ai an )
( x a1 )( x ai 1 )( x ai 1 )( x an )
中国剩余定理的代数表示 设 m 1, 则
m 的标准分解式为 m p1 p2 ps
习题
求解 f ( x) 0(mod 35)
f ( x) x 2 x 8 x 9
4 3
1 求最小的正整数 n,使得它的 是一个平方数, 2 1 1 是一个立方数, 是一个5次方数. 3 5
广义的中国剩余定理 设
x b1 (mod m1 ), x b2 (mod m2 ),
(mod 60)
求解
f ( x) 0(mod m)

中国剩余定理知识点总结

中国剩余定理知识点总结

中国剩余定理知识点总结在初等数论中，我们经常会遇到形如x ≡ a1 (mod m1)x ≡ a2 (mod m2)...x ≡ an (mod mn)的线性同余方程组，其中ai和mi都是整数，m1, m2, ..., mn是两两互质的正整数。

中国剩余定理就是解决这类问题的重要方法。

下面我们来详细介绍一下中国剩余定理的一些基本知识点。

1. 中国剩余定理的表述中国剩余定理可以用如下的形式来表述：对于给定的两两互质的正整数m1, m2, ..., mn，以及任意的整数a1, a2, ..., an，中国剩余定理断言，存在一个解x，使得对于所有的i=1,2,...,n，都有x≡ai(mod mi)。

这个解x是唯一存在的，并且可以用下面的形式来表示：x = a + tM其中a是通解，t是任意整数，M是m1, m2, ..., mn的最小公倍数，即M=lcm(m1, m2, ..., mn)。

2. 中国剩余定理的应用在数论和密码学等领域中，中国剩余定理有着广泛的应用。

例如，可以利用中国剩余定理来解决一些测定一些重要的数学问题，如幂模运算、循环小数、素数和因数分解等问题。

在密码学中，中国剩余定理也被广泛应用。

例如在RSA公钥密码系统中，中国剩余定理能够加速大数的幂模运算，从而大大提高RSA的加密和解密速度。

3. 中国剩余定理的证明中国剩余定理的证明是通过数学归纳法来完成的。

首先我们可以证明当n=2时定理成立，然后利用数学归纳法来证明对于任意n都成立。

具体来说，我们首先假设对于n=k（k≥2）时定理成立，即对于任意的m1, m2, ..., mk，以及任意的整数a1, a2, ..., ak，能够找到一个解x使得x≡ai(mod mi)。

然后我们来考察下一个情况，即n=k+1时定理成立。

我们可以利用n=k时的结果来构造一个新的解x'，然后利用一些数论知识来证明x'也满足n=k+1时的情况。

通过这样的数学归纳法的证明，我们可以得出中国剩余定理的正确性。

中国剩余定理内涵及其简单应用

中国剩余定理内涵及其简单应用

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

所谓线性同余方程组，是指一组形如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。

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

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

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

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

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

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

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

中国剩余定理

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

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

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

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

未知”。

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

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

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

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

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

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

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

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

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

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

中国剩余定理计算过程

中国剩余定理计算过程摘要：一、引言二、中国剩余定理的概念与基本原理1.定义2.基本原理三、中国剩余定理的计算过程1.确定方程组2.求解模数3.计算解四、实例演示五、中国剩余定理的应用与意义1.在数论中的运用2.在密码学中的作用六、总结与展望正文：一、引言在中国数学史上，剩余定理是一项重要的成果。

它起源于古代数学家对分数问题的研究，经过一系列的发展，最终形成了现在我们所熟知的中国剩余定理。

本文将详细介绍中国剩余定理的计算过程及其在实际应用中的重要性。

二、中国剩余定理的概念与基本原理1.定义中国剩余定理（Chinese Remainder Theorem）是一种数论中的结果，它可以用来求解一组同余方程。

设m1、m2、…、mk 为正整数，a1、a2、…、ak 为整数，且gcd(m1，a1)=1，gcd(m2，a2)=1，…，gcd(mk，ak)=1，则同余方程组x ≡ a1 (mod m1)x ≡ a2 (mod m2)…x ≡ ak (mod mk)有唯一解x0，且x0 ≡ ai (mod mi)，其中i=1，2，…，k。

2.基本原理中国剩余定理基于以下两个原理：（1）同余方程的解具有唯一性；（2）同余方程的解可以通过模线性方程组求解。

三、中国剩余定理的计算过程1.确定方程组给定同余方程组：x ≡ a1 (mod m1)x ≡ a2 (mod m2)…x ≡ ak (mod mk)首先确定方程组中的模数mi（i=1，2，…，k）。

2.求解模数根据同余方程组的性质，我们可以通过求解模数来进一步求解原方程组。

求解模数的过程如下：（1）计算mi 与m1、m2、…、mk 的最大公约数，记为d；（2）求解x ≡ 0 (mod mi)；（3）计算x0 = mi × (a1 × d / mi + a2 × (d / m2) + … + ak × (d / mk))；（4）检验x0 是否为方程组的解，若为解，则求解完毕；若不是解，则继续求解。

第8章中国剩余定理和RSA算法

8.4中国剩余定理
8.4中国剩余定理
定理1-10中国剩余定理 (CRT：Chinese Remainder Theorem) 设m1,m2,…，mk是两两互素的正整数，即： (mi,mj)=1，i≠j，i, j=1,2,…，k，则同余方 程组：
X≡b1 mod m1 X≡b2 mod m2 …… X≡bk mod mk


但Diffie-Hellman的开创性论文却引起了美国麻 省理工学院（MIT）的年青教授Ron Rivest对公 钥加密技术的极大兴趣，他下决心要开发一个 最终的公钥加密技术。于是他邀请两位同事Adi Shamirt和 Len Adleman一起来解决这个问题。 1977年，三人开发出了一个能够真正加密数据 的公钥加密算法，并于1978年在一篇题为“A Method for Obtaining Digital Signatures and Public Key Cryptosystems(获取数字签名和公钥 加密系统的方法)”中公开了这个算法，这就是 著名的RSA算法（以三位发明者名字的首字母 缩写命名）。 RSA先后被ISO、ITU、SWIFT等国际化标准组 织采用作为标准。
课后习题： 1.韩信点兵的故事。今有兵员不知其数，每五个数 之，剩下1人；每六个数之，剩下5人；每七人数 之，剩下4人；每十一人数之，剩下10人，问兵 员多少？ *编写中国剩余定理算法程序。 2.什么是单向陷门函数？ 3.P201 9.2 a, b 9.3
用数学方法攻击RSA的途径有以下三种： 分解n为两个素因子。这样就可以计算出φ(n)= （p-1）（q-1），从而可以确定 d≡e-1(mod φ(n))。 直接确定φ(n)而不先确定p和q。 直接确定d，而不先确定φ(n)。 对RSA的密码分析的讨论大都集中于第一种攻击 方法，即分解n。在选择RSA的n时，密钥大小在 1024至2048位范围内是合适的。

中国剩余定理


▪ 后来人们根据古人的研究经验又得出《3、 5、8剩余定理》诗曰： 三人同行40多，五树梅花96朵， 八仙过海105招，除百二十便解惑。并 补充《3、4、5剩余定理》： 三人同行40里，四季花开45枝， 五朵金花36浪，除去六十便得知。
▪谢谢
韩信点兵
▪ 秦朝末年，楚汉相争。一次，韩信将1500名将士与楚王大 将李锋交战。苦战一场，楚军不敌，败退回营，汉军也死 伤四五百人，于是韩信整顿兵马也返回大本营。当行至一 山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土 飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。 韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。 他命令士兵3人一排，结果多出2名；接着命令士兵5人一 排，结果多出3名；他又命令士兵7人一排，结果又多出2 名。韩信马上向将士们宣布：我军有1073名勇士，敌人不 足五百，我们居高临下，以众击寡，一定能打败敌人。汉 军本来就信服自己的统帅，这一来更相信韩信是“神仙下 凡”、“神机妙算”。于是士气大振。一时间旌旗摇动， 鼓声喧天，汉军步步进逼，楚军乱作一团。交战不久，楚 军大败而逃。
物不知数
▪ 我国古代数学名著 《孙子算经》载有一 道数学问题：“今有 物不知其数，三三数 之剩二，五五数之剩 三，七七数之剩二。 问物几何？”这里的 几何指多少的意思。 翻译成数学语言就是： 求正整数N，使N除以3 余2，除以5余3，除以 7余2。
解答
▪ 《孙子算经》给出了一个非常有效的巧妙 解法。术（即答案）曰：“三、三数之剩 二，置一百四十；五、五数之剩三，置六 十三；七、七数之剩二，置三十，并之， 得二百三十三。以二百一十减之，即得。 凡三、三数之剩一，则置七十；五、五数 之剩一，则置二十一；七、七数之剩一， 则置十五。一百六以上，一百五减之，即 得。”
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

一些关于中国剩余定理的定理：
定理2：二数不能整除，若被除数扩大（或 缩小）了几倍，而除数不变，则其余数也 同时扩大（或缩小）相同的倍数（余数必 小于除数）。
如：22÷7＝3……1 （22×4）÷7＝12……1×4（＝4） （要余2即 22×2÷7＝6……2） （22×9）÷7＝28……1×9-7（＝2） （想余5则22×5÷7＝15……5）
代码：PKU1006
#include<iostream>
using namespace std;
int main(){

int p,e,i,d,j,k,a=1,b=1,c=1;

for(j=1;;j++){

if(23*28*j%33==1){

a=23*28*j; break;

}

tmp = x; x = y; y = tmp - a / b * y;
}
return d;
}
int main (){
__int64 a1, m1, a2, m2, t, n, d, x, y;
int flag;
while (scanf ("%I64d", &n) != EOF){
/showproblem.php?pid=13
70
跟PKU1006一样，只是要注意输入。
scanf("%d",&x);
while(x)
{

getchar();

x--;
}
Hdoj 1573
/showproblem.php?p id=1573
第三步： 求各基础数的和 35+63+30＝128 第四步： 求基准数（最小的，只有一个）
128-105=23 第五步： 求适合条件的数X X＝23+105K（K是整数）
这个步骤让我想起了韩信点兵：
传说西汉大将韩信，由于比较年轻，开始他的部 下对他不很佩服。有一次阅兵时，韩信要求士兵 分三路纵队，结果末尾多2人，改成五路纵队，结 果末尾多3人，再改成七路纵队，结果又余下2人， 后来下级军官向他报告共有士兵2395人，韩信立 即笑笑说不对（因2395除以3余数是1，不是2）， 由于已经知道士兵总人数在2300?/FONT>2400 之间，所以韩信根据23，128，233，------，每相 邻两数的间隔是105，便立即说出实际人数应是 2333人（因2333=128+20χ105+105，它除以3 余2，除以5余3，除以7余2）。这样使下级军官 十分敬佩，这
其实，这就是享誉中外的《中国剩余定理》。
一、剩余问题 在整数除法里，一个数同时除以几个数，
整数商后，均有剩余；已知各除数及其对 应的余数，从而要求出适合条件的这个被 除数的问题，叫做剩余问题。
古代人的解法：
凡三三数之剩一，则置七十；五五数之剩 一，则置二十一；七七数之剩一则置十五； 一百六以上，以一百零五减之即得。
代码：PKU1061
#include <iostream>
using namespace std;
__int64 X, Y;
__int64 exp_gcd(__int64 a, __int64 b, __int64 &X, p;
printf("Case %d: the next triple peak occurs in %d
days.\n",j,k);

else

printf("Case %d: the next triple peak occurs in 21252
days.\n",j);

}

return 0;
}
Hdoj 1730
scanf ("%I64d%I64d", &m1, &a1);
n--; flag = 0;
while (n--) {

scanf ("%I64d%I64d", &m2, &a2);

d = exGcd (m1, m2, x, y);

if ((a2 - a1) % d != 0) flag = 1;
}
return 0;
}
PKU 1061 青蛙的约会
/JudgeOnline/problem?id= 1061
大意：青蛙A和青蛙B，规定纬度线上东经0度处 为原点，一条首尾相接的数轴由东往西为正方向， 单位长度1米。设青蛙A的出发点坐标是x，青蛙B 的出发点坐标是y。青蛙A一次能跳m米，青蛙B 一次能跳n米，两只青蛙跳一次所花费的时间相同。 纬度线总长L米。现在要你求出它们跳了几次以后 才会碰面。（同一时间跳到同一点上 才算碰面）

__int64 m = 1;

while(m) {

m = a%b； a = b; b = m;
}

return a;
}
__int64 x, y, m, n, l, A, B, C;
__int64 gcd;
int main(){
while(scanf("%I64d%I64d%I64d%I64d%I64d", &x, &y, &m, &n, &l) != EOF) {

else

printf("Case %d: the next triple peak occurs in 21252 days.\n",j);

}

return 0;
}
改进版：PKU1006
#include<iostream>
using namespace std;
int main(){
中国剩余定理
扩展欧几里德定理
看过《射雕英雄传》的同学应该记得，当年黄蓉身中奇毒， 郭靖将她送到瑛姑那里救治，进入瑛姑茅舍，瑛姑就给他 们出了一题：
“今有物不知其数，三三数之剩二；五五数 之剩三：七七数之剩二。问物几何？”
黄蓉天资聪慧，哪里难得住她，她略微思考，答：23。
大家是不是很好奇，黄蓉是怎么解出这道 题的呢？

X *= C;
if(X < 0) X += ((-X/B) + 1) * B;
else if(X > 0) X -= (X/B)*B;
printf("%I64d\n", X);
}
}
模板：
基础数： int extended_euclid(int a, int b, int &x, int &y) { int d; if(b == 0) {x = 1; y = 0; return a;} d = extended_euclid(b, a % b, y, x); y -= a / b * x; return d; }
A = n - m; B = l; C = x - y;
gcd = GCD(A, B);
if(C % gcd != 0) {

printf("Impossible\n"); continue;
}
A = A/gcd; B = B/gcd; C = C/gcd;
exp_gcd(A, B, X, Y);
以上是韩信点兵的故事，就要确定K值了。
另外一种解法： 用枚举筛选法解 按除数3，7同余2，依次逐一枚举；随后用
除以5余3，进行筛选，便可获解。
摘录条件

3......2
（基准数） ÷ 5……3 同余 2

7......2
（一）求3和7的最小公倍数［3，7] ＝21
（二）进行枚举筛选
依定理译成算式解为： 70×2＋21×3＋15×2＝233 233－105×2＝23
一些关于中国剩余定理的定理：
定理1：几个数相加，如果只有一个加数， 不能被数a整除，而其他加数均能被数a整 除，那么它们的和，就不能被数a整除。
如：10能被5整除，15能被5整除，但7 不能被5整除，所以（10+15+7）不能被5 整除。

if(b == 0){

q = a; X = 1; Y = 0;

return q;

}else{

q = exp_gcd(b, a % b, X, Y);

temp = X; X = Y; Y = temp - (a / b) * Y;

return q;
}
}
__int64 GCD(__int64 a, __int64 b){
现在人的解法：
用各除数的“基础数”法解。
基础数的条件：
（1）此数必须符合除数自身的余数条件； （2）此数必须是其他所有各除数的公倍数。
第一步：
求各除数的最小公倍数

［3，5，7］＝105
第二步： 求各除数的基础数
（1）［3］ 105÷3＝35 ［35］÷3＝11……2 （2）［5］ 105 ÷ 5＝21 21÷5＝4……1（当于3） ∵1×3＝3 21×3＝［63］ （3）［7] 105 ÷ 7＝15 15 ÷ 7＝2……1（当于2） ∵1×2＝2 ∴15×2＝［30］

t = m2 / d;

x *= (a2-a1) / d;

x = (x % t + t) % t;