在 c++ 中扩展欧几里得算法的递归中究竟发生了什么？

Question

我知道什么是扩展欧几里得算法以及为什么在编程中使用它。对于查找数字的反模，这是一种非常有用的算法。我知道如何在 c++ 中实现它，这就是我在下面的 c++ 中实现它的方式。

typedef pair<int, int> pii;
#define x first
#define y second
pii extendedEuclidean(int a, int b)
{
    if(b==0)
        return {a,0};
    else {
        pii d = extendedEuclidean(b, a%b);
        return {d.y, d.x - (d.y*(a/b))};
    }
}

现在，如果我想找到一个数字的反模，例如 13，其中 mod 例如 1000007，那么我只需通过以下方式调用此函数

pair<int, int> res = extendedEuclidean(13, 1000007);

那么结果是

res.first

我的问题是为什么以及在这个递归中究竟发生了什么？以及为什么它会产生正确的结果。

注意：这里的gcd（a， b）必须是1。

Answer 1

欧几里得算法计算一对数的最大公约数(a, b)（假设a>b）。它使用观察，即a和b的任何公约数也是a-b的除数。原因如下：

让d成为除数。然后，对于整数k，a可以表示为a=d*k，对于整数l，b=d*l表示。然后，a-b=d*k-d*l=d*(k-l). k-l又是一个整数。因此，d必须是a-b的除数。

该算法所做的是尽可能多地从较大的数字中减去较小的数字。这是a%b的部分。例如，如果a = 25和b = 7，a%b=4是从a中减去b 3次后得到的。之后，新a将小于b。因此，您交换两个数字。这是您调用递归的部分：extendedEuclidean(b, a%b);

扩展的欧几里得算法做得更多。此外，它计算两个数x和y，使得gcd(a, b) = x * a + y * b。这是它是如何完成的：

在最后一次迭代中，您最终会得到 a'=gcd 和 b'=0 .因此，你有gcd=a' * 1 + b' * 0，其中1和0分别是x'和y'。假设上一次迭代中的值是 a'' 和 b'' 。然后我们知道a'=b''和b'=a'' % b''.有了这个，我们发现b'=a''-(a''/b'')*b''（尽可能多地减去）。我们可以修改

gcd = a' * x' + b' * y'
gcd = b'' * x' + (a''-(a''/b'')*b'') * y'
    = a'' * y' + b'' * (x' - y' * (a''/b''))

因此，新的x''=y'和y''=x' - y' * (a''/b'').这是您的退货声明return {d.y, d.x - (d.y*(a/b))};。

举个例子：

让a=25, b=7.第一遍计算列a和b列（从上到下）。这说明了递归调用。第二遍计算列x和y列（从下到上）。这说明了返回语句：

 a  | b            |  x   | y                     | means
----+--------------+------------------------------+---------------------
 25 |  7           |  2   | -1 - 2 * (25/7) = -7  | 1 = 2 * 25 - 7 * 7 
  7 |  25 % 7 = 4  | -1   |  1 + 1 * (7/4)  =  2  | 1 = (-1) * 7 + 2 * 4
  4 |  7 % 4  = 3  |  1   |  0 - 1 * (4/3)  = -1  | 1 = 1 * 3 - 1 * 3
  3 |  4 % 3  = 1  |  0   |  1 - 0 * (3/1)  =  1  | 1 = 0 * 3 + 1 * 1
  1 |  3 % 1  = 0  |  1   |  0                    | 1 = 1 * 1 + 0 * 0

所以你会得到1 = 2 * 25 - 7 * 7，2是结果的.first，-7是结果的.second。如果我们在 mod 25 ，这简化为：

1 == 2 * 0 - 7 * 7
1 == -7 * 7

因此，-7 == 18（result.second）是7 (mod 25)的乘法逆。请注意，我交换了输入以避免不必要的第一次迭代。否则，它是result.first.