Skip to content

扩展欧几里得算法学习笔记

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

相关定理

欧几里得算法

a,bN,b0,gcd(a,b)=gcd(b,a mod b)\begin{array}{ll} \forall a, b \in \N, b \ne 0, \\ \gcd(a, b) = gcd(b, a \bmod b) \end{array}

Bézout 定理

对于任意整数 a,ba, b,存在一对整数 x,yx, y 满足 ax+by=gcd(a,b)ax + by = gcd(a, b)

扩展欧几里得算法

扩展欧几里得算法是用来求二元一次不定方程(如 (1)(1) 式)的一组特解的算法。

ax+by=c(1)\tag{1} ax + by = c

(1)(1) 式有解当且仅当 gcd(a,b) c\gcd(a, b) ~|~ c

实现

对于每次递归,

  • b=0b = 0 时,
    ax+by=aax + by = a,故 x=1,y=0x = 1, y = 0
  • b0b \ne 0 时,
    x=x,y=yabxx = x, y = y - \lfloor\frac{a}{b} \rfloor x

证明:

d=gcd(a,b)d = \gcd(a, b),由欧几里得算法得:

d=ax+by=by+(a mod b)x=by+(aabb)x=ax+b(yabx)\begin{aligned} d & = ax + by \\ & = by + (a \bmod b)x \\ & = by + (a - \lfloor \frac{a}{b} \rfloor b )x \\ & = ax + b(y - \lfloor \frac{a}{b} \rfloor x) \end{aligned}

则上述 b0b \ne 0 情况中的式子成立。

证毕。

代码

int exgcd(int a, int b, int& x, int& y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }

    int g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

通解

求出特解 x0,y0x_0, y_0 后补齐次项即可:

x=x0+bky=y0ak\begin{array}{l} x = x_0 + bk \\ y = y_0 - ak \end{array}

方程的最小整数解的 k=b/gcd(a,b)k = b / \gcd(a, b)x=(x mod k+k) mod kx = (x \bmod k + k ) \bmod k

逆元

ax1 ( mod b)ax \equiv 1 ~(\bmod~ b),且 a,ba, b 互质,则称 xxaa 的逆元,记为 a1a^{-1}

可将上式转化为:

ax+by=1(2)\tag{2} ax + by = 1

这样可以就使用扩展欧几里得算法求出 (2)(2) 式的解,xx 的最小解即为 aa 的逆元。

参考资料

  1. 第 150 ~ 151 页,0x33 同余,《算法竞赛进阶指南》(ISBN 978-7-83009-313-6,河南电子音像出版社),李煜东,2019 年 5 月第 5 次修订版。
  2. 1.3.4 扩展欧几里得算法,《信息学奥赛之数学一本通》(ISBN 978-7-5641-6576-5,东南大学出版社),林厚从,2019 年 11 月第 9 次修订版。
  3. 1.4 逆元,《信息学奥赛之数学一本通》(ISBN 978-7-5641-6576-5,东南大学出版社),林厚从,2019 年 11 月第 9 次修订版。

2022-05-06: 感谢 iBug 指出本文中的错误。