扩展欧几里得算法:已知整数 $a$、$b$,求得 $x$、$y$ 满足 $ax+by=\gcd(a,b)$.

预备知识

欧几里得算法 (Euclidean algorithm)

常叫辗转相除法,其证明了 $\gcd(a,b)=\gcd(b,a\bmod b)$.

这里给出代码供下文参考:

int gcd(int a, int b)
{
    if (!b)
        return a;
    return gcd(b, a % b);
}

笔记链接:https://io.zouht.com/17.html

裴蜀定理 (Bézout's lemma)

对任何整数 $a$、$b$ 和 $m$,关于未知数 $x$ 和 $y$ 的线性丢番图方程(称为裴蜀等式):

$$ ax+by=m $$

有整数解时当且仅当 $m$ 是 $a$ 及 $b$ 的最大公约数 $d$ 的倍数。

扩展欧几里得算法 (Extended Euclidean algorithm)

算法描述

已知整数 $a$、$b$,扩展欧几里得算法可以在求得 $a$、$b$ 的最大公约数的同时,能找到整数 $x$、$y$(其中一个很可能是负数),使它们满足贝祖等式:

$$ ax + by = \gcd(a, b) $$

算法过程

特解

在欧几里得算法中,递归边界时 $b=0$,$\gcd(a,0)=a$。此时裴蜀等式为:

$$ ax+0y=a $$

易得 $x=1,y=0$,然后返回 $(a,1,0)$,第一位代表最大公约数,第二、三位代表该层裴蜀等式的 $x$ 和 $y$.

在递归中间部分时,我们得到了 $\gcd(b,a\bmod b)=d,x,y$。此时裴蜀等式为(不妨令前面系数为 $y$,后面为 $x$):

$$ \begin{align} by+(a\bmod b)x&=d\\ by+(a-\lfloor\frac{a}{b}\rfloor\cdot b)x&=d\\ ax+b(y-\lfloor\frac{a}{b}\rfloor\cdot x)&=d \end{align} $$

因此当层的解为:

$$ \begin{cases} x'=x\\ y'=y-\lfloor a/b\rfloor\cdot x\\ \end{cases} $$

于是返回 $(d,x',y')$.

通解

该算法求出的是一对满足条件的 $x_0$ 和 $y_0$,实际上答案不唯一,可以通过构造:

$$ a(x_0-k\cdot\frac{b}{d})+b(y_0+k\cdot\frac{a}{d})=d\ (k\in\mathbb{Z}) $$

得到通解:

$$ \begin{cases} x=x_0-k\cdot(b/d)\\ y=y_0+k\cdot(a/d)\\ \end{cases} $$

代码实现

代码中,返回值并未用三元组,而是返回最大公约数,同时通过引用传回了 $x$ 和 $y$,没有本质区别。

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

解决线性同余方程

扩展欧几里得算法可以解决形如 $ax\equiv b\pmod m$ 的线性同余方程,方式如下。

由 $ax\equiv b\pmod m$ 可知,存在 $y$,使 $ax=b+my$. 不妨将 $my$ 移动至等式左侧,负号放入 $y$ 中,则得到:

$$ ax+my=b $$

再令 $d=\gcd(a,m)$,那么关于未知数 $x'$ 和 $y'$ 的裴蜀等式可写为:

$$ ax'+by'=d $$

可使用扩展欧几里得算法得到 $x',y',d$ 的值。如果 $b$ 是 $d$ 的倍数,那么原线性同余方程有解,解为:

$$ \begin{cases} x=x'\cdot(b/d)\bmod m\\ y=y'\cdot(b/d)\bmod m\\ \end{cases} $$

解决模数非质数的乘法逆元

当 $p$ 为质数时,可使用费马小定理求出乘法逆元:

$$ a^{-1}\equiv a^{p-2}\pmod p $$

但当 $p$ 非质数时,该方法失效。此时可构造线性同余方程:

$$ ax\equiv1\pmod p $$

再使用上一节的方法,利用扩展欧几里得算法解该方程即可。

标签: 扩展欧几里得算法

添加新评论