歐幾里得算法（輾轉相除算法）
歐幾里得119、歐幾里得算法（輾轉相除算法）
?
2017年3月30日，網(wǎng)友發(fā)表名為《如何證明存在一種不能表示為兩個整數(shù)之比的數(shù)？》的文章。
文章內(nèi)容：
…
有人覺得奇怪了：既然當時沒有代數(shù)，古希臘人是怎么提出“所有數(shù)都可以表示為整數(shù)之比”的呢？
…代、數(shù)、代數(shù)：見《歐幾里得36》…
…比：見《歐幾里得27》…
?
其實古希臘人根本沒有提出什么整數(shù)之比，這是后人的一個誤解。當時畢達哥拉斯學派提出的，叫做“公度單位”。
…公、度、公度：見《歐幾里得24》…
…單、位、單位：見《歐幾里得116》…
?
兩條線段的公度單位，簡單的說就是找一個公度量，使得兩條線段的長度都是這個公度量的整倍數(shù)（于是這個公度量就可以同時作為兩條線段的單位長度并用于測量）。
…量：見《歐幾里得27》…
?
尋找公度量的方法相當直觀，就是不斷把較長的那個線段減去短的那個線段，直到兩個線段一樣長。
?
熟悉數(shù)論的同學一下就明白了：這就是歐幾里得的輾（zhǎn）轉相除算法求最大公約數(shù)。
…數(shù)、論、數(shù)論：見《歐幾里得15》…
…輾：身體翻來覆去地，如“～～反側”…
?
…轉：手搖動紡錘將散絲集中于一束是專的意思。車、專疊加。車輪往來回復運作行于一途是轉的意思。
?
轉：zhuǎn。
本義：遷徙（xǐ）；流亡。
衍（yǎn）義：引申指“改換方向”。如：轉彎。向左轉。
衍義：引申指“改變形勢、情況”。如：轉敗為勝、天氣轉睛、病情好轉。
?
轉：zhuàn。
衍義：引申指“旋轉”。如：車輪飛轉。
衍義：引申指“圍繞著一個中心運動”。如：繞著太陽轉。
衍義：又用作量詞，旋轉一圈為一轉。如：繞了幾十轉。
衍義：又用作量詞，古代勛（xūn）位每升一級稱“一轉”。如：“策勛十二轉，賞賜百千強?！?/p>
?
字義：[ zhuǎn ]
1.改換方向、位置、形勢、情況等：～身。～臉?！珦Q。～移。好～。向左～。向后～?！珨閯?。由陰～晴。
2.把一方的物品、信件、意見等傳到另一方：～達?！弧！?。這封信由我～給他好了。
[ zhuàn ]
1.旋轉：輪子～得很快。
2.繞著某物移動；打轉：～圈子?！珌怼?。
3.繞一圈兒叫繞一轉…
（…衍、義、衍義：見《歐幾里得25、26》…）
?
…輾轉：指反復不定，翻來覆去的樣子。出自《后漢書·來歷傳》。
?
詞義：1.也作展轉。
2.（躺在床上）翻來覆去（多指睡不著）：～不眠。
3.經(jīng)過許多人的手或經(jīng)過很多地方；間接地：～流傳…
…算、法、算法：見《歐幾里得104》…
…輾轉相除一般指歐幾里得算法…
?
歐幾里得算法：又稱輾轉相除法。用于計算兩個正整數(shù)a，b的最大公約數(shù)。
?
歐幾里得算法是用來求兩個正整數(shù)最大公約數(shù)的算法。古希臘數(shù)學家歐幾里得在其著作《The Elements》中最早描述了這種算法，所以被命名為歐幾里得算法。
…The（英語）：指已提到或易領會到的人或事物；指獨一無二的、正常的或不言而喻的人或事物…
…element（英語）：n.（名詞）要素；基本部分；典型部分…
…elements：element的復數(shù)…
[…復數(shù)：某些語言中由詞的形態(tài)變化等表示的兩個或兩個以上的數(shù)量。例如英語里book（書，單數(shù)）指一本書，books（書，復數(shù)）指兩本或兩本以上的書…]
…《The Elements》：《幾何原本》…
?
假如求1997和615兩個正整數(shù)的最大公約數(shù)，用歐幾里得算法，是這樣進行的：
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的最大公約數(shù)為1。
?
以除數(shù)和余數(shù)反復做除法運算，當余數(shù)為0時，取當前算式除數(shù)為最大公約數(shù)。所以就得出了1997和615的最大公約數(shù) 1。
?
什么叫做輾轉相除法？舉幾個例子——網(wǎng)友提問
2019-05-05，醉意撩人殤（shāng）：輾轉相除法，又名歐幾里德算法，是求最大公約數(shù)的一種方法。它的具體做法是：用較大數(shù)除以較小數(shù)，再用出現(xiàn)的余數(shù)（第一余數(shù)）去除除數(shù)，再用出現(xiàn)的余數(shù)（第二余數(shù)）去除第一余數(shù)，如此反復，直到最后余數(shù)是0為止。如果是求兩個數(shù)的最大公約數(shù)，那么最后的除數(shù)就是這兩個數(shù)的最大公約數(shù)。
?
示例：
123456和7890的最大公因數(shù)是6，這可由下列步驟（其中，“a mod b”是指取a÷b的余數(shù)）看出：
…mod：求余函數(shù)…
?
“無論兩個數(shù)多大，用輾轉相除法都可以方便的求出最大公因數(shù)。是不是很厲害！
請看下集《歐幾里得120、什么叫做輾轉相除法？舉幾個例子》”
若不知曉歷史，便看不清未來
歡迎關注嗶哩號“中國崛起呀”
