(Ex)GCD 的正确性证明

(a, b) = (b, a mod b)

Posted by Ghastlcon on December 27, 2017
CC 采用 $\text{CC BY-NC-SA 4.0}$ 许可,转载请注明:“转自 (Ex)GCD 的正确性证明

忽然发现貌似只会默写 $\text{(Ex)GCD}$ 的模板……

证明(扩展)欧几里得算法的正确性。

$\text{GCD}$

设 $\gcd(a,b)=k$ 。

则有 $x=\frac{a}{k},y=\frac{b}{k}$,且 $a,b\geq 1$ 。

这相当于 $a$ 是由 $x$ 个 $k$ 组成,而 $b$ 则由 $y$ 个 $k$ 组成(即相乘)。

因此得 $a\text{ mod }b=k(x\text{ mod }y)$(在 $a$ 的 $x$ 个 $k$ 中尽可能多的删去 $b$ 中的 $y$ 个 $k$)。


现在欲证 $\gcd(b,a\text{ mod }b)=\gcd(a,b)=k$ 。

很显然 $\gcd(b,a\text{ mod }b)\equiv 0\text{ (mod }k)$,所以下面的目的是证明 $\gcd(x\text{ mod }y,y)=1$ 。


反证,假设 $\gcd(x\text{ mod }y,y)=t,t>1$ 。

则 $x\text{ mod }y,y$ 均可继续拆分,即 $x’=\frac{x\text{ mod }y}{t},y’=\frac{y}{t}$ 。

换句话说

存在整数 $r=\left \lfloor \frac{x}{y} \right \rfloor,r\geq 0$,满足

别忘记 $y=y’t,y’\geq 1$,所以


同时,我们原来 $x,y$ 的定义是

现在又有 $\gcd(x,y)\equiv 0\text{ (mod }t),t>1$,相当于 $\gcd(a,b)$ 至少为 $tk$,产生了矛盾。

$\blacksquare\text{ Q.E.D.}$

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

$\text{ExGCD}$

因为我们已经使得 $bx’+(a\text{ mod }b)y’=\gcd(a,b)$,也就是 $bx’+(a-b\left \lfloor \frac{a}{b} \right \rfloor)y’=\gcd(a,b)$:所以拆开,得

然后把 $b$ 归到同 $1$ 个括号里去

$\blacksquare\text{ Q.E.D.}$

void ExGCD(int a, int b, int d, int x, int y)
{
    if(!b)
    {
        d = a;
        x = 1;
        y = 0;
    {
    else
    {
        ExGCD(b, a % b, d, y, x);
        y -= x * (a / b);
    }
    
    return;
}