【辗转相除法原理】在数学中，辗转相除法（又称欧几里得算法）是一种用于求解两个正整数最大公约数（GCD）的经典方法。该方法基于一个基本的数学原理：两个整数的最大公约数等于其中较小的数与两数之差的最大公约数。通过不断重复这一过程，最终可以得到两个数的最大公约数。
一、原理概述
辗转相除法的核心思想是：
> 用较大的数除以较小的数，然后用余数代替较大的数，继续进行除法运算，直到余数为零，此时的除数即为两数的最大公约数。
这个过程可以形象地理解为“反复取余”，直到余数为零为止。
二、步骤总结
以下是辗转相除法的基本操作步骤：
| 步骤 | 操作说明 |
| 1 | 输入两个正整数 a 和 b，假设 a > b |
| 2 | 用 a 除以 b，得到商 q 和余数 r（即 a = b × q + r） |
| 3 | 将 b 作为新的 a，r 作为新的 b |
| 4 | 重复步骤 2 和 3，直到余数 r 为 0 |
| 5 | 当余数为 0 时，当前的除数就是最大公约数 |
三、示例演示
以求 48 和 18 的最大公约数为例：
| 步骤 | a | b | q | r | 说明 |
| 1 | 48 | 18 | 2 | 12 | 48 ÷ 18 = 2 余 12 |
| 2 | 18 | 12 | 1 | 6 | 18 ÷ 12 = 1 余 6 |
| 3 | 12 | 6 | 2 | 0 | 12 ÷ 6 = 2 余 0 |
| 4 | - | - | - | - | 余数为 0，结束 |
结果： 最大公约数为 6
四、特点与优势
- 高效性：即使对于非常大的数字，也能快速计算出 GCD。
- 简洁性：只需要简单的除法和取余操作，易于编程实现。
- 通用性：适用于所有正整数，且不依赖于质因数分解。
五、应用领域
- 数论研究
- 密码学（如 RSA 算法）
- 分数化简
- 多项式因式分解
六、总结
辗转相除法是一种简单而强大的算法，能够高效地求出两个正整数的最大公约数。其原理清晰、步骤明确，广泛应用于数学和计算机科学领域。掌握这一方法不仅有助于理解数论的基础知识，也为后续学习更复杂的算法打下坚实基础。
