作者 | 大小吳

來源 | 大小吳的數學課堂

“

今天大小吳來和大家聊一聊最大公因數的前世今生。

1 什麼是最大公因數

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

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

2 歐幾裡得與輾轉相除法

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

而歐幾裡得在《幾何原本》第Ⅶ卷中正是運用了線段及其長度解釋了最大公因數問題，并凝練出了世界上最早的算法——輾轉相除法（也稱歐幾裡得算法），具體可見定義Ⅶ.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時，取當前算式除數即為最大公因數。

3 《九章算術》與更相減損術

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

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

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

“

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

這句古文的意思是：

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

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

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

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

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

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

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

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

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

參考文獻[1]歐幾裡得.幾何原本[2]九章算術

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部