欧几里得算法与扩展欧几里得算法

1.欧几里得算法，也叫辗转相除，简称 gcd，用于计算两个整数的最大公约数

　　定义 gcd(a,b) 为整数 a 与 b 的最大公约数

　　引理：gcd(a,b)=gcd(b,a%b)

证明：

设 r=a%b,c=gcd(a,b);

则 a=cx,b=cy,其中x,y互质

r=a%b=a-pb=cx-cpy=c(x-py)

由 r=c(x-py),b=cy,c=gcd(a,b)

可推得 x-py 与 y 互质

反证法：

假设x-py 与 y 不互质

则y=nk,x-py=mk(k>1)

将y代入可得：

x-pnk=mk

x=(pn+m)k

则 a=cx=ck(pn+m),b=cy=ckn

因为k>1,所以gcd(a,b)=ck

与原命题矛盾，则 x-py与y互质，又因为r=c(x-py),b=cy,

所以gcd(b,r)=c

即gcd(a,b)=gcd(b,a%b)=gcd(a%b,b)

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

那么你可能会问 gcd(a,b)=gcd(a,a%b)是否正确？

下面我们来证明一下就知道了。

我们只需证明x与x-py互质就能得到gcd(a,b)=gcd(a,a%b)

反证法：

假设x与x-py不互质

则x=nk,x-py=mk(k>1)

将第二个式子代入第一个式子得：nk-py=mk

化简得：y=((n-m)*k)/p=((n-m)/p)*k

a=cx=cnk,b=cy=((n-m)/p)*ck

当(n-m)/p为正整数时，

那么此时 a 与 b 的最大公约数为 kc 不为 k，与原命题矛盾，则 y 与 x-py 互质，gcd(a,b)=gcd(a,a%b)。

当(n-m)/p不为正整数时，不成立。

所以 x与x-py互质与否是不确定的。原命题错误。

2.扩展欧几里得算法，简称 exgcd，一般用来求解不定方程，求解线性同余方程，求解模的逆元等

　　引理：存在 x , y 使得 gcd(a,b)=ax+by

证明：

当 b=0时,gcd(a,b)=a,此时x=1,y=0

当b!=0时，设ax1+by1=gcd(a,b)=gcd(b,a%b)=bx2+(a%b)y2

cuz a%b=a-a/b*b

so ax1+by1=ay2+b(x2-a/b*y2)

解得 x1=y2,y1=x2-a/b*y2

因为当b=0时存在x,y为最后一组解

每一组解可根据后一组解推得

所以第一组解必然存在

//在求出 a 和 b 的最大公因数 gcd 的同时 ，求出 线性方程 ax + by == g  的一个实数解

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;
}