欧几里得119、欧几里得算法（辗转相除算法）

 

2017年3月30日，网友发表名为《如何证明存在一种不能表示为两个整数之比的数？》的文章。

 

文章内容：

…

有人觉得奇怪了：既然当时没有代数，古希腊人是怎么提出“所有数都可以表示为整数之比”的呢？

…代、数、代数：见《欧几里得36》…

…比：见《欧几里得27》…

 

其实古希腊人根本没有提出什么整数之比，这是后人的一个误解。当时毕达哥拉斯学派提出的，叫做“公度单位”。

…公、度、公度：见《欧几里得24》…

…单、位、单位：见《欧几里得116》…

 

两条线段的公度单位，简单的说就是找一个公度量，使得两条线段的长度都是这个公度量的整倍数（于是这个公度量就可以同时作为两条线段的单位长度并用于测量）。

…量：见《欧几里得27》…

 

寻找公度量的方法相当直观，就是不断把较长的那个线段减去短的那个线段，直到两个线段一样长。

 

熟悉数论的同学一下就明白了：这就是欧几里得的辗（zhn）转相除算法求最大公约数。

…数、论、数论：见《欧几里得15》…

…辗：身体翻来覆去地，如“～～反侧”…

 

…转：手摇动纺锤将散丝集中于一束是专的意思。车、专叠加。车轮往来回复运作行于一途是转的意思。

 

转：zhun。

本义：迁徙（x）；流亡。

衍（yn）义：引申指“改换方向”。如：转弯。向左转。

衍义：引申指“改变形势、情况”。如：转败为胜、天气转睛、病情好转。

 

转：zhuàn。

衍义：引申指“旋转”。如：车轮飞转。

衍义：引申指“围绕着一个中心运动”。如：绕着太阳转。

衍义：又用作量词，旋转一圈为一转。如：绕了几十转。

衍义：又用作量词，古代勋（xn）位每升一级称“一转”。如：“策勋十二转，赏赐百千强。”

 

字义：[ zhun ]

1.改换方向、位置、形势、情况等：～身。～脸。～换。～移。好～。向左～。向后～。～败为胜。由阴～晴。

2.把一方的物品、信件、意见等传到另一方：～达。～交。～送。这封信由我～给他好了。

[ zhuàn ]

1.旋转：轮子～得很快。

2.绕着某物移动；打转：～圈子。～来～去。

3.绕一圈儿叫绕一转…

（…衍、义、衍义：见《欧几里得25、26》…）

 

…辗转：指反复不定，翻来覆去的样子。出自《后汉书·来历传》。

 

词义：1.也作展转。

2.（躺在床上）翻来覆去（多指睡不着）：～不眠。

3.经过许多人的手或经过很多地方；间接地：～流传…

…算、法、算法：见《欧几里得104》…

…辗转相除一般指欧几里得算法…

 

欧几里得算法：又称辗转相除法。用于计算两个正整数a，b的最大公约数。

 

欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法，所以被命名为欧几里得算法。

…The（英语）：指已提到或易领会到的人或事物；指独一无二的、正常的或不言而喻的人或事物…

…element（英语）：n.（名词）要素；基本部分；典型部分…

…elements：element的复数…

[…复数：某些语言中由词的形态变化等表示的两个或两个以上的数量。例如英语里book（书，单数）指一本书，books（书，复数）指两本或两本以上的书…]

…《The Elements》：《几何原本》…

 

假如求1997和615两个正整数的最大公约数，用欧几里得算法，是这样进行的：

1997/615=3（余152）

615/152=4（余7）

152/7=21（余5）

7/5=1（余2）

5/2=2（余1）

2/1=2（余0）

至此，1997与615的最大公约数为1。

 

以除数和余数反复做除法运算，当余数为0时，取当前算式除数为最大公约数。所以就得出了1997和615的最大公约数 1。

 

什么叫做辗转相除法？举几个例子——网友提问

 

2019-05-05，醉意撩人殇（shng）：辗转相除法，又名欧几里德算法，是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

 

示例：

123456和7890的最大公因数是6，这可由下列步骤（其中，“a mod b”是指取a÷b的余数）看出：

…mod：求余函数…

 

“无论两个数多大，用辗转相除法都可以方便的求出最大公因数。是不是很厉害！

请看下集《欧几里得120、什么叫做辗转相除法？举几个例子》”

若不知晓历史，便看不清未来

欢迎关注博客"人性的游戏"或微博"人性的游戏"