欧几里得算法(辗转相除法)——求最大公约数

公式:gcd(a,b)=gcd(b,a mod b)

证明:
设a>=b,a=b$\times$r+c,d=(a,b),则c=a%b=a-b$\times$r
(1).gcd(a,b)<=gcd(b,a mod b)
令d|a,d|b,则d|c,即a,b的公约数同时也是a,c的公约数,
a,b的最大公约数也是a,c的公约数,gcd(a,b)<=gcd(a,a mod b)
(2).gcd(b,a)>=gcd(b,a mod b)
令d|b,d|c,则d|a,即b,c的公约数同时也是a,b的公约数,b,c的最大公约数同时也是a,b的公约数,gcd(b,a mod b)<=gcd(a,b)
(3).综上可得,gcd(a,b)=gcd(a,a mod b),证毕

代码——欧几里德算法

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

裴蜀定理

定义:若a,b是整数,且gcd(a,b)=d,那么对于任意整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立
推论:a,b互质的充要条件是存在整数x,y使ax+by=1(容我先把充分必要条件的关系再捋一捋)

证明(关于前半句对于任意整数x,y,ax+by都一定是d的倍数比较好证,在此就略过了.这里主要证明一定存在X,Y使ax+by=d成立):
设a,b为正数且a>=b,d=gcd(a,b)
(1).当b=0,d=a,则x=1,y=0成立
(2).ax+by=d,由于d=gcd(a,b),两边同除以d得a’x+b’y=1,
转证a’x+b’y=1.
由欧几里得公式:
$a’=b’k_0+r_1$,
$b’=r_1k_1+r_2$,
$r_1=r_2k_2+r_3$,
…
$r_{n-3}=r_{n-2}k_{n-2}+r_{n-1}$, (4)
$r_{n-2}=r_{n-1}k_{n-1}+r_n$, (5)
$r_{n-1}=r_nk_n+r_{n+1}$, (6)
设$r_{n+1}=0为末项,则r_n=d=1$,
(6)$r_{n-1}=k_n$ -> $1=1$ -> $x=1,y=0$,成立(递归出口)
(5)$r_{n-2}-r_{n-1}k_{n-1}=1$,由于各项均为整数$A_{n-1}r_{n-2}+B_{n-1}r_{n-1}=1$,成立
联立(4),(5),得$A_{n-2}r_{n-3}+B_{n-2}r_{n-2}=1$,成立,具体过程见下:
将联立两式一般化,设(5)ax+by=1,(6)c=bz+a,a,b,c表示整数,x,y,z表示整数未知数,将$a=\frac{1-by}{x}$带入(6)式且两边同乘x得cx+b(y-zx)=1,即Ac+Bb=1.
将该式不断向上递归可得$A_0a’+B_0b’=1$,证毕
(3).此外对于ax+by是d的n被的情况,我们可以对两边同除以n,转化为(2)情况求解

利用扩展欧几里得定理求通解:ax+by=gcd(a,b)

主要分为以下两步:
(1).找到解的形式
已知d=gcd(a,b),求ax+by=d(1)的解,设x’和y’是该式的其中一对解,即ax’+by’=d(2),
(1)-(2),显然a(x’-x)=b(y-y’),对两边同除以d,得a’(x’-x)=b’(y-y’),
由于a’,b’互为质数,所以b’|(x’-x),令k=(x-x’)/b’(显然k是一个整数),y=y'+ka'
同理可的,x=x'-kb'
(2).找到解与解之间的关系
设当前及其解为:ax+by=d,(1)
下个式子及其解为:bx’+cy’=d,(2)
将c=a-kb(k=a/b)代入(1),易得x=y',y=x'-ky'

代码——扩展欧几里得算法

int exgcd(int a,int b,int &x,&y){
    if(b==0){
        x=1;
        y=0;
        return a;//递归出口
    }
    int d=exgcd(b,a%b,y,x);//这里交换了向下递归时x,y的位置,妙啊!
    y=y-a/b*x;
    return d;
}

结语:

说实话,这篇没有原先写的那几篇有一种通透的感觉,许多内容写起来模棱两可,自己也有些主张不定,
但是,最后推出来的代码跑通了还是有一种理想照亮现实的感觉.加油,奥利给!
材料参考:百度,csdn,y总的蓝桥杯课程数论部分.