歐幾里德算法

歐幾里德算法又稱輾轉相除法，用于計算兩個整數a,b的最大公約數。其計算原理依賴于下面的定理：

定理：gcd(a,b) = gcd(b,a mod b)

 證明：a可以表示成a = kb + r，則r = a mod b
假設d是a,b的一個公約數，則有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公約數
假設d 是(b,a mod b)的公約數，則
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公約數
因此(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證

歐幾里德算法就是根據這個原理來做的，其算法用C++語言描述為：

    void swap(int & a, int & b)
    {
        int c = a;
        a = b;
        b = c;
    }
    int gcd(int a,int b)
    {
        if(0 == a )
        {
            return b;
        }
        if( 0 == b)
        {
            return a;
        }
        if(a > b)
        {
            swap(a,b);
        }
        int c;
        for(c = a % b ; c > 0  ; c = a % b)
        {
            a = b;
            b = c;
        }
        return b;
    }

模P乘法逆元

對于整數a、p，如果存在整數b，滿足ab mod p =1，則說，b是a的模p乘法逆元。

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

 證明：
首先證明充分性
如果gcd(a,p) = 1，根據歐拉定理，aφ(p) ≡ 1 mod p，因此
顯然aφ(p)-1 mod p是a的模p乘法逆元。
再證明必要性
假設存在a模p的乘法逆元為b
ab ≡ 1 mod p
則ab = kp +1    ，所以1 = ab - kp
因為gcd(a,p) = d
所以d | 1
所以d只能為1

擴展歐幾里德算法

擴展歐幾里德算法不但能計算(a,b)的最大公約數，而且能計算a模b及b模a的乘法逆元，用C語言描述如下：

 int    gcd(int    a,    int    b    ,    int&    ar,int    &    br)
{
int    x1,x2,x3;
int    y1,y2,y3;
int    t1,t2,t3;
if(0    ==    a)
{//有一個數為0，就不存在乘法逆元
             ar    =    0;
             br    =    0    ;
             return    b;
}
if(0    ==    b)
{
             ar    =    0;
             br    =    0    ;
             return    a;
}
x1    =    1;
x2    =    0;
x3    =    a;
y1    =    0;
y2    =    1;
y3    =    b;
int    k;
for(    t3    =    x3    %    y3    ;    t3    !=    0    ;        t3    =    x3    %    y3)
{
k    =    x3    /    y3;
t2    =    x2    -    k    *    y2;
t1    =    x1    -    k    *    y1;
x1    =    y1;
x1    =    y2;
x3    =    y3;
y1    =    t1;
y2    =    t2;
y3    =    t3;
}
if(    y3    ==    1)
{
//有乘法逆元
ar    =    y2;
br    =    x1;
return    1;
}else{
        //公約數不為1，無乘法逆元
         ar    =    0;
         br    =    0;
         return    y3;
}
}

擴展歐幾里德算法對于最大公約數的計算和普通歐幾里德算法是一致的。計算乘法逆元則顯得很難明白。我想了半個小時才想出證明他的方法。

首先重復拙作整除中的一個論斷：

如果gcd(a,b)=d，則存在m,n，使得d = ma + nb，稱呼這種關系為a、b組合整數d，m，n稱為組合系數。當d=1時，有 ma + nb = 1 ，此時可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。

為了證明上面的結論，我們把上述計算中xi、yi看成ti的迭代初始值，考察一組數(t1,t2,t3)，用歸納法證明：當通過擴展歐幾里德算法計算后，每一行都滿足a×t1 + b×t2 = t3

 第一行：1 × a + 0 × b = a成立
第二行：0 × a + 1 × b = b成立
假設前k行都成立，考察第k+1行
對于k-1行和k行有
t1(k-1)    t2(k-1)  t3(k-1)
t1(k)      t2(k)    t3(k)
分別滿足：
t1(k-1) × a + t2(k-1) × b = t3(k-1)
t1(k)   × a + t2(k)   × b = t3(k)
根據擴展歐幾里德算法，假設t3(k-1) = j t3(k) + r
則：
t3(k+1) = r
t2(k+1) = t2(k-1) - j × t2(k)
t1(k+1) = t1(k-1) - j × t1(k)
則
t1(k+1) × a + t2(k+1) × b
=t1(k-1) × a - j × t1(k) × a +
t2(k-1) × b - j × t2(k) × b
= t3(k-1) - j t3(k) = r
= t3(k+1)
得證
因此，當最終t3迭代計算到1時，有t1× a + t2 × b = 1，顯然，t1是a模b的乘法逆元，t2是b模a的乘法逆元。