最古老的一种算法揭秘：辗转相除法为何能准确求出最大公约数？

最古老的一种算法揭秘：辗转相除法为何能准确求出最大公约数？

引用

网易

1.

https://www.163.com/dy/article/J7V5MRR405369M9C.html

辗转相除法，又称欧几里得算法，是人类历史上最早被系统记录并流传下来的算法之一。这一算法不仅展示了古希腊数学家欧几里得对数学逻辑的深刻理解，而且对算术和数论产生了深远的影响。本文将带你深入了解这一古老算法的原理、证明及其在数学中的应用。

基础概念

在数学除法中，余数和商是两个最重要的概念。当我们将一个数（被除数）除以另一个数（除数）时，得到的结果通常包含商和可能的余数。

• 被除数（Dividend）: a
• 除数（Divisor）: b
• 商（Quotient）: q
• 余数（Remainder）: r

数学表达式可以写作：a = b × q + r，其中 q 为整数， b 为非零整数，且 0 ≤ r < b。

算法原理

辗转相除法的基本原理是：两个整数的最大公约数不变，当较大数减去较小数后，得到的差值与较小数的最大公约数相同。以下是算法的步骤：

1. 设两个正整数 a 和 b ，且 a > b 。
2. 用 a 除以 b ，得到余数 r (0 < r < b) 。
3. 如果 r 为 0 ，则 b 即为两数的最大公约数。
4. 如果 r ≠ 0 ，则令 a = b ， b = r ，并返回第二步。

这个过程将不断重复，每次都会产生一个更小的正整数，直到余数为 0 ，此时的 b 就是最大公约数。

算法示例

通过一个例子来说明这一算法：如何找到 252 和 198 的最大公约数。

1. 252 = 1 × 198 + 54
2. 198 = 3 × 54 + 36
3. 54 = 1 × 36 + 18
4. 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₀ = d₁ 。这说明使用辗转相除法，即使在每次迭代中 a 和 b 被更新为较小的数，最大公约数仍然保持不变，直到找到最终解。

应用领域

除了最大公约数的计算，辗转相除法在数学的其他领域也有广泛的应用，如在数论中用于求解线性丢番图方程，以及在密码学中用于RSA加密算法的实现等。