首先重點(diǎn)講解中國(guó)剩余定理姻灶，舉例：
一個(gè)數(shù)x除d1余r1铛绰，除d2余r2，除d3余r3产喉，那么捂掰，求這個(gè)數(shù)的最小值 。
解答：
r1,r2,r3一定是一個(gè)整數(shù)曾沈，一的倍數(shù)这嚣，所以可以使用到數(shù)論倒數(shù)的知識(shí)來(lái)解答，即逆元：
逆元：對(duì)于正整數(shù)a和m塞俱，如果有ax=1(mod m)姐帚，那么把這個(gè)同余方程中x的最小正整數(shù)解叫做a模m的逆元。
比如2 * 3 % 5 = 1障涯，那么3就是2關(guān)于5的逆元罐旗，或者說(shuō)2和3關(guān)于5互為逆元。
那么在應(yīng)用中唯蝶，可以用到的是：逆元的使用規(guī)則九秀，已知除以d1余r1，除d2余r2粘我，除d3余r3鼓蜒，d1的數(shù)論倒數(shù)是M1，d2的數(shù)論倒數(shù)是M2涂滴，d3的數(shù)論倒數(shù)是M3友酱，那么，x=M1?r1+M2?r2+M3?r3柔纵。
由于可能得到的數(shù)比d1缔杉，d2，d3的公倍數(shù)要大搁料，所以可以將得到的數(shù)減去公倍數(shù)或详，得到的就是這個(gè)數(shù)的最小值系羞。

還可以不用數(shù)論倒數(shù)的方法來(lái)理解：
引入實(shí)例：一個(gè)整數(shù)除以三余一，除以五余二霸琴，除以七余三椒振，求這個(gè)最小整數(shù)。

若一個(gè)數(shù)可以被5梧乘，7整除澎迎，但不可以被3整除，那么該數(shù)一定是5选调，7的倍數(shù)夹供，5，7的最小公倍數(shù)：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的最小公倍數(shù)是105，那么：
157-105=52骂蓖。

解答：被除數(shù)加上（或減去）除數(shù)的倍數(shù)积瞒，除數(shù)不變，余數(shù)也不變登下，那么茫孔，例如70為除3余1叮喳，而45，42都為3的倍數(shù)缰贝，那么馍悟，加上3的倍數(shù)以后除以3的結(jié)果仍然是余1的，依次類推剩晴，可得上式解锣咒。

在代碼的實(shí)現(xiàn)過(guò)程中，考慮到程序的簡(jiǎn)潔性赞弥，通常使用的是第一個(gè)方法：求逆元解答宠哄，但是逆元需要如何求出呢？在這里使用的便是歐幾里得算法嗤攻。
歐幾里得算法毛嫉，又稱輾轉(zhuǎn)相除法，主要用來(lái)求解兩個(gè)數(shù)的最大公約數(shù)：
可以使用遞歸迭代等方法妇菱，主要實(shí)現(xiàn)形式為：
gcd（a承粤，b）=gcd（b，a%b）闯团。

歐幾里得算法的擴(kuò)展算法主要應(yīng)用于三個(gè)方面：
（1）求解不定方程辛臊；
（2）求解模線性方程（線性同余方程）；
（3）求解模的逆元房交；

這里主要講解歐幾里得算法的擴(kuò)展算法：
（1）使用擴(kuò)展歐幾里德算法解決不定方程的辦法：

對(duì)于不定整數(shù)方程pa+qb=c彻舰，若 c mod Gcd(p, q)=0,則該方程存在整數(shù)解，否則不存在整數(shù)解候味。
上面已經(jīng)列出找一個(gè)整數(shù)解的方法刃唤，在找到p ? a+q ? b = Gcd(p, q)的一組解p0,q0后，p ? a+q ? b = Gcd(p, q)的其他整數(shù)解滿足：
p = p0 + b/Gcd(p, q) ? t
q = q0 - a/Gcd(p, q) ? t(其中t為任意整數(shù))
至于pa+qb=c的整數(shù)解白群，只需將p ? a+q ? b = Gcd(p, q)的每個(gè)解乘上 c/Gcd(p, q) 即可尚胞。

在找到p ? a+q ? b = Gcd(a, b)的一組解p0,q0后，應(yīng)該是得到p ? a+q ? b = c的一組解p1 = p0?(c/Gcd(a,b)),q1 = q0?(c/Gcd(a,b))帜慢，

p ? a+q ? b = c的其他整數(shù)解滿足：
p = p1 + b/Gcd(a, b) ? t
q = q1 - a/Gcd(a, b) ? t(其中t為任意整數(shù))
p 笼裳、q就是p ? a+q ? b = c的所有整數(shù)解。
相關(guān)證明可參考：http://www.cnblogs.com/void/archive/2011/04/18/2020357.html

用擴(kuò)展歐幾里得算法解不定方程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)用擴(kuò)展歐幾里德算法求解模線性方程的方法：
同余方程 ax≡b (mod n)對(duì)于未知數(shù) x 有解粱玲，當(dāng)且僅當(dāng) gcd(a,n) | b躬柬。且方程有解時(shí)，方程有 gcd(a,n) 個(gè)解抽减。
求解方程 ax≡b (mod n) 相當(dāng)于求解方程 ax+ ny= b, (x, y為整數(shù))

設(shè) d= gcd(a,n)允青，假如整數(shù) x 和 y，滿足 d= ax+ ny(用擴(kuò)展歐幾里德得出)胯甩。如果 d| b昧廷，則方程

a? x0+ n? y0= d堪嫂， 方程兩邊乘以 b/ d，(因?yàn)?d|b木柬，所以能夠整除)皆串，得到 a? x0* b/ d+ n? y0? b/ d= b。
所以 x= x0? b/ d眉枕，y= y0? b/ d 為 ax+ ny= b 的一個(gè)解恶复，所以 x= x0? b/ d 為 ax= b (mod n ) 的解。
ax≡b (mod n)的一個(gè)解為 x0= x? (b/ d ) mod n速挑，且方程的 d 個(gè)解分別為 xi= (x0+ i? (n/ d ))mod n {i= 0... d-1}谤牡。

設(shè)ans=x?(b/d),s=n/d;

方程ax≡b (mod n)的最小整數(shù)解為：(ans%s+s)%s;

相關(guān)證明：

證明方程有一解是: 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個(gè)解: 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

首先看一個(gè)簡(jiǎn)單的例子：
5x=4(mod3)
解得x = 2,5,8,11,14.......由此可以發(fā)現(xiàn)一個(gè)規(guī)律，就是解的間隔是3.
那么這個(gè)解的間隔是怎么決定的呢姥宝？
如果可以設(shè)法找到第一個(gè)解翅萤，并且求出解之間的間隔，那么就可以求出模的線性方程的解集了.
我們?cè)O(shè)解之間的間隔為dx.
那么有a?x = b(mod n);a?(x+dx) = b(mod n);兩式相減腊满，得到:
a*dx(mod n)= 0;

也就是說(shuō)a*dx就是a的倍數(shù)套么，同時(shí)也是n的倍數(shù)，即a?dx是a 和 n的公倍數(shù).為了求出dx,我們應(yīng)該求出a 和 n的最小公倍數(shù),此時(shí)對(duì)應(yīng)的dx是最小的.

設(shè)a 和 n的最大公約數(shù)為d,那么a 和 n 的最小公倍數(shù)為(a*n)/d.
即a?dx = a?n/d;
所以dx = n/d.
因此解之間的間隔就求出來(lái)了.
代碼如下：

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。
這時(shí)稱求出的 x 為 a 的對(duì)模 n 乘法的逆元笤受。
對(duì)于同余方程 ax= 1(mod n )穷缤， gcd(ax,n)= 1 的求解，即ax減一是n的整數(shù)倍感论，假設(shè)為y倍绅项，有ax=ny+1，由于y是一個(gè)未知量比肄，故方程的求解就是解方程：ax+ ny= 1，x, y 為整數(shù)囊陡。這個(gè)可用擴(kuò)展歐幾里德算法求出惩妇，原同余方程的唯一解就是用擴(kuò)展歐幾里德算法得出的 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;
}