Question

初等数论

设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

Answer 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