最大公因數(shù)（最大公因數(shù)的前世今生）

最大公因數(shù)（Greatest Common Divisor），也稱最大公約數(shù)、最大公因子，指兩個(gè)或多個(gè)整數(shù)共有因數(shù)中最大的一個(gè)。,的最大公因數(shù)可記為或，多個(gè)整數(shù)的最大公因數(shù)也有同樣的記號(hào)。求最大公因數(shù)有多種方法，比如我們小學(xué)就學(xué)過(guò)的質(zhì)因數(shù)分解法、短除法。

那么你是否有這樣的疑問(wèn)：追本溯源，最大公因數(shù)最早出現(xiàn)在哪里呢？

實(shí)際上，最早系統(tǒng)研究最大公因數(shù)問(wèn)題的是古希臘數(shù)學(xué)家歐幾里得。只不過(guò)那時(shí)還沒(méi)有系統(tǒng)的代數(shù)學(xué)，相對(duì)應(yīng)地，幾何學(xué)明顯地從數(shù)學(xué)中分離出來(lái)，并在希臘科學(xué)中占統(tǒng)治地位，其威力之大，以致于純算術(shù)的或代數(shù)的問(wèn)題都被轉(zhuǎn)譯為幾何語(yǔ)言。

而歐幾里得在《幾何原本》第Ⅶ卷中正是運(yùn)用了線段及其長(zhǎng)度解釋了最大公因數(shù)問(wèn)題，并凝練出了世界上最早的算法——輾轉(zhuǎn)相除法（也稱歐幾里得算法），具體可見(jiàn)定義Ⅶ.12、命題Ⅶ.1和命題Ⅶ.2.

“

定義Ⅶ.12：只能被作為公約的一個(gè)單位量所測(cè)盡（整除）的幾個(gè)數(shù)稱為互質(zhì)數(shù)。

“

命題Ⅶ.1：設(shè)有不等兩數(shù)，從大數(shù)中連續(xù)減去小數(shù)直到余數(shù)小于小數(shù)，再?gòu)男?shù)中連續(xù)減去余數(shù)直到小于余數(shù)，這樣一直下去，如果余數(shù)測(cè)不盡其前一個(gè)數(shù)，直到最后的余數(shù)為一個(gè)單位，那么該二數(shù)互質(zhì)。

如上圖，有兩不等數(shù)和，連續(xù)從大數(shù)中減去小數(shù)直到小于小數(shù)，再?gòu)男?shù)中連續(xù)減去余數(shù)直到小于余數(shù)，這樣一直下去，余數(shù)總是不能測(cè)盡前一個(gè)數(shù)，直到最后的余數(shù)為一個(gè)單位。

求證：和互質(zhì)，即只有一個(gè)單位能測(cè)盡和.

證明：如果和不互質(zhì)，那么總有某個(gè)數(shù)測(cè)盡它們，令其為（這里）.

令：測(cè)量得，余下小于. 令：測(cè)量得，余下小于. 令：測(cè)量得，余下單位量.

因?yàn)闇y(cè)盡，測(cè)盡，所以：測(cè)盡.

又因?yàn)闇y(cè)盡，所以：它測(cè)盡余值.

同理可得也可以測(cè)盡余值.

最終可得可以測(cè)盡單位量，這是不可能的，因?yàn)槎?/p>

因此：和只能被作為公約的一個(gè)單位量所測(cè)盡，即：和互質(zhì)（定義Ⅶ.12）。

現(xiàn)代數(shù)學(xué)語(yǔ)言已經(jīng)不再沿用歐幾里得在《幾何原本》中的術(shù)語(yǔ)了，“測(cè)得”、“測(cè)盡”兩個(gè)詞已用“除”、“整除”代替。這一命題的證明已經(jīng)運(yùn)用了輾轉(zhuǎn)相除法：開(kāi)始于兩個(gè)數(shù)，從較大的數(shù)中重復(fù)減去較小的數(shù)，只不過(guò)這里為了說(shuō)明兩數(shù)互質(zhì)，它假定1是輾轉(zhuǎn)相除法的最終結(jié)果。

“

命題Ⅶ.2：給定兩個(gè)不互質(zhì)的數(shù)，可以（用輾轉(zhuǎn)相除法）找到它們的最大公因數(shù)。

如上圖，設(shè)和為給定的兩個(gè)不互質(zhì)的數(shù)?，F(xiàn)在要求的是：找到和的最大公因數(shù)。

這里需分類討論：

①如果能測(cè)盡，則必然是和的最大公因數(shù)。

②如果測(cè)不盡，那么：就用余數(shù)去量，如果量不盡，又用后邊的余數(shù)去量前邊的余數(shù)，直到后邊的余數(shù)測(cè)盡前邊的余數(shù)。

這最后的余數(shù)不是一個(gè)單位，否則和互質(zhì)，這與假設(shè)矛盾。所以：某數(shù)可以測(cè)盡它前面數(shù)的余數(shù)。

這里和命題Ⅶ.1的操作類似，測(cè)得，測(cè)得，設(shè)最后測(cè)盡.同樣地，可推得同時(shí)測(cè)盡和，即是和的一個(gè)公因數(shù)。

以下進(jìn)一步說(shuō)明它一定是最大的。

如果不是和的最大公因數(shù)，那么必有一個(gè)大于的某數(shù)同時(shí)測(cè)盡和.

那么，因?yàn)闇y(cè)盡，測(cè)盡，所以也測(cè)盡，又它測(cè)盡整個(gè)，所以它測(cè)盡余值.同理，測(cè)盡余值，但這是不可能的，因?yàn)檩^大數(shù)不可能測(cè)盡較小數(shù)，矛盾。

所以沒(méi)有大于測(cè)盡和的數(shù)，即是和的最大公因數(shù)。

在這一命題中，再次使用了輾轉(zhuǎn)相除法求兩個(gè)不互質(zhì)的數(shù)的最大公因數(shù)，大數(shù)反復(fù)減小數(shù)，直到余數(shù)小于小數(shù)。比如要求，首先，從104中反復(fù)減去40，直到余數(shù)（24）小于40，即再?gòu)?0中反復(fù)減去24得余數(shù)16，即再?gòu)?4中反復(fù)減去16得余數(shù)8，即最后停止，因?yàn)?可以整除16.于是我們找到了這里其實(shí)也可以用圖形來(lái)解釋這一過(guò)程：如圖是邊長(zhǎng)為40和104的矩形，求就等價(jià)于這樣一個(gè)問(wèn)題：找一個(gè)最大的，邊長(zhǎng)為的正方形使它能夠填滿整個(gè)矩形，那么即有

所以我們可以作出下圖：

最終得到兩個(gè)邊長(zhǎng)為8的正方形，此正方形就一定是能夠填滿整個(gè)矩形的正方形中最大的那一個(gè)，即。

歐幾里得在《幾何原本》中對(duì)輾轉(zhuǎn)相除法的討論一直可以延申到對(duì)無(wú)理量和不可公度量的分析中去（同樣也是用幾何作圖的方法），十分有趣，之后我們會(huì)再另寫(xiě)一篇加以討論。

輾轉(zhuǎn)相除法用現(xiàn)代數(shù)學(xué)語(yǔ)言可以描述為

“

設(shè)兩數(shù),,則

（不妨設(shè) 且，不為0，指求余運(yùn)算，為除以的余數(shù)）

即兩個(gè)正整數(shù)的最大公約數(shù)等于其中較小的那個(gè)數(shù)和兩數(shù)相除余數(shù)的最大公因數(shù)。

因此輾轉(zhuǎn)相除法就是以除數(shù)和余數(shù)反復(fù)做除法運(yùn)算，當(dāng)余數(shù)為0時(shí)，取當(dāng)前算式除數(shù)即為最大公因數(shù)。

除了西方，其實(shí)在古老的東方，我國(guó)古代聰明的數(shù)學(xué)家們也早已揭示了最大公因數(shù)的秘密——運(yùn)用更相減損術(shù)求最大公因數(shù)。

提到更相減損術(shù)，就不得不提我國(guó)古代數(shù)學(xué)巨著《九章算術(shù)》?！毒耪滤阈g(shù)》內(nèi)容十分豐富，全書(shū)總結(jié)了戰(zhàn)國(guó)、秦、漢時(shí)期的數(shù)學(xué)成就，成于公元一世紀(jì)左右，其作者已不可考。根據(jù)研究，西漢的張蒼、耿壽昌曾經(jīng)做過(guò)增補(bǔ)。最后成書(shū)最遲在東漢前期，但是其基本內(nèi)容在西漢后期已經(jīng)基本定型。

更相減損術(shù)是《九章算術(shù)》中一種求最大公因數(shù)的算法，它原本是為約分而設(shè)計(jì)的，但它同時(shí)也適用于求兩個(gè)數(shù)的最大公因數(shù)?！毒耪滤阈g(shù)》原文記載：

“

可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也。以等數(shù)約之。

這句古文的意思是：

（如果需要對(duì)分?jǐn)?shù)進(jìn)行約分，那么）可以折半的話，就折半（也就是用2來(lái)約分）。如果不可以折半的話，那么就比較分母和分子的大小，用大數(shù)減去小數(shù)，互相減來(lái)減去，一直到減數(shù)與差相等為止，用這個(gè)相等的數(shù)字來(lái)約分。

舉個(gè)例子，用更相減損術(shù)求104和40的最大公因數(shù).

由于104和40是偶數(shù)，則各取一半得到52和20.

由于52和20還是偶數(shù)，則繼續(xù)取一半得到26和10.

由于26和10還是偶數(shù)，重復(fù)上述操作得到13和5.

由于13和5不是偶數(shù)，則以大數(shù)減小數(shù)，得

得到最后減數(shù)和差都是1，則停止輾轉(zhuǎn)相減。

所以，104和40的最大公因數(shù)等于1乘以第一、二、三步中約掉的3個(gè)2，即

可以發(fā)現(xiàn)，輾轉(zhuǎn)相除法和更相減損術(shù)一個(gè)用除法，一個(gè)用減法，但細(xì)想其原理則是異曲同工的，其作為求最大公因數(shù)的算法，其結(jié)果也是殊途同歸的。不管是東方還是西方，都蘊(yùn)藏著燦爛輝煌的數(shù)學(xué)成就，凝結(jié)了人類智慧的結(jié)晶。