拓展欧几里得算法

拓展欧几里得算法（Extended Euclidian Algorithm），是欧几里得算法的扩展版本，用于在计算两个数的最大公约数 $\gcd(a, b)$ 的同时，找到这两个整数的 贝祖系数（即这两个整数的线性组合等于其最大公约数的系数）。

举例而言，如果给定两个整数 $a, b$ ，我们不仅可以找到这两个整数的最大公约数，还可以找到两个整数 $x, y$ ，满足：

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

与此同时，我们也将这个方程称之为 贝祖等式（Bézout's identity）。拓展欧几里得算法在数论和计算机应用方面有着极其突出的贡献和广泛的应用。例如求解线性同余方程，本文也将会围绕求解同余方程来展开。

线性同余方程

线性同余方程指的是形如 $ax \equiv b \pmod m$ 的方程，其中 $a$ 和 $b$ 表示两个已知的整数常量， $x$ 是需要求解的未知整数，符号 $\equiv$ 表示同余关系，即等式两边同时对 $m$ 取模结果相同。

具体地说，线性同余方程要求找到一个整数 $x$ ，使得 $ax$ 除以 $m$ 所得的余数等于 $b$ ，或者说 $ax$ 与 $b$ 对 $m$ 取余后余数相等。该类型的问题通常存在唯一的解或者无解。

拓展欧几里得算法过程推导

拓展欧几里得算法与普通的欧几里得算法相同，都可以通过递归的方式来非常简便地计算出结果。

假设有两个非负整数 $a$ 和 $b$ （在满足 $a \le b$ 的情况下），设 $r = a \mod b$ ，那么根据欧几里得算法可以得出结论 $\gcd(a, b) = \gcd(b, r)$ 。根据欧几里得算法的推到过程，可以得到：

$bx_1 + ry_1 = \gcd(b, r)$

因为 $r = a - \left\lfloor\frac{a}{b}\right\rfloor b$ ，所以代入推出：

$\gcd(a, b) = bx_1 + (a - \left\lfloor\frac{a}{b}\right\rfloor b)y_1$

经过化简可以得到：

$\gcd(a, b) = ay_1 + b(x_1 - \left\lfloor\frac{a}{b}\right\rfloor y_1)$

由此可以看出， $x = y_1$ 和 $y = x_1 - \left\lfloor\frac{a}{b}\right\rfloor y_1$ 是符合原式的贝祖系数。

拓展欧几里得算法代码

int extended_gcd(int a, int b, int &x, int &y) {
    if (a == 0) {
        x = 0, y = 1;
        return b;
    }
    int x1, y1;
    int gcd = extended_gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return gcd;
}

参考上述代码，extended_gcd 函数接受两个整数 $a$ 和 $b，$ 并计算它们的最大公约数，并通过引用参数 $x$ 和 $y$ 返回贝祖系数。

拓展欧几里得算法​

线性同余方程​

拓展欧几里得算法过程推导​

拓展欧几里得算法代码​

相关引用​

拓展欧几里得算法

线性同余方程

拓展欧几里得算法过程推导

拓展欧几里得算法代码

相关引用