巧求最大公因數(shù)

黃旭軍

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

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

例題：求6和8的最大公因數(shù)。

寫出6的因數(shù)：1，2，3，6。

寫出8的因數(shù)：1，2，4，8。

所以6和8的最大公因數(shù)是2。

老師說：“很好呀，沒錯呀！”數(shù)學(xué)課代表說：“老師，有很大的問題，我發(fā)現(xiàn)數(shù)字要是大一點，這個方法做起來就太復(fù)雜了！”

“對，太復(fù)雜了！”很多同學(xué)應(yīng)和道。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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