辗转相除法求最大公约数

同学们，我们在前面学过了求最大公约数的两种方法：分解质因数法和短除法，但是有的时候给出的数字如果比较大，我们用上述两种方法求质因数就比较麻烦，今天这一讲，我们将学习一种新的求最大公约数的方法：辗转相除法。

一．     知识点介绍：

每一次都用除数和余数相除，能够整除的那个余数，就是所求的最大公约数。辗转相除法求质因数的具体步骤如下：

先用小的数除大的数，得第一个余数；再用第一个余数除小的数，得第二个余数；又用第二个余数除第一个余数，得第三个余数；这样逐次用后一个余数去除第一个余数，直到余数是0为止，那么最后一个除数就是所求的最大公约数。（如果最后的除数是1，那么原来两个数是互质的！）

   我们来举个例子：

  求600和1515的最大公约数： 所以1515和600的最大公约数是15.

【例题讲解】

Eg1:用辗转相除法求4811和1981的最大公约数。

　　解：∵4811=2×1981+849，

　　1981=2×849+283，

　　849=3×283，

∴（4811，1981）=283。

　补充说明：如果要求三个或更多的数的最大公约数，可以先求其中任意两个数的最大公约数，再求这个公约数与另外一个数的最大公约数，这样求下去，直至求得最后结果.也可以直接观察，依次试公有的质因数。

拓展：Eg2:求1008、1260、882和1134四个数的最大公约数是多少？

　　解：∵（1260，1008）=252，

　　（882，1134）=126，

又（252，126）=126，

∴（1008，1260，882，1134）=126。

刚才只是牛刀小试，现在我们一起来看一道杯赛的试题：

Eg3:有一张长方形纸，长2703厘米，宽1113厘米.要把它截成若干个同样大小的正方形，纸张不能有剩余且正方形的边长要尽可能大.问：这样的正方形的边长是多少厘米（1991年小学奥林匹克决赛试题）

分析 由题意可知，正方形的边长即是2703和1113的最大公约数.在学校，我们已经学过用短除法求两个数的最大公约数，但有时会遇到类似此题情况，两个数除了1以外的公约数一下不好找到.但又不能轻易断定它们是互质数.怎么办？在此，我们以Eg3为例介绍另一种求最大公约数的方法:辗转相除法。

　　对于例6，可做如下图解：

从图中可知：在长2703厘米、宽1113厘米的长方形纸的一端，依次裁去以宽（1113厘米）为边长的正方形2个.在裁后剩下的长1113厘米，宽477厘米的长方形中，再裁去以宽（477厘米）为边长的正方形2个.然后又在裁剩下的长方形（长477厘米，宽159厘米）中，以159厘米为边长裁正方形，恰好裁成3个，且无剩余.因此可知，159厘米是477厘米、1113厘米和2703厘米的约数.所以裁成同样大的，且边长尽可能长的正方形的边长应是159厘米.所以，159厘米是2703和1113的最大公约数。

　　让我们把图解过程转化为计算过程，即：

　　2703÷1113，商2余477；

　　1113÷477，商2余159；

　　477÷159，商3余0。

或者写为

2703=2×1113+477，

　　1113=2×477+159，

　　477=3×159。

　　当余数为0时，最后一个算式中的除数159就是原来两个数2703和1113的最大公约数.

　　可见，477=159×3，

　　1113=159×3×2+159=159×7，

　　2703=159×7×2+477

　　=159×7×2+159×3=159×17。

　　又∵7和17是互质数，

∴159是2703和1113的最大公约数。

【小结】辗转相除法的优点在于它能在较短的时间内求出任意两个数的最大公约数。