【辗转相除法原理】一、概述
辗转相除法，又称欧几里得算法，是一种用于计算两个正整数最大公约数（GCD）的古老而高效的数学方法。该方法由古希腊数学家欧几里得在其著作《几何原本》中提出，至今仍被广泛应用于数论、密码学和计算机科学等领域。
二、基本原理
辗转相除法的核心思想是：利用较大的数除以较小的数，然后用余数代替较大的数，重复这一过程，直到余数为零为止。此时的非零除数即为这两个数的最大公约数。
具体步骤如下：
1. 给定两个正整数 $ a $ 和 $ b $，假设 $ a > b $。
2. 用 $ a $ 除以 $ b $，得到商 $ q $ 和余数 $ r $，即 $ a = b \times q + r $。
3. 将 $ b $ 替换为新的 $ a $，将 $ r $ 替换为新的 $ b $。
4. 重复步骤 2 和 3，直到余数为零。
5. 此时的除数即为最大公约数。
三、示例说明
以求 84 和 18 的最大公约数为例：
| 步骤 | a | b | q | r |
| 1 | 84 | 18 | 4 | 12 |
| 2 | 18 | 12 | 1 | 6 |
| 3 | 12 | 6 | 2 | 0 |
最终结果：最大公约数为 6。
四、特点与优势
- 高效性：相比枚举法，辗转相除法在处理大数时效率更高。
- 适用性广：适用于所有正整数，且不依赖于因数分解。
- 算法简单：仅需基本的除法和取余操作，易于实现。
五、总结
辗转相除法是一种简洁、高效、实用的数学工具，其原理基于余数递推的思想，通过不断缩小问题规模，最终找到两个数的最大公约数。它不仅在数学领域有重要应用，在编程和实际问题解决中也具有广泛价值。
附：算法流程图（文字版）
```
开始
输入 a, b (a > b)
计算 r = a % b
如果 r == 0，则输出 b 作为 GCD
否则，将 a = b, b = r，继续循环
结束
```