欧几里得算法

欧几里德算法又称，用于计算两个整数a，b的最大公约数。其计算原理依赖于下面的定理：

　　定理：gcd(a,b) = gcd(b,a mod b)
证明：假设m是a,b的一个公约数，则有m|a,m|b,即存在唯一的整数x,y有a=xm,b=ym，由整数的除法知必存在唯一的一组数k,r，使a=kb+r;
        =>  xm=kym+r  =>  r=(x-ky)m  =>  m是r的一个约数  =>  m是b,r的公约数  =>  a,b和b,r具有相同的公约数  =>  a,b和b,r具有相同的最大公约数，即gcd(a,b) = gcd(b,a mod b)。

C代码：
    函数：
    int gcd(int a,int b)
    {
        int c;
        c=a%b;
        if(c==0)
            return b;
        return gcd(b,c);
    }

    程序块：
       while(b!=0)

　　{

　　    temp=b;

　　    b=a%b;

　　    a=temp;

　　}

模P乘法逆元

　　对于整数a、p，如果存在整数b，满足ab mod p =1，则说，b是a的模p乘法逆元。

　　定理：a存在模p的乘法逆元的充要条件是gcd(a，p) = 1


 欧几里德算法的Stein版
Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。和欧几里德算法 算法不同的是，Stein算法只有整数的移位和加减法。

c++/java stein 算法

　　int gcd(int a,int b){

　　if(ab

　　int temp = a;

　　a = b;

　　b=temp;

　　}

　　if(0==b)//the base case

　　return a;

　　if(a%2==0 && b%2 ==0)//a and b are even

　　return 2*gcd(a/2,b/2);

　　if ( a%2 == 0)// only a is even

　　return gcd(a/2,b);

　　if ( b%2==0 )// only b is even

　　return gcd(a,b/2);

　　return gcd((a+b)/2,(a-b)/2);// a and b are odd

　　}

 扩展欧几里德算法

扩展欧几里德算法是用来在已知a, b求解一组x，y使得ax+by = Gcd(a, b) =d(解一定存在，根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。

设 a>b。 
　　1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0； 
　　2，ab!=0 时 
　　设 ax1+by1=gcd(a,b); 
　　bx2+(a mod b)y2=gcd(b,a mod b); 
　　根据朴素的原理有 gcd(a,b)=gcd(b,a mod b); 
　　则:ax1+by1=bx2+(a mod b)y2; 
　　即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2; 
　　根据恒等定理得：x1=y2; y1=x2-(a/b)*y2; 
　　这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2. 
　　上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以
　　结束。


代码：
void exgcd(long long a, long long b, long long &x, long long &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return ;
    }
    exgcd(b, a % b, x, y);
    long long t = x;
    x = y;
    y = t - a / b * y;
    return ;
}

如果加入求最大公约数的功能，即：
int exGcd(int a, int b, int &x, int &y)
{
　　if(b == 0)
　　{
　　  x = 1;
　　  y = 0;
　　  return a; 
　　}
　　int r = exGcd(b, a % b, x, y);
　　int t = x;
　　x = y;
　　y = t - a / b * y;
　　return r;
}