求最大公约数用辗转相除法如何证明
题目
求最大公约数用辗转相除法如何证明
答案
辗转相除法
定理: 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.给你一张边长为45厘米的正方形纸,将创新小学的长120米,宽80米的长方形操场的平面图画在上面,你觉得合适的比例尺是多少?
- 应该让别人的生活因为有了你的存在而更加美好的制解释
- 张华5分钟打字250个,李明1分钟打字45个,李明与张华每分钟打字个数的比是?【用比例的知识解答问题】
- 8,what are mutual funds?
- 8分之7+7分之4-0.875=?
- 人造卫星受的是非平衡力么?
- 请问偏铝酸钠能与盐酸反应吗?反应原理是什么?
- 已知抛物线y=x2-2mx+2m+12,问:当m为何值时,(1)抛物线经过坐标原点?(2)抛物线的对称轴是直线x=3?
- 洛必达法则的极限公式有哪些
- 计划修路8km,前2天修了1.6km,计划改变,要提前2天完成,以后平均每天至少修路多少千米?
热门考点