【—公約數(shù)的點(diǎn)】輾轉(zhuǎn)相除法是古希臘求兩個(gè)正整數(shù)的最大公約數(shù)的，也叫歐幾里德算法。

　　公約數(shù)

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

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

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

　　定義

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

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

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

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

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

　　288÷123=2余42

　　123÷42=2余39

　　42÷39=1余3

　　39÷3=13

　　所以3就是288和123的最大公約數(shù)。

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

本文來自：逍遙右腦記憶 http://www.yy-art.cn/chuzhong/241257.html

相關(guān)閱讀：初三數(shù)學(xué)學(xué)習(xí)要做好課前自學(xué)準(zhǔn)備