Great question! Let's break down exactly how we can build the Euclidean algorithm from that fundamental gcd property you mentioned.

1. 先回顾核心结论 #

首先，我们把已知的关键结论放在最前面，方便后续推导：

当存在非负整数r满足 a = bq + r 时，gcd(a, b) = gcd(b, r)

这是欧几里得算法的核心支柱——它让我们在不改变最终最大公约数结果的前提下，把求解问题的数字规模一步步缩小。

2. 算法的核心思路 #

欧几里得算法的本质就是反复套用这个结论，让我们处理的数字越来越小，直到出现可以直接得出结果的终止条件。具体逻辑如下：

• 从两个正整数 a 和 b 开始（为了方便，我们先假设 a ≥ b；如果不是，直接交换两者即可，因为 gcd(a,b)=gcd(b,a)）。
• 用带余除法写出 a = bq₁ + r₁，其中 0 ≤ r₁ < b。根据核心结论，gcd(a,b) = gcd(b, r₁)。
• 接下来把 b 和 r₁ 作为新的输入，重复操作：写出 b = r₁q₂ + r₂，其中 0 ≤ r₂ < r₁，此时 gcd(b, r₁) = gcd(r₁, r₂)。
• 持续重复这个过程：每次用前一步的除数作为新的被除数，余数作为新的除数，让问题规模不断缩小。
• 当余数变为0时停止。此时剩下的非零数字就是原始 a 和 b 的最大公约数。

3. 为什么余数为0时就能终止？ #

我们看终止前的最后一步：假设此时有 rₙ₋₁ = rₙqₙ₊₁ + 0，这说明 rₙ 能整除 rₙ₋₁。再套用核心结论：
gcd(rₙ₋₁, rₙ) = gcd(rₙ, 0)
而任何数字和0的最大公约数就是这个数字本身（因为所有数都能整除0，而 rₙ 的最大约数就是它自己）。所以 gcd(rₙ, 0) = rₙ，这个 rₙ 就是之前所有数对的最大公约数——包括最初的 a 和 b。

4. 具体示例演示 #

我们用 gcd(48, 18) 来走一遍流程，更直观地理解：

1. 48 = 18×2 + 12 → gcd(48,18) = gcd(18,12)
2. 18 = 12×1 + 6 → gcd(18,12) = gcd(12,6)
3. 12 = 6×2 + 0 → 余数为0，此时 gcd(12,6) = 6，所以 gcd(48,18) = 6。

5. 算法伪代码实现 #

下面是简单的伪代码，几乎可以直接翻译成任何编程语言：

function euclidean_gcd(a, b):
    while b != 0:
        temp = b
        b = a % b  # 计算a除以b的余数r
        a = temp
    return a

这个循环完全遵循了我们的推导步骤：每次把 a 替换成之前的 b，b 替换成余数，直到 b 为0，最终返回的 a 就是最大公约数。

内容的提问来源于stack exchange，提问作者Zhenqing Xu