初等数论

设a,b是任意两个正整数,由带余数除法,我们有下列等式:a=bq1+r10<r1<bb=r1q2+r20<r2<r1.........rn-2=rn-1qn+rn0<rn... 设a,b是任意两个正整数,由带余数除法,我们有下列等式:
a=bq1+r1 0<r1<b
b=r1q2+r2 0<r2<r1
.........
rn-2=rn-1qn+rn 0<rn<rn-1
rn-1=rnqn+1+rn+1 rn+1=0 ................................................(1)
(1)式中所指出的计算方法,即为辗转相除法
求证:(1)式中的n≤2logb/log2
展开
 我来答
风痕云迹_
2012-12-29 · TA获得超过5628个赞
知道大有可为答主
回答量:1676
采纳率:100%
帮助的人:903万
展开全部
如果 b < a/2, 则 r1<b<a/2,
如果 b>=a/2, 则 r1 <= a-b <= a/2
所以, 总有 r1 < a/2

类似 有:
r2<= b/2
r3<= r1/2
...
rn <= r(n-2)/2

将上列式相乘,得:
r2*r3*...*rn <= b/2 * r1/2* ...* r(n-2)/2
===>
r(n-1)rn *2^(n-1)<= b*r1
===>
2^n <= r(n-1)rn *2^(n-1) <= b*r1<=b^2
===> n <= 2logb / log2
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式