欧几里得算法如何通过重复除法计算两个自然数的最大公约数？

适用条件

• 输入 $a$ 和 $b$ 是自然数。
• 反复应用除法算法。
• 当余数等于 0 时停止过程。

理解与推导

1. 从两个自然数 $a$ 和 $b$ 开始。
2. 应用除法算法：$a = bq_1 + r_1$。
3. 用 $(b, r_1)$ 替换这对数 $(a, b)$。
4. 再次应用除法算法：$b = r_1q_2 + r_2$。
5. 继续这个过程，生成一系列余数 $r_1, r_2, \dots$
6. 当某个余数 $r_n$ 为 0 时停止。
7. 将最后一个非零余数 $r_{n-1}$ 识别为 $\gcd(a, b)$。

例子

为了求 $\gcd(5295, 4321)$，算法过程如下： $5295 = 1 \cdot 4321 + 974$ $4321 = 4 \cdot 974 + 425$ $974 = 2 \cdot 425 + 124$ $425 = 3 \cdot 124 + 53$ $124 = 2 \cdot 53 + 18$ $53 = 2 \cdot 18 + 17$ $18 = 1 \cdot 17 + 1$ $17 = 17 \cdot 1 + 0$ 最后一个非零余数是 1，所以 $\gcd(5295, 4321) = 1$。

容易误解的地方

• 认为算法在第一个余数为 1 时就停止；它必须继续直到余数为 0 以正式满足停止条件，尽管达到 1 已经意味着最大公约数是 1。
• 混淆商和余数；下一步使用的是余数，而不是商。
• 认为算法要求数字是质数；它对任何自然数都有效。

观看对应讲解

相关概念

继续追问

• 为什么最后一个非零余数等于最大公约数？
• 当欧几里得算法给出最大公约数为 1 时意味着什么？
• 必须继续直到余数恰好为 0 吗？

相关问题