作业帮求两个数的最大公约数的方法叫啥了/
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/15 20:41:48
求两个数的最大公约数的方法叫啥了/
求两个数的最大公约数的方法叫啥了/
求两个数的最大公约数的方法叫啥了/
辗转相除法
辗转相除法,又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法.它是已知最古老的算法,其可追溯至3000年前.
简介
辗转相除法的演示动画
在数学中,辗转相除法,又称欧几里得算法,是求最大公约数的算法.辗转相除法首次出现于欧几里得的《几何原本》（第VII卷,命题i和ii）中,而在中国则可以追溯至东汉出现的《九章算术》. 两个整数的最大公约数是能够同时整除它们的最大的正整数.辗转相减法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数.例如,252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 − 105 = 147,所以147和105的最大公约数也是21.在这个过程中,较大的数缩小了,所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零.这时,所剩下的还没有变成零的数就是两数的最大公约数.由辗转相除法也可以推出,两数的最大公约数可以用两数的整数倍相加来表示,如21 = 5 × 105 + (−2) × 252.这个重要的等式叫做贝祖等式. 辗转相除法最早出现在欧几里得的几何原本中（大约公元前300年）,所以它是现在仍在使用的算法中最早出现的.这个算法原先只用来处理自然数,但在19世纪,辗转相除法被推广至其他类型的数,如高斯整数和一元多项式.自此,现代抽象代数概念如欧几里得整环开始出现.后来,辗转相除法又扩展至其他数学领域,如纽结理论和多元多项式. 辗转相除法有很多应用,它甚至可以用来生成全世界不同文化中的传统音乐节奏.在现代密码学方面,它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分.它还被用来解丢番图方程,寻找满足中国剩余定理的数,或者求有限域的倒数.辗转相除法还可以用来构造连分数,在施图姆定理和一些整数分解算法中也有应用.辗转相除法是现代数论中的基本工具. 辗转相除法处理大数时非常高效,它需要的步骤不会超过较小数的位数（十进制下）的五倍.加百利·拉梅(Gabriel Lamé)于1844年证明了这点,开创了计算复杂性理论.
编辑本段证明
简单的想法
设两数为a、b(a>b,b最大公约数(a,b)的步骤如下：用b除a,得a=bq.r1(0≤r1).若r1=0,则(a,b)=b；若r1≠0,则再用r1除b,得b=r1q.r2 (0≤r2).若r2=0,则(a,b)=r1,若r2≠0,则继续用r2除r1,……如此下去,直到能整除为止.其最后一个非零除数即为(a,b).
原理及其详细证明
设两数为a、b(b1),则m=kn+xd=kyd+xd=(ky+x)d,则a=mc=(ky+x)dc,b=nc=ycd,故a与b最大公约数成为cd,而非c】 从而可知gcd(b,r)=c,继而gcd(a,b)=gcd(b,r). 证毕.
编辑本段计算机算法
自然语言描述
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的： 1.若 r 是 a ÷ b 的余数,则 gcd(a,b) = gcd(b,r) 2.a 和其倍数之最大公因子为 a. 另一种写法是： 1.a ÷ b,令r为所得余数（0≤r