巧求最大公因數

黃旭軍

老師走進教室門口，聽到教室里吵成一團。

原來同學們都在指著黑板上的例題議論紛紛。

例題：求6和8的最大公因數。

寫出6的因數：1，2，3，6。

寫出8的因數：1，2，4，8。

所以6和8的最大公因數是2。

老師說：“很好呀，沒錯呀！”數學課代表說：“老師，有很大的問題，我發現數字要是大一點，這個方法做起來就太復雜了！”

“對，太復雜了！”很多同學應和道。

老師說：“求最大公因數除了上面這種方法，還有短除法和輾轉相除法（更相減損術，這兩種方法原理相同）！既然大家這么好學，今天就告訴大家一些“獨家秘方”吧！”

例1 一個房間地面長450厘米，寬330厘米，現在計劃用正方形的方磚鋪房間的地面，請問方磚的邊長最長為多少厘米，才能正好將房間的地面無空隙地鋪滿？

方磚邊長的值需要既是450的因數，又是330的因數。所以方磚邊長的值需要是450和330的公因數。求方磚的最長邊長也就轉化成求450和330的最大公因數。

寫出450的因數：1，2，6，9，10，15，18，25，30，45，60，225，450。

寫出330的因數：1，2，3，5，6，10，11，15，22，30，33，55，66，110，165，330。

找出二者所有的公因數：1，2，6，10，15，30。由此可見，450和330的最大公因數是30。

答：方磚的邊長最長為30厘米，才能正好將房間地面無空隙地鋪滿。

求450和330的最大公因數，可以用短除法。短除法就是先找出兩個數的公因數，再用原數分別除以這個因數，把商寫下來之后，再繼續找這兩個商的因數，以此類推。直到最后所剩數的公因數為1。再將左側一列的數相乘，所得結果便是我們要求的最大公因數。

用短除法求450和330的最大公因數的具體計算過程如右圖，所以450和330的最大公因數是5×3×2=30。

答：方磚的邊長最長為30厘米，才能正好將房間地面無空隙地鋪滿。

例2 兩根繩子的長度分別是8251厘米和8177厘米，把它們盡可能剪成一些同樣長度的短繩。那么這些短繩每根的長度最長是多少？

剪成同樣長度的短繩，也可以看成是求出8251和8177的公因數。而求這些短繩最長的長度，也就是求8251和8177的最大公因數。

我們知道8251和8177各自的因數有很多，而8251和8177兩個數本身也比較大，求二者的公因數并不適合用短除法，因為計算起來會十分復雜。那么8251和8177的公因數要怎么求呢？

我們試著用輾轉相除法的原理來解決這個問題。

根據輾轉相除法原理，設兩個數的最大公因數是x，則有8251=ax，8177=bx，8251-8177=74=ax-bx=（a-b）x，也就是74=（a-b）x。

將74分解質因數，74=37×2。而8251和8177都是奇數，二者的最大公因數不可能是2，所以8251和8177的最大公因數是37。這些短繩每根的長度最長是37厘米。