辗转相除法求最大公约数 辗转相除法 | 最大公约数 | 连分数

比如a=24，b=18，那么(A，b)= 6。所以A和B的最小公倍数是24乘以18再除以6得到72。

当最大公约数用旋转和相位的除法计算时，可以得到以这两个数为分子分母的分数的连续分数表示。这个很重要，这么多概念都是相通的。

下图是上述过程的可视化表示:

注意，上面的连续分数中有一个很有趣的现象:如果你计算上图中的连续分数，结果必须回到50/21，也就是说你必须得到缩减分数(分子和分母只有1作为它们的共同因子分数)，但是你不会得到300/126，虽然300/126和50/21是相等的，连续分数表达式也是一样的。

因为一个有理数可以用p/q的形式表示，所以twitter和phase的划分可以在有限步之后完成，也就是说有理数可以用有限连续分数的形式表示。

建议用笔在纸上练习捻转和捻转的划分。一定要多练习，获得感性认知，再上升到理性思考。

无理数也可以用连续分数的形式表示，必须是无限连续的分数。这个无理数可以用无穷连续分数的渐近分数来近似，可以精确到你想要的任何精度。比如π可以用无限连续分数表示。π的分数表示为:

π的连续分数表示为:

π的渐近分数越来越精确；

(祖冲之的近似比例和密度包含在上述公式中)。理论上可能很难得到π的连续分数。我们能做的就是从我们已经知道的π的小数表示(精确到几十万位小数)中得到π的连续小数表示。依然是辗转反侧的分裂。扭除不仅可以用在两个整数之间，也可以用在无限无环小数和整数之间。下面，我们给出一个把π表示为连续分数的简单过程。小数位数越多，连续分数的偏商越精确。下图所示的精度可以使其正确得到连续得分的前八商。

旋转除法，也称为欧几里德算法，出现在《几何元素》的第七章。以上述300/126为例，欧氏算法如下:

因为优美的乐谱占用空间太大，所以有两种简单的写法，比如:

在上面倒数第二个写法中，第二个加号“+”必须写在分母之间，这意味着它实际上是一个连续分数。而上面最后一个方括号叫做连续分数的偏商表示，是最简单的。注意，以上三种写法是相通的，应该可以从一种推导出另外两种写法。

下一期可能需要介绍无理数(1+根式5)/2，也就是黄金分割比(大PHI)是如何表示成连续分数(最简单干净的连续分数)的，并介绍它与斐波那契数列的关系。