歐幾里德算法
歐幾里德算法又稱輾轉(zhuǎn)相除法，用于計(jì)算兩個(gè)整數(shù)a,b的最大公約數(shù)。其計(jì)算原理依賴于下面的定理：
定理：gcd(a,b) = gcd(b,a mod b)
證明：a可以表示成a = kb + r，則r = a mod b
假設(shè)d是a,b的一個(gè)公約數(shù)，則有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公約數(shù)
假設(shè)d 是(b,a mod b)的公約數(shù)，則
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公約數(shù)
因此(a,b)和(b,a mod b)的公約數(shù)是一樣的，其最大公約數(shù)也必然相等，得證
歐幾里德算法就是根據(jù)這個(gè)原理來(lái)做的，其算法用C++語(yǔ)言描述為：
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乘法逆元
對(duì)于整數(shù)a、p，如果存在整數(shù)b，滿足ab mod p =1，則說(shuō)，b是a的模p乘法逆元。
定理：a存在模p的乘法逆元的充要條件是gcd(a,p) = 1
證明：
首先證明充分性
如果gcd(a,p) = 1，根據(jù)歐拉定理，aφ(p) ≡ 1 mod p，因此
顯然aφ(p)-1 mod p是a的模p乘法逆元。
再證明必要性
假設(shè)存在a模p的乘法逆元為b
ab ≡ 1 mod p
則ab = kp +1 ，所以1 = ab - kp
因?yàn)間cd(a,p) = d
所以d | 1
所以d只能為1
擴(kuò)展歐幾里德算法
擴(kuò)展歐幾里德算法不但能計(jì)算(a,b)的最大公約數(shù)，而且能計(jì)算a模b及b模a的乘法逆元，用C語(yǔ)言描述如下：
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)
{//有一個(gè)數(shù)為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{
//公約數(shù)不為1，無(wú)乘法逆元
ar = 0;
br = 0;
return y3;
}
}
擴(kuò)展歐幾里德算法對(duì)于最大公約數(shù)的計(jì)算和普通歐幾里德算法是一致的。計(jì)算乘法逆元?jiǎng)t顯得很難明白。我想了半個(gè)小時(shí)才想出證明他的方法。
首先重復(fù)拙作整除中的一個(gè)論斷：
如果gcd(a,b)=d，則存在m,n，使得d = ma + nb，稱呼這種關(guān)系為a、b組合整數(shù)d，m，n稱為組合系數(shù)。當(dāng)d=1時(shí)，有 ma + nb = 1 ，此時(shí)可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。
為了證明上面的結(jié)論，我們把上述計(jì)算中xi、yi看成ti的迭代初始值，考察一組數(shù)(t1,t2,t3)，用歸納法證明：當(dāng)通過(guò)擴(kuò)展歐幾里德算法計(jì)算后，每一行都滿足a×t1 + b×t2 = t3
第一行：1 × a + 0 × b = a成立
第二行：0 × a + 1 × b = b成立
假設(shè)前k行都成立，考察第k+1行
對(duì)于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)
根據(jù)擴(kuò)展歐幾里德算法，假設(shè)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)
得證
因此，當(dāng)最終t3迭代計(jì)算到1時(shí)，有t1× a + t2 × b = 1，顯然，t1是a模b的乘法逆元，t2是b模a的乘法逆元。