巧求最大公因数

黄旭军

老师走进教室门口，听到教室里吵成一团。

原来同学们都在指着黑板上的例题议论纷纷。

例题：求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厘米。