扩展欧几里德算法

欧几里德算法

欧几里德算法又称辗转相除法，用于计算两个整数a, b的最大公约数。基本算法：设$a=bq+r$，其中a, b, q, r都是整数，则：

$\gcd(a,b)=\gcd(b,r)$

即$\gcd(a,b)=\gcd(b,a\%b)$。

证明引自离散数学课本：

先看一个整除定理与推论

接下来是证过程：

代码实现：

function gcd(a, b) {
    if (b===0) {
        return a;
    }
    return gcd(b, a%b);
}

扩展欧几里德算法

扩展欧几里德算法是欧几里德算法的扩展。

定理：若$a$和$b$为正整数，则存在整数$x,y$使得$\gcd(a,b)=ax+by$；

换句话说$\gcd(a,b)$可以表示为$a,b$的线性组合，例如：$\gcd(6,14)=2$，而 $2=(-2)*6+1*14$。

已知整数$a,b$，扩展欧几里德算法可以在求得$a,b$的最大公约数的同时，找到整数$x,y$（其中一个很可能是负数），使它们满足等式$ax+by=\gcd(a,b)$。对两个整数$a,b$进行辗转相除法，可得它们的最大公约数，然后，收集辗转相除法中产生的式子，倒回去，可以得到$ax+by=\gcd(a,b)$的整数解。

用类似辗转相除法，求二元一次不定方程$252x+198y=18$的整数解。

$252=1*198+54$ $(1)$

$198=3*54+36$ $(2)$

$54=1*36+18$ $(3)$

$36=2*18$ $(4)$

由$(2)$、$(3)$式可知：

$18=54-1*36$ $(5)$

$36=198-3*54$ $(6)$

将$(6)$代入$(5)$可知：

$18=54-1*36=54-1*(198-3*54)=4*54-1*198$

由$(1)$知$54=252-1*198$，代入上式，得：

$18=4*(252-1*198)-1*198=4*252-5*198$

问题得解：$x=4,y=-5$。

代码实现

欧几里德算法停止的状态是： $a= \gcd(a,b),\;b = 0$

推理2，$ab!=0$时

设 $ax_1+by_1=\gcd(a,b)$;

$bx_2+(a\%b)y_2=\gcd(b,a\%b)$;

根据朴素的欧几里德原理有 $\gcd(a,b)=\gcd(b,a\%b)$;

则: $ax_1+by_1=bx_2+(a\%b)y_2$；

即:$ax_1+by_1=bx_2+(a-\lfloor a/b \rfloor*b)y_2=ay_2+bx_2-\lfloor a/b \rfloor*by_2$；

令$\lfloor a/b\rfloor=k$;

得$ax_1+by_1=bx_2+(a-k*b)y_2=ay_2+b(x_2-k*y_2)=ay_2+b(x_2-\lfloor a/b \rfloor*y_2)$;

根据恒等定理得：$x_1=y_2; y_1=x_2-\lfloor a/b\rfloor*y_2$；

这样我们就得到了求解 $x_1,y_1$的方法：$x_1, y_1$的值基于 $x_2, y_2$.

上面的思想是以递归定义的，因为 $\gcd$不断的递归求解一定会有个时候 $b=0$，所以递归可以结束。

扩展欧几里德算法递归代码：

function exgcd(a, b) {
    let x, y;
    if (b===0) {
        x = 1;
        y = 0;
        return [x, y];
    }
    [x, y] = exgcd(b, a%b);
    [x, y] = [y, x-(Math.floor(a/b))*y];
    return [x, y];
}