当前位置 :
【辗转相除的原理是?题:求204和85的最大公约数解:204/85=2……3485/34=2……1734/17=2……0所以17是最大公约数问:为什么?能不能证出来?】
1人问答
更新时间:2024-04-25 23:46:23
问题描述:

辗转相除的原理是?

题:求204和85的最大公约数

解:204/85=2……34

85/34=2……17

34/17=2……0

所以17是最大公约数

问:为什么?能不能证出来?

陈昌熊回答:
  辗转相除法的证明   设两数为a、b(b<a),求它们最大公约数的步骤如下:用b除a,得a=bq+r(0≤r<b)(q是这个除法的商).若r=0,则b是a和b的最大公约数.若r≠0,则继续考虑.   首先,应该明白的一点是任何a和b的公约数都是r的公约数.要想证明这一点,就要考虑把r写成r=a-bq.现在,如果a和b有一个公约数d,而且设a=sd,b=td,那么r=sd-tdq=(s-tq)d.因为这个式子中,所有的数(包括s-tq)都为整数,所以r可以被d整除.   对于所有的d的值,这都是正确的;所以a和b的最大公约数也是b和r的最大公约数.因此我们可以继续对b和r进行上述取余的运算.这个过程在有限的重复后,可以最终得到r=0的结果,我们也就得到了a和b的最大公约数.
最新更新
PC端 | 移动端 | mip端
问答网(wenda2.com)汇总了汉语字典,新华字典,成语字典,组词,词语,在线查字典,中文字典,英汉字典,在线字典,康熙字典等等,是学生查询学习资料的好帮手,是老师教学的好助手。
声明:本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。

邮箱:联系方式:

Copyright©2009-2021 问答网 wenda2.com 版权所有 闽ICP备2022000227号-1