中国剩余定理介绍
在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2），问物几何？”这个问题称为“孙子问题”，
明朝数学家程大位在他著的《算法统宗》(1593年)中就用四句很通俗的口诀暗示了此题的解法:
三人同行七十稀，
五树梅花甘一枝，
七子团圆正半月，
除百零五便得知。
"正半月"暗指15。"除百零五"的原意是，当所得的数比105大时，就不断减105，直到使之小于105；这相当于用105去除，求出余数。用数学的方式表达就是（70*3+21*5+15*7）%105=23
该问题的一般解法在国际上称为“中国剩余定理”。具体解法可以分为三步：
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*2）得到和233。
3. 求符合条件的最小数：
用三个乘积的和233除以3，5，7三个数的最小公倍数105，得到余数23，即233%5=23。这个余数23就是符合条件的最小数。
中国剩余定理分析（两两互质）
我们可以将“孙子问题”分解成几个简单的小问题。
首先，我们假设n1是满足除以3余2的一个数，比如2，5，8等等。同样，我们假设n2是满足除以5余3的一个数，n3是满足除以7余2的一个数。
有了这些假设，我们先从n1角度分析，已知n1满足除以3余2，能不能使得 n1+n2 的和仍然满足除以3余2呢？进而使得n1+n2+n3的和仍然满足除以3余2呢？
这里涉及到一个基本的数学定理，如果有a%b=c,则有(a+kb)%b=c(k为非零整数)，通俗地讲，如果一个除法运算的余数为c，那么被除数与k倍的除数相加（或相减）的和（差）再与除数相除，余数不变。
根据这个定理，如果n2是3的倍数，n1+n2就依然满足除以3余2。同理，如果n3也是3的倍数，那么n1+n2+n3的和就满足除以3余2。这是从n1的角度考虑的，再从n2，n3的角度分析，我们可推导出以下三点：
1. 为使n1+n2+n3的和满足除以3余2，n2和n3必须是3的倍数。
2. 为使n1+n2+n3的和满足除以5余3，n1和n3必须是5的倍数。
3. 为使n1+n2+n3的和满足除以7余2，n1和n2必须是7的倍数。
因此，为使n1+n2+n3的和作为“孙子问题”的一个最终解，需满足：
1. n1除以3余2，且是5和7的公倍数。
2. n2除以5余3，且是3和7的公倍数。
3. n3除以7余2，且是3和5的公倍数。
所以，孙子问题解法的本质是从5和7的公倍数中找一个除以3余2的数n1，从3和7的公倍数中找一个除以5余3的数n2，从3和5的公倍数中找一个除以7 余2的数n3，再将三个数相加得到解。（在求n1，n2，n3时有一个小技巧，以n1为例，并非从5和7的公倍数中直接找一个除以3余2的数，而是先找一个除以3余1的数，再乘以2。）
这里又有一个数学公式，如果a%b=c，那么（a*k）%b=a%b+a%b+…+a%b=c+c+…+c=kc（k>0）,也就是说，如果一个除法的余数为c，那么被除数的k倍与除数相除的余数为kc。如展开式中的证明。
最后，我们还要注意，n1+n2+n3只是问题的一个解，并不是最小的解。如何得到最小解？我们只需要从中最大限度的减掉掉3，5，7的公倍数105 即可。道理就是前面讲过的定理“如果a%b=c,则有(a-kb)%b=c”。所以（n1+n2+n3）%105就是最终的最小解。
以上只是对求孙子问题的简单分析过程，那么如果给出的不仅仅是三组呢？而是10组，20组或者更多呢？下面我们就中国剩余定理进行深入分析，探寻一种解法。
设有n组数据，每组数据的除数为P[i]，余数为R[i]（1<=i<=n），根据上面对孙子问题的分析，我们知道，首先我们要在P[2],P[3],……,P[n]的公倍数中找到一个除以P[1]余R[1]的数num[1],在P[1],P[3],……,P[n]的公倍数中找到一个除以P[2]余R[2]的数num[2],……，在P[1],P[2],……,P[n-1]的公倍数中找到一个除以P[n]余R[n]的数num[n],然后将num[1],num[2],num[3],……，num[n]累加求和sum，最后用sum对P[1],P[2],……,P[n]的最小公倍数求余，得到的数即是符合条件的最小整数。
注意：孙子问题分析时是求出所有数的和在取余，当组数少时，这是没问题的，但是当组数太多时和必然也多，这里我们可以利用公式(a+b)%c=(a%c+b%c)%c就可将程序优化
程序算法的解法代码：
代码如下：
可运行代码：C/C++代码
#include<stdio.h>
#include <iostream>
using namespace std;
//扩展欧几里得算法
int exgcd(int a,int b,int &x,int &y)
{
int d;
if(b==0)
{
x=1;y=0;
return a;
}
d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
//中国剩余定理 ,r[]存放余数 ,prime[]存放两两互质的数
int Chinese_Remainder(int r[],int prime[],int len)
{
int i,d,x,y,m,n=1,sum=0;
//计算所以除数的积n，也是所以除数的最小公倍数
for(i=0;i<len;i++)
n*=prime[i];
//计算符合所以条件的数
for(i=0;i<len;i++)
{
m=n/prime[i];//计算除去本身的所以除数的积m
d=exgcd(prime[i],m,x,y);//计算w[i]*x+m*y=gcd(w[i],m)的一个解y
//累加整数解y的同并不断对n取余，其利用公式:(a+b)%c=(a%c+b%c)%c
sum=(sum+y*m*r[i])%n;
}
return (n+sum%n)%n;//满足所以方程的最小解
}
int main()
{
int n,i;
int prime[15],r[15];
while (printf("请输入组数n：\n"),scanf("%d",&n)!=EOF)
{
printf("请依次输入每组的除数和余数：\n");
for (i=0;i<n;i++)
{
scanf("%d%d",&prime[i],&r[i]);
}
//printf("%d\n",Chinese_Remainder(b,w,n));
printf("符合条件的最小整数：%d\n\n",Chinese_Remainder(r,prime,n));
}
return 0;
}
int Chinese_Remainder(int r[],int prime[],int len)
{
int i,d,x,y,m,n=1,sum=0;
for(i=0;i<len;i++)
n*=prime[i];
for(i=0;i<len;i++)
{
m=n/prime[i];
d=exgcd(prime[i],m,x,y);
sum=(sum+y*m*r[i])%n;
}
return (n+sum%n)%n;
}
原文：http://blog.csdn.net/yanghuaqings/article/details/38415161