数形结合理解辗转相除法

为什么叫"辗转相除法"？

这个算法源于古希腊数学家欧几里得，其核心思想是：

"用较小数除较大数，再用余数去除除数，反复进行，直到余数为0，最后的除数就是最大公因数。"

几何意义：长方形切割

假设有一个长A、宽B的长方形（A > B）：

1. 用边长为B的正方形尽可能多地填充长方形
2. 剩下的部分是一个小长方形（宽为余数）
3. 对这个小长方形重复这个过程
4. 直到能完全用正方形填满，这个正方形的边长就是最大公因数

数学公式表达

GCD(A, B) = GCD(B, A mod B)

其中 A mod B 表示 A 除以 B 的余数。

为什么这样能得到最大公因数？

因为如果 d 是 A 和 B 的公因数，那么 d 也一定是 (A - kB) 的公因数，其中 k 是整数。

所以 A 和 B 的公因数集合与 B 和 (A mod B) 的公因数集合完全相同！