初等数论设a,b是任意两个正整数,由带余数除法,我们有下列等式：a=bq1+r10＜r1＜bb=r1q2+r20＜r2＜r1.rn-2=rn-1qn+rn0＜rn＜rn-1rn-1=rnqn+1+rn+1rn+1=0.（1）（1）式中所指出的计算方法,即为辗转相除法求

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