辗转相减法求最大公约数的正确性与有限步终止性证明问询

一、正确性证明 #

辗转相减法的核心逻辑是：对任意非负整数对 (a, b)，若 a ≥ b，则 gcd(a, b) = gcd(b, a - b)。

• 若 d 是 a 和 b 的公约数，即 d 能整除 a 且 d 能整除 b，那么 d 必然能整除 a - b（整数的线性组合仍可被公约数整除），因此 d 也是 b 和 a - b 的公约数。
• 反之，若 d 是 b 和 a - b 的公约数，即 d 能整除 b 且 d 能整除 a - b，那么 d 必然能整除 b + (a - b) = a，因此 d 也是 a 和 b 的公约数。

由此可知，(a, b) 的公约数集合与 (b, a - b) 的公约数集合完全一致，它们的最大公约数自然相等。重复执行减法操作，最终会得到形如 (g, 0) 的数对，其中 g 就是原数对的最大公约数，这就证明了辗转相减法的正确性。

二、有限终止性证明 #

要证明辗转相减法必然在有限步内终止，只需观察每次操作后数对的变化规律：

• 假设处理的是非负整数对 (a, b)，不妨设 a ≥ b > 0。每次操作后得到新数对 (b, a - b)，新数对的两个数均为非负整数，且它们的和为 b + (a - b) = a，比原数对的和 a + b 更小（因为 b > 0）。
• 正整数的和是严格递减的，而正整数集合满足良序原理（任意非空正整数子集必有最小元素），因此这个递减的和序列不可能无限延续，必然会在有限步后出现其中一个数为 0 的情况。当数对变为 (g, 0) 时，操作终止，g 即为原数对的最大公约数。

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