辗转相除法怎么理解,最好能跟个例子!
来源：学生作业帮助网 编辑：六六作业网 时间：2024/04/29 11:59:27
辗转相除法怎么理解,最好能跟个例子!
辗转相除法怎么理解,最好能跟个例子!
辗转相除法怎么理解,最好能跟个例子!
那我就按照你给的这个例子具体来说吧：
8251＝6105＋2146,为了表示简单,我就用a=b+c表示这个吧
于是有c=a-b
那么如果有d|a,且d|b,就必然有d|a-b,也就是d|c,
可见a和b的公约数必然也是c的约数.
现在假设d是a,b的最大公约数,那么d也必然是c的约数,于是d是b,c的公约数,现在就要证明它是最大公约数——
因为a=b+c,于是b,c的公约数也必然是a的约数,假设(b,c)=e,（根据"d是b,c的公约数"知道d|e）那么有e|b+c,即e|a,可见e也是a,b的公约数,e|d,综上有e=d
可见(a,b)=(b,c)=d
这个思想一推广,就成了辗转相除法了.
说的够明白吧?
辗转相除法是求最大公约数的另一种方法。具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
例如：求112和77的最大公约数。
112=77*1+35(余数)
77=35*2+7(余数)
35=7*5+0(余数)<...
全部展开
辗转相除法是求最大公约数的另一种方法。具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
例如：求112和77的最大公约数。
112=77*1+35(余数)
77=35*2+7(余数)
35=7*5+0(余数)
所以最大公约数是：7
收起
一张长方形纸，长2703厘米，宽1113厘米.要把它截成若干个同样大小的正方形，纸张不能有剩余且正方形的边长要尽可能大.问：这样的正方形的边长是多少厘米？
由题意可知，正方形的边长即是2703和1113的最大公约数。在学校，我们已经学过用短除法求两个数的最大公约数，但有时会遇到类似此题情况，两个数除了1以外的公约数一下不好找到，但又不能轻易断定它们是互质数怎么办？在此，我们介绍另...
全部展开
一张长方形纸，长2703厘米，宽1113厘米.要把它截成若干个同样大小的正方形，纸张不能有剩余且正方形的边长要尽可能大.问：这样的正方形的边长是多少厘米？
由题意可知，正方形的边长即是2703和1113的最大公约数。在学校，我们已经学过用短除法求两个数的最大公约数，但有时会遇到类似此题情况，两个数除了1以外的公约数一下不好找到，但又不能轻易断定它们是互质数怎么办？在此，我们介绍另一种求最大公约数的方法。
做如下图
从图中可知：在长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的最大公约数。
我们把这种求最大公约数的方法叫做辗转相除法.辗转相除法的优点在于它能在较短的时间内求出任意两个数的最大公约数。
收起