【—公約數的點】輾轉相除法是古希臘求兩個正整數的最大公約數的，也叫歐幾里德算法。

　　公約數

　　能夠整除一個整數的整數稱為其的約數(如5是10的約數);

　　能夠被一個整數整除的整數稱為其的倍數(如10是5的倍數);

　　如果一個數既是數A的約數，又是數B的約數，稱為A,B的公約數，A,B的公約數中最大的一個(可以包括AB自身)稱為AB的最大公約數[1]

　　定義

　　如果有一個自然數a能被自然數b整除，則稱a為b的倍數，b為a的約數。幾個自然數公有的約數，叫做這幾個自然數的公約數。公約數中最大的一個公約數，稱為這幾個自然數的最大公約數。

　　例： 在2、4、6中，2就是2，4，6的最大公約數。

　　輾轉相除法使用到的原理很聰明也很簡單，假設用f(x, y)表示x，y的最大公約數，取k = x/y，b = x%y，則x = ky + b，如果一個數能夠同時整除x和y，則必能同時整除b和y;而能夠同時整除b和y的數也必能同時整除x和y，即x和y的公約數與b和y的公約數是相同的，其最大公約數也是相同的，則有f(x, y)= f(y, x%y)(y > 0)，如此便可把原問題轉化為求兩個更小數的最大公約數，直到其中一個數為0，剩下的另外一個數就是兩者最大的公約數。

　　例如，12和30的公約數有：1、2、3、6，其中6就是12和30的最大公約數。

　　其方法是用較大的數除以較小的數，上面較小的除數和得出的余數構成新的一對數，繼續(xù)做上面的除法，直到出現(xiàn)能夠整除的兩個數，其中較小的數(即除數)就是最大公約數。以求288和123的最大公約數為例，操作如下：

　　288÷123=2余42

　　123÷42=2余39

　　42÷39=1余3

　　39÷3=13

　　所以3就是288和123的最大公約數。

　　其實早在公元前300年左右，歐幾里得就在他的著作《幾何原本》中給出了高效的解法——輾轉相除法。

本文來自：逍遙右腦記憶 http://www.portlandfoamroofing.com/chuzhong/241257.html

相關閱讀：初三數學學習要做好課前自學準備