欧几里得算法是如何工作的？

Question

我在我的讲义笔记中找到了一个计算最大公约数的算法：

public static int gcd( int a, int b ) {
    while (b != 0) {
        final int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

所以r是将a除以b所得余数（获取模数）。然后将b赋值给a，并将余数赋值给b，最后返回a。我一直都不明白这个算法是如何工作的！

而且，显然这个算法并不适用于所有情况，必须使用以下算法：

public static int gcd( int a, int b ) {
    final int gcd;
    if (b != 0) {
        final int q = a / b;
        final int r = a % b; // a == r + q * b AND r == a - q * b.
        gcd = gcd( b, r );
    } else {
        gcd = a;
    }
    return gcd;
}

我不理解这背后的原因。我通常能理解递归并且擅长Java，但是这个问题困扰着我。请帮我一下？

- John Curtsy

---

你尝试过谷歌搜索吗？这里有一个好的解释：http://en.wikipedia.org/wiki/Euclidean_algorithm。 - Luc M

Answer 1

维基百科中有相关解释，但不易立刻找到（并且算法流程和证明并不能总是回答“为什么它起作用”的问题）。

基本上这归结于两个整数a、b（假设a>=b），它们一定可以写成a=bq+r，其中r

如果d=gcd(a,b)，那么我们可以将a=ds和b=dt，因此得到ds=qdt+r。因为左边可以被d整除，所以右边也必须被d整除。而且由于qdt是可被d整除的，所以得出结论：r也必须被d整除。

总结一下：我们有a=bq+r，其中r

因为a >= b > r，我们有两种情况：

1. 如果r = 0，则a = bq，因此b同时被b和a整除，故gcd(a,b)=b。 2. 否则(r > 0)，我们可以将寻找gcd(a,b)的问题简化为寻找gcd(b,r)，它们是完全相同的数字（因为a、b和r都可被d整除）。

为什么这是简化呢？因为r

现在，r = a % b，这就解释了你所看到的代码。

- Omri Barel

---

@Luc - 这是什么意思？当然不是数学中所有的证明都是建设性的。哥德尔的不完备定理是关于为什么某些东西“不起作用”的问题。 - Ted Hopp

我理解a、b和r都有d作为因子。但是你怎么知道d是b和r的最大公约数？难道b和r不可能有另一个大于gcd(a，b)的因子吗？ - Mohsin Kale

让我们来看看：假设 gcd(b, r) = w > gcd(a, b)。所以我们可以写成 b=wu 和 r=wv。现在 a = bq + r，所以 a = wuq + wv。因此，a 可以被 w 整除。b 也可以被 w 整除。因此，我们找到了一个大于 gcd(a, b) 的 a 和 b 的公共因子。这是个矛盾。 - Omri Barel

Answer 2

它们是等价的。首先要注意的是第二个程序中的q根本没有被使用。另一个区别只是迭代和递归。

至于为什么它有效，上面链接的维基百科页面很好。特别是第一幅插图直观地传达了“为什么”，然后下面的动画说明了“如何”。

- Amadan

Answer 3

这是一篇有趣的博客文章：Tominology。

在这里，我们讨论了欧几里得算法背后的很多直觉，它是用JavaScript实现的，但我相信如果有人想要，将代码转换为Java并不难。

- Marco

Answer 4

鉴于 'q' 从未被使用，我并没有看到您普通的迭代函数和递归迭代函数之间的区别...两者都执行相同的操作。

gdc(first number, second number)
  as long as (second number > 0) {
      int remainder = first % second;
      gcd = try(second as first, remainder as second);
  }
}

除了尝试将其应用于非整数的情况下，这个算法在哪些情况下会失败？

（还可以参见http://en.wikipedia.org/wiki/Euclidean_algorithm获取更详细的信息）

- Mike 'Pomax' Kamermans

Answer 5

这里是我找到的非常有用的解释。

对于那些懒得打开它的人，这就是它所说的：

考虑一个例子，当你需要找到(3084,1424)的最大公约数时。假设d是最大公约数。这意味着d | 3084和d | 1424（使用符号'|'表示“除以”）。

由此可见，d | (3084 - 1424)。现在我们将尽可能减少这些可被d整除的数字（在本例中为3084和1024），以便我们达到其中一个数字为0。请记住，GCD（a，0）是a。

由于d | (3084 - 1424)，因此d | (3084 - 2(1424))，这意味着d | 236。
提示：（3084-2 * 1424 = 236）

现在忘掉最初的数字，我们只需要解决d的问题，我们知道d是能够整除236、1424和3084的最大数。因此，我们使用较小的两个数字进行计算，因为这样可以将问题收敛到0。

d | 1424 和 d | 236 意味着 d | (1424 - 236)。
因此，d | ( 1424 - 6(236) ) => d | 8.

现在我们知道d是能够整除8、236、1424和3084的最大数。再次取较小的两个数字，我们有

d | 236 和 d | 8，这意味着 d | (236 - 8)。
因此，d | ( 236 - 29(8) ) => d | 4。

列表中可被d整除的数字增加并收敛（数字越来越小，接近0）。目前为止，d是能够整除4、8、236、1424和3084的最大数。

采取同样的步骤，

d | 8 和 d | 4 意味着 d | (8-4)。
因此，d | (8-2(4)) => d | 0。

现在可被 d 整除的数字列表为 0、4、8、236、1484、3084。 (a, 0) 的 GCD 总是 a。因此，只要你有其中一个数字为 0，另一个数字就是原始两个数字及其之间所有数字的 GCD。

这正是您的代码所做的。您可以将终止条件识别为 GCD(a, 0) = a。

另一步是找到两个数字的余数，并选择前两个数字中较小的数字作为新数字。

- Prateek