辗转相除法求最大公约数和最小公倍数
(2006-08-28 11:39:55)
转载
分类：小学奥数专题讲解
辗转相除法是求最大公约数和最小公倍数的另一种方法。
具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。
如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
把这些数相乘就是最小公倍数。
例如：求112和77的最大公约数。
把112和77并列，用77去除112，商1余35，如下图：
因为余数不是0，所以继续用35去除77，商2余7，如下图：
因为余数不是0，继续用7去除35，商5余0，如下图：
当最后余数是0时，辗转相除的过程已经完成，最后的除数7就是112和77的最大公约数。
辗转相除法的算理是根据：在a=bq+r，中，除数b和余数r能被同一个数整除，那么被除数a也能被这个数整除。
或者说，除数与余数的最大公约数，就是被除数与除数的最大公约数；如果反过来说，被除数与除数的最大公约数，就是除数与余数的最大公约数。
如果用辗转相除法求两个数的最大公约数时，最后的余数是1，那么这两个数就是互质数，或者说，它们只有公约数1。
最大公约数和最小公倍数初中数学中，最大公约数和最小公倍数是非常重要的概念，它们在解决整数运算、分数化简、方程求解等问题中起着至关重要的作用。
本文将从实际问题出发，通过举例、分析和说明，详细介绍最大公约数和最小公倍数的概念、性质和应用，以帮助中学生和他们的父母更好地理解和运用这两个概念。
一、最大公约数最大公约数，简称最大公因数，是指两个或多个整数共有的最大的约数。
我们可以通过列举法、质因数分解法和辗转相除法等方法来求解最大公约数。
例如，我们要求解12和18的最大公约数。
首先，我们可以列举出12的因数为1、2、3、4、6、12，18的因数为1、2、3、6、9、18。
可以看出，它们的公因数有1、2、3、6，其中6是最大的，因此12和18的最大公约数为6。
又如，我们要求解24和36的最大公约数。
我们可以使用质因数分解法，将24分解为2^3 × 3，36分解为2^2 × 3^2。
可以看出，它们的公因数有2^2 × 3，即12，因此24和36的最大公约数为12。
最大公约数在分数化简、比例关系、方程求解等问题中都有广泛的应用。
例如，在分数化简中，我们可以通过求解分子和分母的最大公约数，将分数化简为最简形式；在比例关系中，我们可以通过求解比例中各个数的最大公约数，确定比例的最简形式；在方程求解中，我们可以通过求解方程中各个系数的最大公约数，将方程化简为最简形式。
二、最小公倍数最小公倍数，简称最小公倍数，是指两个或多个整数的公倍数中最小的一个。
我们可以通过列举法、质因数分解法和最大公约数的性质来求解最小公倍数。
例如，我们要求解6和9的最小公倍数。
通过列举法，我们可以找到它们的公倍数为6、12、18、24、30、36、42、48、54、60等，可以看出，它们的最小公倍数为18。
又如，我们要求解8和12的最小公倍数。
我们可以使用质因数分解法，将8分解为2^3，12分解为2^2 × 3。
最大公约数与最小公倍数基本概念：1、公约数和最大公约数几个数公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。
例如：12的约数有1，2，3，4，6，12；30的约数有1，2，3，5，6，10，15，30。
12和30的公约数有1，2，3，6，其中6是12和30的最大公约数。
一般地我们用（a,b）表示a,b这两个自然数的最大公约数，如（12，30）=6。
如果（a,b）=1,则a,b两个数是互质数。
2、公倍数和最小公倍数几个数公有的倍数，叫做这几个数的公倍数；其中最小的一个，叫做这几个数的最小公倍数。
例如：12的倍数有12，24，36，48，60，72，…18的倍数有18，36，72，90，…12和18的公倍数有：36，72…其中36是12和18的最小公倍数。
一般地，我们用[a,b]表示自然数，a,b的最小公倍数，如[12，18]=36。
3、最大公约数与最小公倍数的求法A．最大公约数求两个数的最大公约数一般有以下几种方法（1）分解质因数法（2）短除法（3）辗转相除法（4）小数缩倍法（5）公式法前两种方法在数学课本中已经学过，在这里我们主要介绍辗转相除法。
当两个整数不容易看出公约数时（一般是数字比较大），我们可以合用辗转相除法。
B．最小公倍数求几个数的最小公倍数的方法也有以下几种方法：（1）分解质因数法（2）短除法（3）大数翻倍法（4）a×b=（a,b）×[a,b]上面的公式表示：两个数的乘积等于这两个数的最大公约数和最小公倍数的乘积。
例1、437与323的最大公约数是多少？LX1、24871和3468的最小公倍数是多少？例2、把一块长90厘米，宽42厘米的长方形铁板剪成边长都是整厘米，面积都相等的小正方形铁板，恰无剩余。
至少能剪块。
【分析】根据题意，剪得的小正形的边长必须是90和42的最大公约6。
所以原长方形的长要分90÷6＝15段，宽要分42÷6＝７段，至少能剪17×７＝105（块）解：（１）求90和42的最大公约数2 90 423 45 2115 7（90，42）＝60（2）求至少剪多少块正方形铁板90÷6＝1545÷6 ＝715×7＝105（块）至少可以剪105块正方形铁板。
写两个函数分别求两个整数的最大公约数和最小公倍数函数一：求两个整数的最大公约数
```python
def gcd(a, b):
"""
递归求两个整数的最大公约数
:param a: 整数1
:param b: 整数2
:return: 最大公约数
"""
if b == 0:
return a
else:
return gcd(b, a % b)
```
```python
def lcm(a, b):
"""
:param a: 整数1
:param b: 整数2
"""
return abs(a * b) // gcd(a, b)
```
这两个函数分别实现了求两个整数的最大公约数和最小公倍数的功能。
其中，函数`gcd`使用了辗转相除法来求最大公约数。
在每一次迭代中，如果b等于0，则说明a就是最大公约数，直接返回a；否则，将b
和a对b取余得到的结果作为新的a，b作为新的b，继续递归调用函数
`gcd`。
函数`lcm`中，先调用函数`gcd`来求出最大公约数，然后使用整数a
和b的乘积除以最大公约数得到最小公倍数。
注意，为了确保最小公倍数
为正数，使用了`abs`函数来取绝对值。
这样，通过调用这两个函数，可以方便地求解任意两个整数的最大公
约数和最小公倍数。
