辗转相除法和更相减损术的来历,证明,以及它们的应用
来源：学生作业帮助网 编辑：六六作业网 时间：2024/04/29 12:54:41
辗转相除法和更相减损术的来历,证明,以及它们的应用
辗转相除法和更相减损术的来历,证明,以及它们的应用
辗转相除法和更相减损术的来历,证明,以及它们的应用
来历：
辗转相除法最早出现在欧几里得的几何原本中（大约公元前300年）,所以它是现在仍在使用的算法中最早出现的.这个算法原先只用来处理自然数,但在19世纪,辗转相除法被推广至其他类型的数,如高斯整数和一元多项式.自此,现代抽象代数概念如欧几里得整环开始出现.后来,辗转相除法又扩展至其他数学领域,如纽结理论和多元多项式.
更相减损术是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合.
更相减损术例子：
、用更相减损术求98与63的最大公约数.
由于63不是偶数,把98和63以大数减小数,并辗转相减：
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
所以,98和63的最大公约数等于7
辗转相除法例子：
计算 gcd(546,429)
gcd(546,429) 546=1*429+117
=gcd(429,117) 429=3*117+78
=gcd(117,78) 117=1*78+39
=gcd(78,39) 78=2*39
=39
辗转相除法的证明：
∵a为m,n的最大公约数,
∴m能被a整除,且n也能被a整除,
∴由推论1得：qn也能被a整除,
∴ 由推论2得：m-qn也能被a整除,
又 ∵m-qn=r,
∴r也能被a整除,即a为n和r的公约数（注意：还不是最大公约数）
∵b为n和r的最大公约数,a为n和r的公约数
∴a≤b,
同理 ∵b为n,r的最大公约数,
∴n能被b整除,且r也能被b整除,
∴由推论1得：qn也能被b整除,
∴由推论2得：qn+r也能被b整除,
又∵m=qn+r,
∴m也能被b整除,即b为m和n的公约数,（注意：还不是最大公约数）
∵a为m,n的最大公约数,b为m和n的公约数,
∴b≤a,
由以上可知：a≤b与b≤a同时成立,
故可得 a=b,
证毕.
那是什么东西？
貌似在计算机里面用到吧