如何用辗转相除法求两个数的最小公倍数(步骤)
如何用辗转相除法求两个数的最小公倍数(步骤)
数学人气:584 ℃时间:2020-05-08 16:09:51
优质解答
在数学中,辗转相除法,又称欧几里得算法,是求最大公约数的算法.辗转相除法首次出现于欧几里得的《几何原本》(第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年证明了这点,开创了计算复杂性理论.
我来回答
类似推荐
猜你喜欢
- 1关于校园生态文化的作文
- 2自我介绍,谈自己对科学的认识.
- 3请帮忙翻译并分析下句子成份!What else,but a journey at the opposite end of the world,Antarctica.
- 4在杜甫的《登岳阳楼》中,“吴楚东南坼,乾坤日夜浮”一句的技巧及思想感情
- 5教书用英语怎么拼写?
- 6向AlCl3溶夜中逐滴加入NaAlO2溶液会反应吗?请把反应的离子方程式写出来.
- 7相当于几公斤压力?与气压怎么换算?
- 8英语选择题,翻译并讲解相关知识点、语法:
- 9which season do you like best?winter.why do you likewinter?because l can skate.
- 10证明 当导体中的电阻保持不变时,通过电阻的电流与电阻两端的电压成正比 要求写出实验步骤