欧几里得算法（也叫辗转相除法）： 问题描述：              a 和 b的最大公约数是多少？ 古代解法：辗转相除法 迭代过程：例如： {a = 15 和 b = 12  } =>{ a = 12,b =  15 - (15/12)* 12 = 3 } => {a = 3,b=  12 - (12/3)*3 = 0 } => { b = 0 所以a为最大公因数}
从上述思路可得模板代码： int gcd1(int a,int b){ int r; while(b>0){ r=a%b; a=b; b=r; } return a; } 也可以一行代码简单解决： int gcd2(int a,int b){ return b?gcd2(b,a%b):a; }   扩展欧几里得算法：一般用来求解不定方程，求解线性同余方程，求解模的逆元等。 引理：存在 x , y 使得 gcd(a,b)=ax+by 　　证明：        　　当 b=0 时，gcd(a,b)=a，此时 x=1 , y=0        　　当 b!=0 时，               设 ax1+by1=gcd(a,b)=gcd(b,a%b)=bx2+(a%b)y2        　　又因 a%b=a-a/b*b        　　则 ax1+by1=bx2+(a-a/b*b)y2                    ax1+by1=bx2+ay2-a/b*by2                    ax1+by1=ay2+bx2-b*a/b*y2                    ax1+by1=ay2+b(x2-a/b*y2) 　　　　解得 x1=y2 , y1=x2-a/b*y2 　　　　因为当 b=0 时存在 x , y 为最后一组解 　　　　而每一组的解可根据后一组得到 　　　　所以第一组的解 x , y 必然存在 　　　　得证 　　根据上面的证明，在实现的时候采用递归做法 　　先递归进入下一层，等到到达最后一层即 b=0 时就返回x=1 , y=0 　　再根据 x=y’ , y=x’-a/b/y’ ( x’ 与 y’ 为下一层的 x 与 y ) 得到当层的解 　　不断算出当层的解并返回，最终返回至第一层，得到原解。 代码如下： int ex_gcd(int a,int b,int &x,int &y){ if(b == 0){ x = 1;y = 0; return a; }else{ int r = ex_gcd(b,a%b,y,x); int t = y; y = x - (a/b)*y; x = t; return r; } }   乘法逆元：是指数学领域群G中任意一个元素a，都在G中有唯一的逆元a‘，具有性质a×a'=a'×a=e，其中e为该群的单位元。（离散数学中的知识） 例如：4关于1模7的乘法逆元为多少？                         4X≡1 mod 7 这个方程等价于求一个X和K，满足                        4X=7K+1 其中X和K都是整数。 若ax≡1 mod f, 则称a关于1模f的乘法逆元为x。也可表示为ax≡1(mod f)。 当a与f互素时，a关于模f的乘法逆元有解。如果不互素，则无解。如果f为素数，则从1到f-1的任意数都与f互素，即在1到f-1之间都恰好有一个关于模f的乘法逆元。 例如，求5关于模14的乘法逆元：                         14=5*2+4                         5=4*1+1 说明5与14互素，存在5关于14的乘法逆元。  1=5-4=5-(14-5*2)=5*3-14 因此，5关于模14的乘法逆元为3。   欧拉定理： 若正整数 a , n 互质，则  aφ(n)≡1(mod n)   其中 φ(n) 是欧拉函数（1~n) 与 n 互质的数。   费马小定理： 对于质数p，任意整数a，均满足：ap≡a（mod p） 证明如下： 　　这个可以用欧拉定理来说明：首先，我们把这个式子做一个简单变换得：ap-1 * a ≡ a（mod p） 因为a ≡ a（mod p）恒成立，所以ap-1 mod p == 1时费马小定理才成立，又因为p是质数，所以 φn == n-1 ,所以根据欧拉定理：若a，p互质则ap-1 mod p == 1成立。那么对于a，p不互质，因为p是质数，所以，a一定是倍数ap ≡ a ≡ 0（mod p）。综上所述，费马小定理成立，其实它算是欧拉定理的一个特例。