关于辗转相除法求最大公约数及其简单证明
关于辗转相除法求最大公约数及其简单证明
辗转相除法的详细介绍在这里：
简单来说，就是两个数a跟b的最大公约数gcd(a,b) = gcd(b, a%b),当b=0时，gcd(a,b) = a。
举例来说：
gcd(18,30) = gcd(30, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6
那么，这个式子永远都是对的吗？我来简单证明一下：
1.首先，必然存在两种情况a&b和a&b,我们先考虑a&b的情况。此时，a%b=a,所以gcd(a,b) = gcd(b,a),这意味着我们只需要考虑a&b的情况。
2.由于该算法分两部分，我们需要单独证明其的正确性：
I.a,b均不为0时：
设a,b的x为a和b的任意一个公约数,则有：
则c=a%b=a-nb(其中n&a/b)=a'x-nb'x=x(a'-nb'),因为n&a/b=a'x/b'x=a'/b',所以n&a'/b'
我们有这个等式c=a%b=a-nb=a'x-nb'x=x(a'-nb')，其中a'为整数，nb'均为整数，且nb'&a,则a'-nb'为大于0的整数。所以：
x也是a%b的约数，也就是说，结论一：a跟b的任意一个公约数均为b跟a%b的公约数。
再设y为b和a%b的任意一个公约数，则用：
a=nb+c=nb'y+c'y=y(nb'+c'),又因为n,b',c'均为正整数，则可以得出,y为a的约数，且：
结论二：b跟a%b的任意一个公约数均为a跟b的公约数
综合结论一跟结论二: a,b跟b,a%b的公约数集合是一样的，则Z=gcd(a,b)为a,b公约数集合中最大的一个数，则Z肯定在b,a%b的公约数集合中，而且是最大的一个，所以Z=gcd(a,b) = gcd(b, a%b)
II.当b为0时(采用a[x],b[x]及a[x+1],b[x+1]表示父一代a,b及子一代a,b的关系)：
当b[x]=0,则可说明a[x-1]%b[x-1]=0,说明a[x-1]是b[x-1]=a[x]的整数倍。显而易见，最后的a=a[x]为a[x-1],b[x-1]的最大公约数。
综上两部分证明，可以得知，辗转相除法求最大公约数是正确的
我的热门文章
即使是一小步也想与你分享当前位置：
＞＞＞分别用辗转相除法和更相减损之术求下列两数的最大公约数.(1)261..
分别用辗转相除法和更相减损之术求下列两数的最大公约数. (1)261，319;(2)1 734，816.
题型：解答题难度：偏易来源：不详
解：(1)辗转相除法319÷261=1(余58)261÷58=4(余29)58÷29=2(余0)∴319与261的最大公约数是29.更相减损之术：(261，319)→(261，58)→(203，58)→(145，58)→(87，58)→(29，58)→(29，29).∴319与261的最大公约数是29.(2)辗转相除法：1 734÷816=2(余102)，816÷102=8(余0)，∴1 734与816的最大公约数是102.更相减损之术：因为两数皆为偶数，首先除以2得到867，408，再求867与408的最大公约数.(867，408)→(459，408)→(51，408)→(51，357)→(51，306)→(51，255)→(51，204)→(51，153)→(51，102)→(51，51).∴1 734与816的最大公约数是51×2=102.[=HS(]对于第二个问题，用更相减损之术求解时，最后的结论有的同学可能会写成51，而没有乘以2，从而得出与用辗转相除法不一样的答案，51是它们的公约数，2也是它们的公约数，所以最大公约数就为51×2=102.使用辗转相除法可依据m=nq+r，反复执行，直到r=0为止；用更相减损之术就是根据m-n=r，反复执行，直到n=r为止.
马上分享给同学
据魔方格专家权威分析，试题“分别用辗转相除法和更相减损之术求下列两数的最大公约数.(1)261..”主要考查你对&&算法案例&&等考点的理解。关于这些考点的“档案”如下：
现在没空？点击收藏，以后再看。
因为篇幅有限，只列出部分考点，详细请访问。
主要有辗转相除法、更相减损术、秦九韶算法、k进制化十进制的算法。
辗转相除的定义：
所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。
更相减损术的定义：
就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。比较辗转相除法与更相减损术的区别：
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。辗转相除法的一个程序算法的步骤：
第一步：输入两个正整数m,n(m&n).第二步：计算m除以n所得的余数r.第三步：m=n,n=r.第四步：若r＝0,则m,n的最大公约数等于m；否则转到第二步.第五步：输出最大公约数m.
更相减勋术的一个程序算法步骤：
第一步：输入两个正整数a,b(a&b);第二步：若a不等于b,则执行第三步；否则转到第五步；第三步：把a-b的差赋予r;第四步：如果b&r,那么把b赋给a,把r赋给b;否则把r赋给a，执行第二步；第五步：输出最大公约数b.
发现相似题
与“分别用辗转相除法和更相减损之术求下列两数的最大公约数.(1)261..”考查相似的试题有：
768880754469771896852366771841808368高中数学 COOCO.因你而专业 ！
你好！请或
使用次数：0
入库时间：
（本小题满分12分）(1)用辗转相除法求840与1764的最大公约数.
&&&&&&&&& (2)用秦九韶算法计算函数时的函数值.
解：（1）用辗转相除法求840与1 764 的最大公约数.
1 764 = 840×2 + 84&&&&&&&&&
840 = 84×10 +0
所以840与1 764 的最大公约数是84
(2)根据秦九韶算法，把多项式改写成如下形式：f(x)=(((2x+3)x+0)x+5)x-4
从内到外的顺序依次计算一次多项式当x=2时的值：
v0=2&& v1=2×2+3=7& v2=7×2+0=14&& v3=14×2+5=33& v4=33×2-4=62
所以，当x=2时，多项式的值等于62
如果没有找到你要的试题答案和解析，请尝试下下面的试题搜索功能。百万题库任你搜索。搜索成功率80%用辗转相除法求最大公约数,为什么?理论依据?
梦殇天堂147
【两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数.】辗转相除法求两个数的最大公约数的步骤如下：先用小的一个数除大的一个数,得第一个余数；再用第一个余数除小的一个数,得第二个余数；又用第二个余数除第一个余数,得第三个余数；这样逐次用后一个数去除前一个余数,直到余数是0为止.那么,最后一个除数就是所求的最大公约数（如果最后的除数是1,那么原来的两个数是互质数）.例如求的最大公约数,第一次：用600除1515,商2余315；第二次：用315除600,商1余285；第三次：用285除315,商1余30；第四次：用30除285,商9余15；第五次：用15除30,商2余0.的最大公约数是15.辗转相除法是求两个数的最大公约数的方法.如果求几个数的最大公约数,可以先求两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数.这样依次下去,直到最后一个数为止.最后所得的一个最大公约数,就是所求的几个数的最大公约数.【以上是我参考的其他网友的回答,】不过,有些问题不需要钻牛角尖,只要直接拿来用就OK,要不然会很累的.：）
为您推荐：
其他类似问题
若A、B都是N的倍数，则A-B仍然是N的倍数。也就是把两个数相减，不会使约数消失。那么可以用互相减的办法，把数字化小，直到一个数是另一个数的倍数。
这样由于a和b的全体公因子集合与b和r的全体公因子集合相同，所以a和b的最大公因子必须等于b和r的最大公因子其实还有一个更相减损术，也是求最大公约数
扫描下载二维码}