辗转相除法这一名称来源于其独特的计算过程，其历史可追溯至古希腊数学巨匠欧几里得的经典著作《几何原本》。因此，该算法也享有欧几里得算法（Euclidean algorithm）的美誉。在《几何原本》这部不朽的数学文献中，第七卷详细阐述了这一算法，并在后续的多个命题中得到了广泛应用。
作为历史上最早被系统记录并广泛传播的计算方法之一，欧几里得算法专门用于求解两个非负整数之间的最大公约数（GCD）。这一算法不仅彰显了欧几里得在数学逻辑方面的卓越洞察力，同时也是算法发展史上的重要里程碑，对后来的算术理论以及数论研究产生了不可磨灭的影响。
在数学除法的基本框架中，余数与商是两个核心概念。当我们进行除法运算时，即将一个数（被除数）除以另一个数（除数），所得结果通常包含整数部分的商以及可能的余数部分。
- 被除数（Dividend）: a
- 除数（Divisor）: b
- 商（Quotient）: q
- 余数（Remainder）: r
用数学表达式可以精确描述为：a = b × q + r，其中 q 代表整数商，b 为非零整数，且余数 r 满足 0 ≤ r < b 的条件。
辗转相除法的核心原理在于：两个整数的最大公约数在运算过程中保持不变，即便将较大数减去较小数后，所得差值与较小数之间的最大公约数依然保持一致。以下是该算法的具体实施步骤：
- 首先设定两个正整数 a 和 b ，并确保 a 大于 b 。
- 运用 a 除以 b 的运算，得到余数 r (要求 0 < r < b) 。
- 如果余数 r 等于 0 ，则表明 b 即为这两个数的最大公约数。
- 如果余数 r 不等于 0 ，则将 a 更新为 b 的值，将 b 更新为 r 的值，并重新执行第二步。
这一过程将循环执行，每次迭代都会产生一个更小的正整数，直至余数最终为零，此时 b 的值即为所求的最大公约数。
算法实例演示
为了更直观地理解这一算法，我们通过一个具体实例进行说明：如何计算 252 和 198 这两个数的最大公约数。
- 252 = 1 × 198 + 54
- 198 = 3 × 54 + 36
- 54 = 1 × 36 + 18
- 36 = 2 × 18 + 0
由此可见，252 和 198 的最大公约数确实为 18 。
算法有效性证明
为了深入理解辗转相除法为何能够有效求解最大公约数，我们可以进行严谨的数学证明。假设有两个正整数 a 和 b，且满足 a > b ，根据算法原理有 a = q b + r 。设这两个数的最大公约数为 d₀ ，即 d₀ = (a, b) ，同时 d₁ = (r, b) ，我们的目标是证明 d₀ = d₁ 。
证明 d₀ 整除 r :
由于 r = a – q b ，任何能够同时整除 a 和 b 的数也必然能够整除 r 。
假设存在一个整数 c ，该整数同时整除 a 和 b 。根据整除性的定义，我们可以表示为 a = c ⋅ m, b = c ⋅ n ，其中 m 和 n 均为整数。因此： r = c ⋅ (m – q ⋅ n)
由此可见，由于 d₀ 是 a 和 b 的最大公约数，它必然也整除 r 。这意味着 d₀ 是 r 和 b 的一个公约数。
证明 d₀ ≤ d₁ :
由于 d₀ 是 r 和 b 的公约数，而 d₁ 作为 r 和 b 的最大公约数，显然有 d₀ ≤ d₁ 。
证明 d₁ 整除 a :
同理，任何能够整除 r 和 b 的数也必然能够整除 a （这是因为 a = q b + r ，所以 a 可以表示为 r 和 b 的线性组合）。
因此 d₁ 也是 a 和 b 的一个公约数。
证明 d₁ ≤ d₀ :
由于 d₁ 是 a 和 b 的公约数，而 d₀ 作为 a 和 b 的最大公约数，因此 d₁ 必须满足 d₁ ≤ d₀ 。
结论阐述</strong.EditValue