欧几里得算法用来求两个数的最大公因数。

欧几里得算法

代码

这个大概是我最早接触的东西了吧，下面是学长传授的代码：

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

证明

$a$和$b$的最大公因数记为$gcd(a,b)$，简写为$(a,b)$ 。

证明Euclid算法的正确性，即证明$(a,b)=(a,b-ka)$ ，$k=\lfloor \frac{a}{b} \rfloor$。

设$x=(a,b)$，$y=(a,b-ka)$，

$\because x=(a,b)$，$\therefore x|a$，$x|b$ 。

$\therefore x|(-ka+b)$，$\therefore x|(a,b-ka)=y$，

故$x \leqslant y$.

$\because y=(a,b-ka)$，$\therefore y|a$，$y|(b-ka)$ 。

$\therefore y|[ka+(b-ka)]=b$，$\therefore y|(a,b)$，即$y|x$，

故$y \leqslant x$.

$\therefore x=y$.

即$(a,b)=(a,b-ka)$ 。

拓展欧几里得算法

上述欧几里得算法仅求出$(a,b)$，而不能得到$(a,b)$关于$a$ 和$b$ 的线性表示，故有了拓展欧几里得算法。

代码

递归版

int EXGCD(int a,int b,int &x,int &y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    int d=EXGCD(b,a%b,x,y);
    int t=x;
    x=y;y=t-a/b*y;
    return d;
}

非递归版

int EXGCD(int a,int b,int &x,int &y){
    int x0=1,x1=0,x2=a;
    int y0=0,y1=1,y2=b;
    while(y2!=0){
        int q=x2/y2;
        int t0=x0,t1=x1,t2=x2;
        x0=y0;x1=y1;x2=y2;
        y0=t0-q*y0;y1=t1-q*y1;y2=t2-q*y2;
    }
    x=x0;y=x1;
    return x2;
}

上述算法可求得$x$ 和$y$ ，使满足$(a,b)=ax+by$ 。

证明

为便于证明，以非递归版本为例。

若$ax_0+bx_1=x_2$，$ay_0+by_1=y_2$，

不难得到$a(x_0-qy_0)+b(x_1-qy_1)=x_2-qy_2$.

上述等式正式保证了拓展欧几里得算法的正确性。

作用

用以求模线性方程$ax+by=(a,b)$ 的解。特别地，当$(a,b)=1$ 时，$x$ 即为$a$ 在$b$ 下的乘法逆元。