中国剩余定理在数论题中的应用
例题：
   在200至300之间，有三个连续的自然数a<b<c，3|a、7|b、13|c,即a,b,c分别能被3、7、13整除，问这三个数分别是多少？
分析：
   方法一：先找出200至300之间的能被13整除的数，然后看看比它小1的数能不能被7整除，比它小2的数能不能被3整除（想想为什么要先找能被13整除的？因为能被13整除的少，能被3整除的多）。200至300之间能被13整除的数有：208，221，234，247，260，273，286，299（注：想想怎么快速找出能被13整除的数？需不需要用200去除以13？其实不需要，因为每13个连续自然数里面就有一个能被13整除的数，所以可以先找出一个能被13整除的，然后不断加13和减13就行，比如：一眼看出260能被13整除，260不断加13得到：273，286，299；260不断减13得到：247，234，221，208，这样都找出来了，学数学需要不断动脑筋）然后先看他们减2能不能被3整除：206，219，232，245，258，271，284，297很容易判断：219，258，297能被3整除再最后判断219，258，297加1能不能被7整除，220，259，298中只有259能被7整除所以这三个数是：258，259，260（注：为什么要先检验能不能被3整除而不检验能不能被7整除？因为判断一个数能不能被3整除容易。）

   方法二：方法一比较简单，但是不通用，比如要找出1-1000之间满足条件的数就很困难了。我们可以用中国剩余定理来做(附后)。中国剩余定理解决的是一个数的问题，比如：一个数被3除余1，被4除余2，被5除余4，这个数最小是几？而本题涉及到三个数，怎么办呢？很容易，可以先转化为一个数，我们可以先算出最大的那个自然数，最大的数能被13整除，被7除余1，被3除余2（想想为什么？），那我们的问题就转化为：200-300之间的一个数满足：被13除余0，被7除余1，被3除余2，这个数是几？用中国剩余定理来解就很简单了题中3、7、13三个数两两互质。则〔3，7〕=21；〔3，13〕=39；〔7，13〕=91；〔3，7，13〕=273。为了使21被13除余1，用21×5=105；使39被7除余1，用39×2=78；使91被3除余1，用91×1=91。然后，105×0＋78×1＋91×2=260，因为，260<273，所以260就是所求的数。所以这三个数分别为：258，259，260

 方法三：假设这三个连续自然数分别为a-2，a-1，aa-2能被3整除，a-1能被7整除，a能被13整除考虑a+13这个数因为a能被13整除，所以a+13能被13整除因为a-1能被7整除，（a+13）-（a-1）=14，所以a+13能被7整除因为a-2能被3整除，（a+13）-（a-2）=15，所以a+13能被3整除这样a+13能同时被3，7，13整除，是他们的公倍数所以a+13=3*7*13=273，a=260所以所求的三个数分别为：258，259，260

 方法四：最大的数能被13整除，假设最大数为13k，那么这三个连续自然数就是13k-2，13k-1，13k那么我们的关键是求出一个k，使得13k-2能被3整除，而且13k-1能被7整除，我们利用整除的性质来做由（13k-1）能被7整除知，14k-（13k-1）=k+1也能被7整除（因为两个能被7整除的差也能被7整除），由（13k-2）能被3整除知，（13k-2）-12k=k-2也能被3整除，（k-2）+3=k+1也能被3整除得出k+1能同时被3和7整除，k+1=3*7=21,k=20所以所求的三个数分别为：258，259，260

中国剩余定理
    中国剩余定理是中国古代求解一次同余式组的方法。是数论中一个重要定理。

原文
    中国剩余定理我国古代数学名著《孙子算经》中，记载这样一个问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。”用现在的话来说就是：“有一批物品，三个三个地数余二个，五个五个地数余三个，七个七个地数余二个，问这批物品最少有多少个。”这个问题的解题思路，被称为“孙子问题”“鬼谷算”“隔墙算”“韩信点兵”等、、、等。那么，这个问题怎么解呢？明朝数学家程大位把这一解法编成四句歌诀：三人同行七十（70）稀，五树梅花廿一（21）枝，七子团圆正月半（15），除百零五（105）便得知。
    歌诀中每一句话都是一步解法：第一句指除以3的余数用70去乘；第二句指除以5的余数用21去乘；第三句指除以7的余数用15去乘；第四句指上面乘得的三个积相加的和如超过105，就减去105的倍数，就得到答案了。即：70×2＋21×3＋15×2－105×2=23

算理
  为什么这样解呢？因为70是5和7的公倍数，且除以3余1。21是3和7的公倍数，且除以5余1。15是3和5的公倍数，且除以7余1。（任何一个一次同余式组，只要根据这个规律求出那几个关键数字，那么这个一次同余式组就不难解出了。）把70、21、15这三个数分别乘以它们的余数，再把三个积加起来是233，符合题意，但不是最小，而105又是3、5、7的最小公倍数，去掉105的倍数，剩下的差就是最小的一个答案。

解释
  三数为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) ;

证明
　　令T1=k1×m1,T2=k2×m2,T3=k3×m3;
　　因为 k1%a==1 ；所以 T1%a==m1;
　　对于 a，已知： T2%a==0,T3%a==0,T1%a==m1;
　　所以： Answer%a==m1;
　　因为：T1%b==0,T3%b==0,T2%b==m2 => Answer%b==m2
　　同理：Answer%c==m3;
　　又因为 a×b×c能同时整除 a b c，所以Answer ± P×(a×b×c）也是题目的解；
　　所以Answer是题目的解，又Answer = Answer % (a×b×c），所以Answer为最小解.

推广
  中国剩余定理推广到一般情形：
  设m1,m2,…mk是两两互素的正整数，则对任意b1,b2,…,bk，同余方程组
  x mod m1=b1 mod m1,
  x mod m2=b2 mod m2,
  …
  x mod mk=bk mod mk, 其解为： x=(M1’M1b1+M2’M2b2+…+M’kMkbk )mod m
  m=m1m2…mk,
  Mi=m/mi  MiMi’ mod mi=1 显然(Mi,mi)=1
  即Mi’是Mi的逆元或者可用辗转相除法求Mi’.

例1：一个数被3除余1，被4除余2，被5除余4，这个数最小是几？题中3、4、5三个数两两互质。则〔4，5〕=20；〔3，5〕=15；〔3，4〕=12；〔3，4，5〕=60。为了使20被3除余1，用20×2=40；使15被4除余1，用15×3=45；使12被5除余1，用12×3=36。然后，40×1＋45×2＋36×4=274，因为，274>60，所以，274－60×4=34，就是所求的数。

例2：一个数被3除余2，被7除余4，被8除余5，这个数最小是几？题中3、7、8三个数两两互质。则〔7，8〕=56；〔3，8〕=24；〔3，7〕=21；〔3，7，8〕=168。为了使56被3除余1，用56×2=112；使24被7除余1，用24×5=120。使21被8除余1，用21×5=105；然后，112×2＋120×4＋105×5=1229，因为，1229>168，所以，1229－168×7=53，就是所求的数。

例3：一个数除以5余4，除以8余3，除以11余2，求满足条件的最小的自然数。题中5、8、11三个数两两互质。则〔8，11〕=88；〔5，11〕=55；〔5，8〕=40；〔5，8，11〕=440。为了使88被5除余1，用88×2=176；使55被8除余1，用55×7=385；使40被11除余1，40×8=320。用然后，176×4＋385×3＋320×2=2499，因为，2499>440，所以，2499－440×5=299，就是所求的数。

例4：有一个年级的同学，每9人一排多5人，每7人一排多1人，每5人一排多2人，问这个年级至少有多少人？题中9、7、5三个数两两互质。则〔7，5〕=35；〔9，5〕=45；〔9，7〕=63；〔9，7，5〕=315。为了使35被9除余1，用35×8=280；使45被7除余1，用45×5=225；使63被5除余1，用63×2=126。然后，280×5＋225×1＋126×2=1877，因为，1877>315，所以，1877－315×5=302，就是所求的数。

例5：有一个年级的同学，每9人一排多6人，每7人一排多2人，每5人一排多3人，问这个年级至少有多少人？题中9、7、5三个数两两互质。则〔7，5〕=35；〔9，5〕=45；〔9，7〕=63；〔9，7，5〕=315。为了使35被9除余1，用35×8=280；使45被7除余1，用45×5=225；使63被5除余1，用63×2=126。然后，280×6＋225×2＋126×3=2508，因为，2508>315，所以，2508－315×7=303，就是所求的数。（例5与例4的除数相同，那么各个余数要乘的“数”也分别相同，所不同的就是最后两步。）

练习:
1、一个数除以7余1，除以8余2，除以9余3，求满足条件的最小的自然数。
2、在10000以内，除以3余2，除以7余3，除以11余4的数有多少个？
3、满足除以5余1，除以7余3，除以8余5的最小自然数。
4、求满足除以6余3，除以8余5，除以9余6的最小自然数。
5、在小于1000的自然数中，除以4余3，除以5余2，除以7余4的最大自然数是多少？
6、有一个两位数，除以2与除以3都余1，除以4与除以5都余3，求这个数。