数学百科知识整理:欧几里得算法
知识是无限,是丰富的,大家除了课本上的知识外,课外的一些百科知识也应该了解,下文提供了数学百科知识整理,欢迎大家参考。
欧几里德算法
欧几里德算法又称辗转相除法,用于计算两个整数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)的公约数是一样的,其最大公约数也必然相等,得证。
数学百科知识整理的相关内容就为大家分享到这里了,希望大家能够丰富自己,努力自己。
【数学百科知识整理:欧几里得算法】相关文章:
- 上一篇:沪教版三年级数学上册《三角形》教案
- 下一篇:课外数学百科小知识:费马大定理
相关数学趣味数学推荐
精美图文
精品推荐
- 【北京特级教师同步复习精讲辅导】2014~2015学年华师大版九年级数学下册课后练习:二次根式的概念和性质@_@课后练习二(含详
- 【北京特级教师同步复习精讲辅导】2014~2015学年华师大版九年级数学下册课后练习:一元二次方程的整数根@_@课后练习二(含详
- 【北京特级教师同步复习精讲辅导】2014~2015学年华师大版九年级数学下册课后练习:一元二次方程的应用@_@课后练习二(含详解
- 【北京特级教师同步复习精讲辅导】2014~2015学年华师大版九年级数学下册课后练习:一元二次方程的判别式@_@课后练习二(含详
- 【北京特级教师同步复习精讲辅导】2014~2015学年华师大版九年级数学下册课后练习:相似三角形的应用@_@课后练习二(含详解共
- 【北京特级教师同步复习精讲辅导】2014~2015学年华师大版九年级数学下册课后练习:相似三角形的应用@_@课后练习一(含详解共
- 【北京特级教师同步复习精讲辅导】2014~2015学年华师大版九年级数学下册课后练习:相似三角形有关的综合问题2@_@课后练习二
- 【北京特级教师同步复习精讲辅导】2014~2015学年华师大版九年级数学下册课后练习:一元二次方程的公共根@_@课后练习一(含详
- 61、2020同步人A数学必修第一册新教材章末综合测评(五) 三角函数 Word版含解析
- 58、2020同步人A数学必修第一册新教材章末综合测评(二) 一元二次函数、方程和不等式 Word版含解析
- 冀教版小学数学二年级下册第二单元《租船问题》
- 君晓天云【顺丰江苏适用】2019秋全新 亮点给力大试卷二年级上册 语文人教版+数学苏教版 2年级上试卷 两本 小学生单元期中期末综合测试卷
- 北师大版数学七上-2.1《有理数》课堂教学视频实录-刘学军
- 小升初试卷模拟卷试题人教版 小升初真题卷语文数学英语全套3本 小学生毕业总複习资料 小升初模拟卷 六年级小升初试卷真题
- 苏科版数学七年级下册7.2《探索平行线的性质》
- 冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣
- 人教版七年级数学下册第五章5.1.3《同位角、内错角、同旁内角》_高清
- 高职高考数学公式
- 北师大版数学七上-2.1《有理数》课堂教学视频实录-朱慧芬
- 冀教版小学数学二年级下册第二单元《有余数除法的整理与复习》