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

编辑:sx_yanxf

2016-10-08

知识是无限,是丰富的,大家除了课本上的知识外,课外的一些百科知识也应该了解,下文提供了数学百科知识整理,欢迎大家参考。

欧几里德算法

欧几里德算法又称辗转相除法,用于计算两个整数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)的公约数是一样的,其最大公约数也必然相等,得证。

数学百科知识整理的相关内容就为大家分享到这里了,希望大家能够丰富自己,努力自己。

相关推荐:

课外数学百科知识点之《相似三角形的识别》  

经典数学百科知识点:N维空间的欧拉公式  

标签:数学

免责声明

威廉希尔app (51edu.com)在建设过程中引用了互联网上的一些信息资源并对有明确来源的信息注明了出处,版权归原作者及原网站所有,如果您对本站信息资源版权的归属问题存有异议,请您致信qinquan#51edu.com(将#换成@),我们会立即做出答复并及时解决。如果您认为本站有侵犯您权益的行为,请通知我们,我们一定根据实际情况及时处理。