黃旭軍

老師走進(jìn)教室門(mén)口，聽(tīng)到教室里吵成一團(tuán)。

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

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

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

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

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

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

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

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

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

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

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

寫(xiě)出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。由此可見(jiàn)，450和330的最大公因數(shù)是30。

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

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

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

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

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

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

我們知道8251和8177各自的因數(shù)有很多，而8251和8177兩個(gè)數(shù)本身也比較大，求二者的公因數(shù)并不適合用短除法，因?yàn)橛?jì)算起來(lái)會(huì)十分復(fù)雜。那么8251和8177的公因數(shù)要怎么求呢？

我們?cè)囍幂氜D(zhuǎn)相除法的原理來(lái)解決這個(gè)問(wèn)題。

根據(jù)輾轉(zhuǎn)相除法原理，設(shè)兩個(gè)數(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。這些短繩每根的長(zhǎng)度最長(zhǎng)是37厘米。