什么是辗转相除法？一句话概括：

辗转相除法，又称欧几里得算法，是求两个正整数最大公约数（Greatest Common Divisor, GCD）的经典算法。其核心思想在于：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

🤔️ 是不是有点懵？没关系，我们来展开聊聊，保证让你彻底搞懂！

情景导入：分蛋糕的智慧

想象一下，你有一块长方形蛋糕，长27厘米，宽18厘米。现在你想把这块蛋糕切成大小相同的正方形小块，并且不能有剩余。那么，这个正方形小块的最大边长是多少呢？

这个问题，其实就是在求27和18的最大公约数！

手动模拟：辗转相除法的操作

1. 第一次“除”： 用较大的数（27）除以较小的数（18），得到商1和余数9。

   • 27 ÷ 18 = 1 … 9
   • 这一步，我们把问题转化成了求18和9的最大公约数。

2. 第二次“除”： 用上一步的除数（18）除以余数（9），得到商2和余数0。

   • 18 ÷ 9 = 2 … 0
   • 余数为0了！这意味着9就是18和9的最大公约数。

3. 得出结论： 因为18和9的最大公约数是9，而27和18的最大公约数等于18和9的最大公约数，所以27和18的最大公约数也是9。

因此，蛋糕能切成的最大正方形小块的边长是9厘米。

✨ 原理揭秘：为什么可以这样做？

让我们用更严谨的方式来解释一下这背后的数学原理。

假设有两个正整数 a 和 b，且 a > b。

1. 核心等式： 我们可以将 a 表示为 a = b q + r，其中 q 是商，r 是余数（0 ≤ r < b）。

2. 关键证明：

   • 假设 d 是 a 和 b 的一个公约数，那么 d 也能整除 r。（因为 r = a – b q，而 a 和 b 都能被 d 整除）
   • 反过来，假设 d 是 b 和 r 的一个公约数，那么 d 也能整除 a。（因为 a = b q + r，而 b 和 r 都能被 d 整除）
   • 这说明，a 和 b 的公约数集合 与 b 和 r 的公约数集合 完全相同！

3. 最大公约数不变性：既然公约数集合相同，那么最大的那个公约数（即最大公约数）自然也相同。也就是说，gcd(a, b) = gcd(b, r)。

4. 递推至余数为0： 通过不断重复这个过程，余数会越来越小，最终一定会变成0。当余数为0时，上一步的除数就是最大公约数。

💡 代码实现：用Python来写

“`python

def gcd(a, b):

“””

使用辗转相除法求两个数的最大公约数。

Args:

a: 第一个正整数。

b: 第二个正整数。

Returns:

两个数的最大公约数。

“””

while b:

a, b = b, a % b

return a

示例

result = gcd(27, 18)

print(f”27和18的最大公约数是：{result}”) # 输出：27和18的最大公约数是：9

result1 = gcd(48,30)

print(f”48和30的最大公约数是：{result1}”)

result2 = gcd(12345, 54321)

print(f”12345和54321的最大公约数是：{result2}”)

“`

代码解读：

• while b:：只要 b 不为0，就继续循环。
• a, b = b, a % b：同时更新 a 和 b，a 变成原来的 b，b 变成原来的余数。这步很巧妙地实现了“辗转相除”。
• return a：当 b 为0时，a 就是最大公约数。

进阶应用：不只是求最大公约数

除了求最大公约数，辗转相除法还可以稍作修改：

• 求最小公倍数（Least Common Multiple, LCM）： 两个数的最小公倍数 = 两数之积 / 最大公约数。

  lcm(a,b) = ab/gcd(a,b)

总结一下

辗转相除法，用不断求余的方式，将求两个大数的最大公约数问题，转化成求两个较小数的最大公约数问题，直至余数为零，巧妙地找到了答案。这个方法不仅高效，而且易于理解和实现，是数论中的一个经典算法。下次遇到类似问题，不妨试试这个神奇的方法吧！