哈嘍小伙伴們 ，今天給大家科普一個小知識。在日常生活中我們或多或少的都會接觸到最大公因數（最大公因數的前世今生）方面的一些說法，有的小伙伴還不是很了解，今天就給大家詳細的介紹一下關于最大公因數（最大公因數的前世今生）的相關內容。

最大公因數（最大公因數的前世今生）

(資料圖片)

最大公因數（Greatest Common Divisor），也稱最大公約數、最大公因子，指兩個或多個整數共有因數中最大的一個。,的最大公因數可記為或，多個整數的最大公因數也有同樣的記號。求最大公因數有多種方法，比如我們小學就學過的質因數分解法、短除法。

那么你是否有這樣的疑問：追本溯源，最大公因數最早出現在哪里呢？

實際上，最早系統研究最大公因數問題的是古希臘數學家歐幾里得。只不過那時還沒有系統的代數學，相對應地，幾何學明顯地從數學中分離出來，并在希臘科學中占統治地位，其威力之大，以致于純算術的或代數的問題都被轉譯為幾何語言。

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

“

定義Ⅶ.12：只能被作為公約的一個單位量所測盡（整除）的幾個數稱為互質數。

“

命題Ⅶ.1：設有不等兩數，從大數中連續減去小數直到余數小于小數，再從小數中連續減去余數直到小于余數，這樣一直下去，如果余數測不盡其前一個數，直到最后的余數為一個單位，那么該二數互質。

如上圖，有兩不等數和，連續從大數中減去小數直到小于小數，再從小數中連續減去余數直到小于余數，這樣一直下去，余數總是不能測盡前一個數，直到最后的余數為一個單位。

求證：和互質，即只有一個單位能測盡和.

證明：如果和不互質，那么總有某個數測盡它們，令其為（這里）.

令：測量得，余下小于. 令：測量得，余下小于. 令：測量得，余下單位量.

因為測盡，測盡，所以：測盡.

又因為測盡，所以：它測盡余值.

同理可得也可以測盡余值.

最終可得可以測盡單位量，這是不可能的，因為而。

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

現代數學語言已經不再沿用歐幾里得在《幾何原本》中的術語了，“測得”、“測盡”兩個詞已用“除”、“整除”代替。這一命題的證明已經運用了輾轉相除法：開始于兩個數，從較大的數中重復減去較小的數，只不過這里為了說明兩數互質，它假定1是輾轉相除法的最終結果。

“

命題Ⅶ.2：給定兩個不互質的數，可以（用輾轉相除法）找到它們的最大公因數。

如上圖，設和為給定的兩個不互質的數。現在要求的是：找到和的最大公因數。

這里需分類討論：

①如果能測盡，則必然是和的最大公因數。

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

這最后的余數不是一個單位，否則和互質，這與假設矛盾。所以：某數可以測盡它前面數的余數。

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

以下進一步說明它一定是最大的。

如果不是和的最大公因數，那么必有一個大于的某數同時測盡和.

那么，因為測盡，測盡，所以也測盡，又它測盡整個，所以它測盡余值.同理，測盡余值，但這是不可能的，因為較大數不可能測盡較小數，矛盾。

所以沒有大于測盡和的數，即是和的最大公因數。

在這一命題中，再次使用了輾轉相除法求兩個不互質的數的最大公因數，大數反復減小數，直到余數小于小數。比如要求，首先，從104中反復減去40，直到余數（24）小于40，即再從40中反復減去24得余數16，即再從24中反復減去16得余數8，即最后停止，因為8可以整除16.于是我們找到了這里其實也可以用圖形來解釋這一過程：如圖是邊長為40和104的矩形，求就等價于這樣一個問題：找一個最大的，邊長為的正方形使它能夠填滿整個矩形，那么即有

所以我們可以作出下圖：

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

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

輾轉相除法用現代數學語言可以描述為

“

設兩數,,則

（不妨設 且，不為0，指求余運算，為除以的余數）

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

因此輾轉相除法就是以除數和余數反復做除法運算，當余數為0時，取當前算式除數即為最大公因數。

除了西方，其實在古老的東方，我國古代聰明的數學家們也早已揭示了最大公因數的秘密——運用更相減損術求最大公因數。

提到更相減損術，就不得不提我國古代數學巨著《九章算術》。《九章算術》內容十分豐富，全書總結了戰國、秦、漢時期的數學成就，成于公元一世紀左右，其作者已不可考。根據研究，西漢的張蒼、耿壽昌曾經做過增補。最后成書最遲在東漢前期，但是其基本內容在西漢后期已經基本定型。

更相減損術是《九章算術》中一種求最大公因數的算法，它原本是為約分而設計的，但它同時也適用于求兩個數的最大公因數。《九章算術》原文記載：

“

可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。

這句古文的意思是：

（如果需要對分數進行約分，那么）可以折半的話，就折半（也就是用2來約分）。如果不可以折半的話，那么就比較分母和分子的大小，用大數減去小數，互相減來減去，一直到減數與差相等為止，用這個相等的數字來約分。

舉個例子，用更相減損術求104和40的最大公因數.

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

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

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

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

得到最后減數和差都是1，則停止輾轉相減。

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

可以發現，輾轉相除法和更相減損術一個用除法，一個用減法，但細想其原理則是異曲同工的，其作為求最大公因數的算法，其結果也是殊途同歸的。不管是東方還是西方，都蘊藏著燦爛輝煌的數學成就，凝結了人類智慧的結晶。