初等数论
设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 展开
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 展开
1个回答
展开全部
如果 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
如果 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
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询