【欧几里得算法】欧几里得算法，又称辗转相除法，是求两个正整数的最大公约数（GCD）的一种经典方法。该算法由古希腊数学家欧几里得在其著作《几何原本》中提出，至今仍被广泛应用于数学、计算机科学和密码学等领域。
一、算法原理
欧几里得算法的核心思想是：两个正整数 a 和 b 的最大公约数等于 b 与 a 除以 b 的余数 r 的最大公约数。即：
$$
\gcd(a, b) = \gcd(b, a \mod b)
$$
通过不断重复这一过程，直到余数为零时，此时的非零数即为这两个数的最大公约数。
二、步骤说明
1. 给定两个正整数 a 和 b（a > b）。
2. 用 a 除以 b，得到商 q 和余数 r。
3. 将 b 作为新的 a，r 作为新的 b。
4. 重复步骤 2 和 3，直到余数为 0。
5. 此时的除数即为两数的最大公约数。
三、示例演示
以下是一个具体的例子，展示如何使用欧几里得算法求 84 和 30 的最大公约数。
| 步骤 | a | b | 余数 r = a mod b |
| 1 | 84 | 30 | 24 |
| 2 | 30 | 24 | 6 |
| 3 | 24 | 6 | 0 |
最终，余数为 0，因此最大公约数是 6。
四、算法特点
| 特点 | 描述 |
| 简单高效 | 不需要因式分解，计算速度快，适用于大数运算。 |
| 应用广泛 | 广泛用于密码学、数据压缩、分数化简等领域。 |
| 可编程实现 | 容易用程序语言（如 Python、C、Java）实现，适合自动化处理。 |
| 适用范围 | 仅适用于正整数，若涉及负数需先取绝对值。 |
五、总结
欧几里得算法是一种简洁而强大的工具，能够快速求出两个正整数的最大公约数。它不仅在数学理论中有重要地位，也在实际应用中展现出卓越的效率和实用性。掌握这一算法有助于理解更复杂的数学概念，并为后续学习如扩展欧几里得算法、模运算等打下坚实基础。
