密碼學簡單數論筆記（2）：最大公約數、擴充歐幾裡得算法和最小公倍數

參考資料：

1.https://www.bilibili.com/video/BV1x3411s7Sy/?spm_id_from=333.788&vd_source=e66dd25b0246f28e772d75f11c80f03c

2.http://t.csdn.cn/diQ27

2.餘紅兵：《數學奧林匹克小叢書（第二版）高中卷10————數論》

最大公約數

設a,b∈Z，如果d∈Z且d|a,d|b，則稱d是a和b的公因子（公約數）。

若d>=0,且a和b的所有公因子都整除d，則稱d是a和b的最大公約數，記作gcd(a,b).

之前CSDN上我也寫過一篇gcd篩：

https://blog.csdn.net/hustle28214/article/details/128601837?spm=1001.2014.3001.5501

互素

設a,b∈Z，若gcd(a,b)=1,則稱a和b互素。

互素的a,b公因子僅有±1，該條件可反推出a,b兩數互素.

根據定義有結論：

設gcd(a,b)=d,則存在q1,q2∈Z,使得a=q1d,b=q2d,且gcd(q1,q2)=1.

若gcd(q1,q2)=t>1,則gcd(a,b)=td>d,與“最大”沖突.

歐幾裡得算法（輾轉相除法）

設a>=b>=0,求gcd(a,b)

對于上述條件下的a,b,有a=qb+r;

b=0時,gcd(a,0)=a

b>0時,gcd(a,b)=gcd(b,r)=gcd(r1,r2)

gcd(a,b)=gcd(b,r)這條推廣有必要示範一下：

gcd(40,3)=1

gcd(40,3)=gcd(3,1)=gcd(1,0)=1

依次如此操作直到見到0

int gcd(int x, int y)
{
    int r = x % y;
    while (r != 0)
    {
        x = y;
        y = r;
        r = x % y;
    }    
return y;//最大公約數實作
 
}
           

擴充歐幾裡得算法

(重要)定理5-1（最大公約數表示定理）（裴蜀定理）

設a,b∈Z,d=gcd(a,b),則存在s,t∈Z,使得as+bt=d.

特别地：gcd(a,b)=1————as+bd=1（充要）

推論：d|v————as+bt=v

證明：

設b>=a,b=ax1+r1,那麼b%a後b=r1.

重複輾轉相除直至餘數為0。

b=ax1+r1,

a=r1x2+r2,

…,

rk-3=rk-2xk-1+rk-1(2)

rk-2=rk-1xk+rk,(1)

rk-1=rkxk+1+rk+1.

此時rk+1=0(餘數).由此得出rk=d(最大公約數).将此式代入(1)式，移項得到d=rk-2-rk-1xk.

将此式與(2)式聯立，得到d=rk-2-(rk-3-rk-2xk-1)xk.

展開，得到d=m1rk-2-n1rk-3.

上述所有提及皆為整數,則m1（1-xk-1xk）,n1（-xk）必為整數。

相同的操作可以重複做，不斷帶入之前的式子可以發現最後可以化成d=mka+nkb。

而顯然mk,nk為整數。

證畢。

對于第二條“特别地”的證明如下：

假設gcd(a,b)!=1.

那麼，

将a表示為k1gcd(a,b)=a,

b=k2gcd(a,b).

代入as+bd=1:

k1*gcd(a,b)*s+k2*gcd(a,b)*r=1.

即,(k1s+k2r)=1/gcd(a,b)

那麼右式取值區間為(0,1)，顯然無法滿足整數解性質.

是以gcd(a,b)=1才能使as+bd=1有整數解。

想一想,如果要證其必要性,則假設as+bd=1沒有整數解，右式=1，也必定存在s,d∈Z使得方程有解.

第三條推論自不必說，v是d的整數倍.

是以，擴歐相對于歐幾裡得算法的擴充性就是：使用歐幾裡得算法時，利用餘數和商向上疊代出sn,tn。這同樣也是在計算二進制一次不定方程.

通過擴歐我們可以找到判斷二進制一次不定方程是否有整數解的方法：

對于方程ax+by=z，隻有滿足gcd(a,b)|z，方程才有整數解.

最小公倍數

設a,b∈Z，若m∈Z分别是a和b的倍數，m稱為a和b的公倍數.

記a,b的最小公倍數為lcm(a,b),若m是a和b所有正的公倍數中最小，m稱作a和b的最小公倍數.

lcm(a,b)=ab/gcd(a,b).

我在CSDN那篇上寫“最小公倍數的求算依賴于最大公約數的求算”，其實這有些以偏概全，求最小公倍數的算法并不止這一種。下面就記錄一下這種不需要找最大公約數的神奇算法（更相增益術/更相減損術）：

設有兩正整數0<a<b.

a更小，a自加成2a;此時若發現b更小，b自加，成2b;…;若發現a更小，a自加，直到2k*a=2k-1*b.那麼2ka就等于lcm(a,b)。

int lcm(int a,int b)
{
    while(a!=b)
    {
        if(a<b)
        a+=a;
        else if(b<a)
        b+=b;

    }
    return a;
}