题目
求最大公约数用辗转相除法如何证明
提问时间:2020-11-01
答案
辗转相除法
定理: 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) 和(a, a mod 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) 和(a, a mod b)的公约数是一样的,其最大公约数也必然相等,得证.
举一反三
已知函数f(x)=x,g(x)=alnx,a∈R.若曲线y=f(x)与曲线y=g(x)相交,且在交点处有相同的切线,求a的值和该切线方程.
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
最新试题
热门考点
- 1英语翻译
- 2一道初一比较麻烦的方程题题 我实在解不出了 请大家多多关照啊
- 3有药与水的混合液两种,甲种药水中药与水的比是3:1 .乙种药水中,水与药的比是5:1 .现在要把这两种药水混合成药与水各半的溶液14升.甲与乙两种药水各应取多少升?
- 4歌词中有句“小星星,亮晶晶;~小星星,眨眼睛”,是哪首歌
- 5然审视殊无所见是什么意思
- 6第二次世界大战期间德国侵略法国的资料
- 7be ,lik ,in ,to ,the ,they ,day ,quiet.
- 8什么植物一天早中晚会变化颜色?
- 9HIS ONLY SUBJECT IS RUNNING AROUND WITH ME.和HIS SUBJECT IS ONLY RUNNING AROUND WITH ME.哪个是对的
- 10cellulite