扩展欧几里得与模逆元

一句话说明

扩展欧几里得不只是求 gcd(a,b)，而是顺手求出一组 x,y，使得 ax + by = gcd(a,b)。

什么时候该想到它

• 要求模逆元，但模数不一定是质数
• 要解 ax + by = c
• 要解线性同余方程
• 想同时拿到 gcd 和系数解

为什么它成立

普通欧几里得用了：

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

而：

a mod b = a - floor(a/b) * b

所以如果子问题已经知道：

g = b*x1 + (a mod b)*y1

代回去就能得到：

g = a*y1 + b*(x1 - floor(a/b)*y1)

于是：

• x = y1
• y = x1 - (a/b)*y1

Go 模板：扩展欧几里得

func Exgcd(a, b int) (g, x, y int) {
    if b == 0 {
        return a, 1, 0
    }
 
    g, x1, y1 := Exgcd(b, a%b)
    x = y1
    y = x1 - (a/b)*y1
    return g, x, y
}

Go 模板：模逆元

如果 gcd(a, m) = 1，那么 a 在模 m 下存在逆元。

func ModInverse(a, m int) int {
    g, x, _ := Exgcd(a, m)
    if g != 1 {
        return -1
    }
    x %= m
    if x < 0 {
        x += m
    }
    return x
}

为什么 x 就是逆元

因为当 gcd(a,m)=1 时，扩展欧几里得会给出：

ax + my = 1

两边对 m 取模：

ax ≡ 1 (mod m)

所以 x 就是逆元。

一个很实用的结论

模逆元存在的前提是：

gcd(a, m) = 1

如果不互质，就别再往“除法取模”上硬做了。

易错点

扩展欧几里得与模逆元最容易错的地方

• 回推公式里 x 和 y 很容易写反。
• 最终逆元要规范到 0..m-1 范围。
• 只有互质时逆元才存在。

复杂度

指标	复杂度
时间复杂度	O(log min(a,b))
空间复杂度	递归写法 O(log min(a,b))

相关笔记

• 同余与模运算
• 组合数取模与Lucas定理

---

返回：数学算法