初等数论：辗转相除法（欧几里得算法）

陈一男学习网站[ ChenYinan.com ] - 中国数学学会 - 中国院士 - GeoGebra - 数学基础

1. 辗转相除法定义和原理

定义：辗转相除法（欧几里得算法）是一种求两个整数的最大公因数的算法。

对于两个整数\(a\)和\(b\)（\(a>b\)），用\(a\)除以\(b\)得到商\(q\)和余数\(r\)，即\(a = bq + r\)（\(0\leq r < b\)），然后

把\(b\)作为新的\(a\)，\(r\)作为新的\(b\)，继续上述除法运算，直到余数为\(0\)，此时的除数就是原来两个数的最大公因数。

原理依据：因为两个整数的最大公因数等于其中较小的数和两数相除余数的最大公因数。

例如，对于\(a = 24\)，\(b = 18\)

\(24 = 18\times1+6\)，此时\((24,18)=(18,6)\)，继续计算

\(18 = 6\times3 + 0\)，所以\((24,18)=6\)。

2. 计算步骤示例

求\((48,18)\)：

首先\(48\div18 = 2\cdots\cdots12\)，此时\(a = 48\)，\(b = 18\)，商\(q = 2\)，余数\(r = 12\)。

然后把\(b = 18\)作为新的\(a\)，\(r = 12\)作为新的\(b\)，计算\(18\div12 = 1\cdots\cdots6\)。

再把\(a = 12\)，\(b = 6\)，计算\(12\div6 = 2\cdots\cdots0\)，当余数为\(0\)时，此时的除数\(6\)就是\(48\)和\(18\)的最大公因数，即\((48,18)=6\)。

3. 时间复杂度和效率

辗转相除法的时间复杂度在最坏情况下是对数级别的，即\(O(\log n)\)，其中\(n\)是两个数中的较大数。这是因为在每一步计算中，余数至少会减少一半（可以通过数学归纳法证明），所以计算步骤不会太多，相比于列举因数等方法效率更高。例如，计算两个较大的数如\(10000\)和\(9999\)的最大公因数，辗转相除法只需要几步就能得出结果，而列举因数法会非常繁琐。

4. 辗转相除法扩展应用

扩展欧几里得算法：基于辗转相除法，可以进一步得到扩展欧几里得算法。该算法不仅能求出两个整数\(a\)和\(b\)的最大公因数\(d\)，还能找到整数\(x\)和\(y\)，使得\(ax+by = d\)。这在求解线性不定方程、同余方程等问题中有广泛的应用。例如，在密码学中的RSA算法等部分环节会用到扩展欧几里得算法来求解密钥相关的方程。

分数化简：在化简分数\(\frac{a}{b}\)时，可以先通过辗转相除法求出\(a\)和\(b\)的最大公因数\(d\)，然后将分子分母同时除以\(d\)，得到最简分数。例如，对于分数\(\frac{24}{36}\)，通过辗转相除法求出\((24,36)=12\)，将分子分母同时除以\(12\)，得到最简分数\(\frac{2}{3}\)。