首先重点讲解中国剩余定理，举例：
一个数x除d1余r1，除d2余r2，除d3余r3，那么，求这个数的最小值 。
解答：
r1,r2,r3一定是一个整数，一的倍数，所以可以使用到数论倒数的知识来解答，即逆元：
逆元：对于正整数a和m，如果有ax=1(mod m)，那么把这个同余方程中x的最小正整数解叫做a模m的逆元。
比如2 * 3 % 5 = 1，那么3就是2关于5的逆元，或者说2和3关于5互为逆元。
那么在应用中，可以用到的是：逆元的使用规则，已知除以d1余r1，除d2余r2，除d3余r3，d1的数论倒数是M1，d2的数论倒数是M2，d3的数论倒数是M3，那么，x=M1✲r1+M2✲r2+M3✲r3。
由于可能得到的数比d1，d2，d3的公倍数要大，所以可以将得到的数减去公倍数，得到的就是这个数的最小值。
还可以不用数论倒数的方法来理解：
引入实例：一个整数除以三余一，除以五余二，除以七余三，求这个最小整数。
若一个数可以被5，7整除，但不可以被3整除，那么该数一定是5，7的倍数，5，7的最小公倍数：5*7=35，但是不能被3整除，且除3余1。
35%3=2，那么，可以（35✲a）%3=1，解之，a至少等于2：
5✲7✲2=70
依次类推，可以被3，5整除，除7余3，3✲5✲b%7=3，b=3，解为3✲5✲3=45。
可以被3，7整除，除5余2：3✲7✲c%5=2，c=2，解为:3✲7✲2=42。
5✲7✲2=70
3✲5✲3=45
3✲7✲2=42
题解为70+45+42=157，由于3，5，7的最小公倍数是105，那么：
157-105=52。
解答：被除数加上（或减去）除数的倍数，除数不变，余数也不变，那么，例如70为除3余1，而45，42都为3的倍数，那么，加上3的倍数以后除以3的结果仍然是余1的，依次类推，可得上式解。
在代码的实现过程中，考虑到程序的简洁性，通常使用的是第一个方法：求逆元解答，但是逆元需要如何求出呢？在这里使用的便是欧几里得算法。
欧几里得算法，又称辗转相除法，主要用来求解两个数的最大公约数：
可以使用递归迭代等方法，主要实现形式为：
gcd（a，b）=gcd（b，a%b）。
欧几里得算法的扩展算法主要应用于三个方面：
（1）求解不定方程；
（2）求解模线性方程（线性同余方程）；
（3）求解模的逆元；
这里主要讲解欧几里得算法的扩展算法：
（1）使用扩展欧几里德算法解决不定方程的办法：
对于不定整数方程pa+qb=c，若 c mod Gcd(p, q)=0,则该方程存在整数解，否则不存在整数解。
上面已经列出找一个整数解的方法，在找到p ✲ a+q ✲ b = Gcd(p, q)的一组解p0,q0后，p ✲ a+q ✲ b = Gcd(p, q)的其他整数解满足：
p = p0 + b/Gcd(p, q) ✲ t
q = q0 - a/Gcd(p, q) ✲ t(其中t为任意整数)
至于pa+qb=c的整数解，只需将p ✲ a+q ✲ b = Gcd(p, q)的每个解乘上 c/Gcd(p, q) 即可。
在找到p ✲ a+q ✲ b = Gcd(a, b)的一组解p0,q0后，应该是得到p ✲ a+q ✲ b = c的一组解p1 = p0✲(c/Gcd(a,b)),q1 = q0✲(c/Gcd(a,b))，
p ✲ a+q ✲ b = c的其他整数解满足：
p = p1 + b/Gcd(a, b) ✲ t
q = q1 - a/Gcd(a, b) ✲ t(其中t为任意整数)
p 、q就是p ✲ a+q ✲ b = c的所有整数解。
相关证明可参考：http://www.cnblogs.com/void/archive/2011/04/18/2020357.html
用扩展欧几里得算法解不定方程ax+by=c;
代码如下：
01.bool linear_equation(int a,int b,int c,int &x,int &y)
02.{
03. int d=exgcd(a,b,x,y);
04. if(c%d)
05. return false;
06. int k=c/d;
07. x*=k; y*=k; //求得的只是其中一组解
08. return true;
09.}
(2)用扩展欧几里德算法求解模线性方程的方法：
同余方程 ax≡b (mod n)对于未知数 x 有解，当且仅当 gcd(a,n) | b。且方程有解时，方程有 gcd(a,n) 个解。
求解方程 ax≡b (mod n) 相当于求解方程 ax+ ny= b, (x, y为整数)
设 d= gcd(a,n)，假如整数 x 和 y，满足 d= ax+ ny(用扩展欧几里德得出)。如果 d| b，则方程
a✲ x0+ n✲ y0= d， 方程两边乘以 b/ d，(因为 d|b，所以能够整除)，得到 a✲ x0* b/ d+ n✲ y0✲ b/ d= b。
所以 x= x0✲ b/ d，y= y0✲ b/ d 为 ax+ ny= b 的一个解，所以 x= x0✲ b/ d 为 ax= b (mod n ) 的解。
ax≡b (mod n)的一个解为 x0= x✲ (b/ d ) mod n，且方程的 d 个解分别为 xi= (x0+ i✲ (n/ d ))mod n {i= 0... d-1}。
设ans=x✲(b/d),s=n/d;
方程ax≡b (mod n)的最小整数解为：(ans%s+s)%s;
相关证明：
证明方程有一解是: x0 = x'(b/d) mod n;
由 a✲x0 = a✲x'(b/d) (mod n)
a✲x0 = d (b/d) (mod n) (由于 ax' = d (mod n))
= b (mod n)
证明方程有d个解: xi = x0 + i✲(n/d) (mod n);
由 a*xi (mod n) = a ✲ (x0 + i✲(n/d)) (mod n)
= (a✲x0+a✲i✲(n/d)) (mod n)
= a ✲ x0 (mod n) (由于 d | a)
= b
首先看一个简单的例子：
5x=4(mod3)
解得x = 2,5,8,11,14.......由此可以发现一个规律，就是解的间隔是3.
那么这个解的间隔是怎么决定的呢？
如果可以设法找到第一个解，并且求出解之间的间隔，那么就可以求出模的线性方程的解集了.
我们设解之间的间隔为dx.
那么有a✲x = b(mod n);a✲(x+dx) = b(mod n);两式相减，得到:
a*dx(mod n)= 0;
也就是说a*dx就是a的倍数，同时也是n的倍数，即a✲dx是a 和 n的公倍数.为了求出dx,我们应该求出a 和 n的最小公倍数,此时对应的dx是最小的.
设a 和 n的最大公约数为d,那么a 和 n 的最小公倍数为(a*n)/d.
即a✲dx = a✲n/d;
所以dx = n/d.
因此解之间的间隔就求出来了.
代码如下：
01.bool modular_linear_equation(int a,int b,int n)
02.{
03. int x,y,x0,i;
04. int d=exgcd(a,n,x,y);
05. if(b%d)
06. return false;
07. x0=x*(b/d)%n; //特解
08. for(i=1;i<d;i++)
09. printf("%d\n",(x0+i*(n/d))%n);
10. return true;
11.}
（3）用欧几里德算法求模的逆元：
同余方程ax≡b (mod n)，如果 gcd(a,n)== 1，则方程只有唯一解。
在这种情况下，如果 b== 1，同余方程就是 ax=1 (mod n ),gcd(a,n)= 1。
这时称求出的 x 为 a 的对模 n 乘法的逆元。
对于同余方程 ax= 1(mod n )， gcd(ax,n)= 1 的求解，即ax减一是n的整数倍，假设为y倍，有ax=ny+1，由于y是一个未知量，故方程的求解就是解方程：ax+ ny= 1，x, y 为整数。这个可用扩展欧几里德算法求出，原同余方程的唯一解就是用扩展欧几里德算法得出的 x 。
如下代码，所求解为（ax）%b=1，求解为x的值：
#include <iostream>
#include <cstdio>
using namespace std;
int x,y,q;
void extend_Eulid(int a,int b)
{
if(b == 0){
x = 1;y = 0;q = a;
}else{
extend_Eulid(b,a%b);
int temp = x;
x = y;
y = temp - a/b*y;
}
}
int main()
{
int a,b;
cin>>a>>b;
extend_Eulid(a,b);
printf("%d=(%d)*%d+(%d)*%d\n",q,x,a,y,b);
return 0;
}
