数论 · 扩展欧几里得算法

· · 个人记录

问题

扩展欧几里得算法是用来在已知 (a,b) 时，求解一组 (p,q)，使得

p \times a + q \times b = \gcd (a, b)

求解

exgcd的拓展应用及说明证明。

首先，解一定存在（证明略）。

其次，由 \gcd (a, b) = \gcd (b,a\bmod b) 可得：

p' \times a + q' \times b = \gcd (b, a\bmod b) = p \times b + q \times (a \bmod b) = p \times b + q \times (a - \left\lfloor\dfrac{a}{b}\right\rfloor \times b) = q \times a + (p - \left\lfloor\dfrac{a}{b}\right\rfloor \times q) \times b

注意，在这一行柿子中，p', q' 是当前求解的答案，p,q 是上一次已经求出的答案。

因为当前 exgcd 中的 a 和 b 与上一次 exgcd 中的 a 和 b 不同，所以对应的解不同。

所以，当 a 和 b 都在减小时，就可以得出 p = 1,\ q = 0。

然后递归回去的时候就可以求出最终的 p 和 q 了。

代码


inline void exgcd (int a, int b)//求解 ap + bq = gcd (a, b) 时的 p 和 q
{
    if (!b)//此时有了 gcd (a, b)
    {
        x = 1, y = 0;
        return;
    }
    exgcd (b, a % b);
    int t = x;
    x = y, y = t - a / b * y;
    //此时的 x, y 满足 ax + by = gcd (a, b)
}

——End——