题目
辗转相除法求最大公因数
提问时间:2020-12-09
答案
辗转相除法原本是初等数论的内容,不过近年在中学数学里也有出现,是以算法初步的内容出现的,所以有必要简单介绍一下.并且我们在下一篇文章里,将结合菲波拉契数列导出辗转相除法的步数估计——拉梅定理.
辗转相除法又叫欧几里得算法,是欧几里得最先提出来的.不过这个名字有点不好,就如同在数学里说欧拉定理这个词一样,你不知道说的是哪个定理,因为欧拉发现的定理实在是太多……辗转相除法的实现,是基于下面的原理(在这里用(a,b)表示a和b的最大公因数):
(a,b)=(a,ka+b),其中a、b、k都为自然数.………………①
也就是说,两个数的最大公约数,将其中一个数加到另一个数上,得到的新数,其公约数不变,比如(4,6)=(4+6,6)=(4,6+2×4)=2.要证明这个原理很容易:如果p是a和ka+b的公约数,p整除a,也能整除ka+b.那么就必定要整除b,所以p又是a和b的公约数,从而证明他们的最大公约数也是相等的.
基于上面的原理,就能实现我们的迭代相减法:
(78,14)=(64,14)=(50,14)=(36,14)=(22,14)=(8,14)=(8,6)=(2,6)=(2,4)=(2,2)=(0,2)=2
基本上思路就是大数减去小数,一直减到能算出来为止,在作为练习的时候,往往进行到某一步就已经可以看出得值.迭代相减法简单,不过步数比较多,实际上我们可以看到,在上面的过程中,由(78,14)到(8,14)完全可以一步到位,因为(78,14)=(14×5+8,14)=(8,14),由此就诞生出我们的辗转相除法.
用辗转相除法求(a,b).设r0=b,r1=a,反复运用除法算式,得到一系列整数qi,ri和下面的方程:
相当于每一步都运用原理①把数字进行缩小,上面右边就是每一步对应的缩小结果,可以看出,最后的余数rn就是a和b的公约数.我们以一个题为例说明基本过程.
例题:求(326,78)
所以(326,78)=2.这和我们用迭代相减法算出来的结果是一样的.所以中学的同学们应该看到,迭代相减法和辗转相除法在本质上是一样的,相对来说,减法比较简单,但是除法步数少.
我们要看到的是,在辗转相除法中,我们必须算到最后一步才知道rn是不是所求的最大公因数,所以我们把n称作辗转相除法里的步数.在明天,我们将利用辗转相除法的过程来导出此方法的步数估计——拉梅定理.
辗转相除法又叫欧几里得算法,是欧几里得最先提出来的.不过这个名字有点不好,就如同在数学里说欧拉定理这个词一样,你不知道说的是哪个定理,因为欧拉发现的定理实在是太多……辗转相除法的实现,是基于下面的原理(在这里用(a,b)表示a和b的最大公因数):
(a,b)=(a,ka+b),其中a、b、k都为自然数.………………①
也就是说,两个数的最大公约数,将其中一个数加到另一个数上,得到的新数,其公约数不变,比如(4,6)=(4+6,6)=(4,6+2×4)=2.要证明这个原理很容易:如果p是a和ka+b的公约数,p整除a,也能整除ka+b.那么就必定要整除b,所以p又是a和b的公约数,从而证明他们的最大公约数也是相等的.
基于上面的原理,就能实现我们的迭代相减法:
(78,14)=(64,14)=(50,14)=(36,14)=(22,14)=(8,14)=(8,6)=(2,6)=(2,4)=(2,2)=(0,2)=2
基本上思路就是大数减去小数,一直减到能算出来为止,在作为练习的时候,往往进行到某一步就已经可以看出得值.迭代相减法简单,不过步数比较多,实际上我们可以看到,在上面的过程中,由(78,14)到(8,14)完全可以一步到位,因为(78,14)=(14×5+8,14)=(8,14),由此就诞生出我们的辗转相除法.
用辗转相除法求(a,b).设r0=b,r1=a,反复运用除法算式,得到一系列整数qi,ri和下面的方程:
相当于每一步都运用原理①把数字进行缩小,上面右边就是每一步对应的缩小结果,可以看出,最后的余数rn就是a和b的公约数.我们以一个题为例说明基本过程.
例题:求(326,78)
所以(326,78)=2.这和我们用迭代相减法算出来的结果是一样的.所以中学的同学们应该看到,迭代相减法和辗转相除法在本质上是一样的,相对来说,减法比较简单,但是除法步数少.
我们要看到的是,在辗转相除法中,我们必须算到最后一步才知道rn是不是所求的最大公因数,所以我们把n称作辗转相除法里的步数.在明天,我们将利用辗转相除法的过程来导出此方法的步数估计——拉梅定理.
举一反三
已知函数f(x)=x,g(x)=alnx,a∈R.若曲线y=f(x)与曲线y=g(x)相交,且在交点处有相同的切线,求a的值和该切线方程.
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
最新试题
- 1数列1,0,-1,1,0,-1,……则该数列极限是
- 2哪些科学家都为光合作用的探究过程作出了努力?按先后顺序排列
- 3有什么有关月亮的神话故事
- 4描写爸爸品质的作文
- 5人非圣贤,孰能不过,过而能改,善莫大焉,
- 6I turned off the gas,opened all the windows,and then went out of the house.这句话里opened为什么不用opening?中间
- 7是listen to someone to talk对,还是listen to someone talk对
- 8『高中数学』在三角形ABC中,a,b,c分别是内角A,B,C的对边,且C=2B求证c2-b2=2ab(c的平方减b的平方=2ab)
- 9is the most beautiful color in life
- 10师生总共240人去公园,大车每辆限乘50人,租金110元;小车每辆限乘20人,租金50元,怎么租车更省钱?
热门考点
- 1思忖的近义词是什么?
- 2解不等式log以x为底数,tanx为真数大于0.
- 3已知20℃时硝酸钾的溶解度是32g/100g水,若要配制100g 20℃时饱和KNO3溶液,需要KNO3和水各多少克?
- 4用一根长15.7米的绳子在一棵大树上绕了10圈,这棵大树的直径是多少米?
- 5The baby is still crying.It is time to f() him
- 6这章实在学得不好,
- 7“听我说”用英语怎么说
- 8英语各类词的缩写是什么意思?
- 9《我喜欢的一首歌》作文歌曲是《我要的飞翔》六年级的,6百字
- 10水果店运来一批水果,第一天卖出了总量的3分之1,第二天卖出了360千克,还剩下总数的9分之4,这批水果有多少