金榜之路
学大陪你
个性化辅导
关于我们  |  联系我们

数学百科知识:欧几里得算法

来源:学大教育     时间:2016-10-17 18:01:35


学习数学需要大家了解很多知识,这些知识有利于我们增长见识,下面学大教育网为大家带来数学百科知识:欧几里得算法,希望我们能够完全掌握这些数学知识,从而增加自己的学识。

欧几里德算法

欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理:

定理:gcd(a,b) = gcd(b,a mod b)

证明:a可以表示成a = kb + r,则r = a mod b

假设d是a,b的一个公约数,则有

d|a, d|b,而r = a - kb,因此d|r

因此d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数,则

d | b , d |r ,但是a = kb +r

因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证。

数学百科知识:欧几里得算法是学大教育网为大家带来的,希望大家能够好好了解这些数学知识,想要了解更多的课外知识,欢迎登陆学大教育网。

网站地图 | 全国免费咨询热线: | 服务时间:8:00-23:00(节假日不休)

违法和不良信息举报电话:400-810-5688 举报邮箱:info@xueda.com 网上有害信息举报专区

京ICP备10045583号-6 学大Xueda.com 版权所有 北京学大信息技术集团有限公司 京公网安备 11010502031324号

增值电信业务经营许可证京B2-20100091 电信与信息服务业务经营许可证京ICP证100956