UC知道初等数论 辗转相除法
来源：百度知道 编辑：UC知道 时间：2024/07/04 02:27:08
辗转相除法：
对于a，b两个任意正整数，由带余除法
a=b*q1+r1,0<r1<b,
b=r1*q2+r2,0<r2<r1,
…………
r(n-2)=r(n-1）*q（n）+r(n),0<r(n)<r(n-1),
r(n-1)=r(n)*q（n+1)+r(n+1),r(n+1)=0.
求证：n<=2*logb/log2
对于a，b两个任意正整数，由带余除法
a=b*q1+r1,0<r1<b,
b=r1*q2+r2,0<r2<r1,
…………
r(n-2)=r(n-1）*q（n）+r(n),0<r(n)<r(n-1),
r(n-1)=r(n)*q（n+1)+r(n+1),r(n+1)=0.
求证：n<=2*logb/log2
由于qi》1
a》b+r1
b》r1+r2
...
r(n-2)》r(n-1)+rn
r(n-1)>rn》1
r（n-1）》2
设f1=rn=1，f2=r（n-1）=2
f（k+2）=f（k+1）+fk 为斐波那契数列（变式）
则ri》f（n+1-i）
b》f(n+1)
由特征根法求出fn通项公式即可
再证b方》2的n次幂
特征根法：
http://baike.baidu.com/view/1424477.htm?func=retitle
http://iask.sina.com.cn/b/2452802.html?from=related