题目
求最大公约数用辗转相除法如何证明
提问时间: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从0-9选5个的组合数共有252组,请问252组中无3个以上(包括3个)数字重复的有多少组?
- 2”中国以有了自己的工程师”变化句子的说法,但句意不变
- 3hear(换字母变词)( ..
- 4英语翻译
- 5一项工作,甲单独做需要10天,乙单独做需要12天,丙单独做需15天,现甲乙共做3天后,甲因事离去,丙参加工作,还需几天完成?
- 6形容什么事只能靠自己的成语
- 7死也不倒下阅读题 吉鸿昌的墓碑上会写些什么内容
- 8里字组词
- 9i must have watched 和 i must have been watch TV意思一样吗 为什么
- 10两个数的和等于758,其中一个数的最后一位数字是0,如果把0去掉,两个数就相等,这两个数中较小的一个是( ).
热门考点
- 1that the dog was the first animal to be domesticated is generally agreed upon by
- 2若已定义X,Y为float类型,则表达式X=2,Y=X+3/2值是(求详细解答过程)
- 3从粮仓里第一次调出的小麦占粮仓存粮总数的9/16,第二天又调出第一次的1/3,正好是54吨,第三次又调出总数
- 4一次植树活动,规定大树每人种2棵,小树每人种4棵,全班5O人植树140棵,问种这两种树各多少人?
- 5·体操运动员手上擦镁粉是为了增大摩擦还是减少摩擦?
- 6受到惩罚用英文怎么说
- 7当k为何值时,关于x的方程x²-(2k-1)x+k²=0有两个不相等的实数根
- 8两个正整数的和是16,要是这两个正整数的乘积最大,这两个正整数各是多少?这两个正整数的乘积最小,这两个正整数各是多少?
- 9是否所有金属氧化物都能与浓硝酸反应?
- 10一个“220V,100W”的灯泡在家庭电路中标有“220v.3000r/Kw.H”的电能表上单独工作60s时,电能表转盘刚好转过4转,此时家庭电路的实际电压是多少x0c