基本介紹
- 中文名：拉梅定理
- 外文名：LAMÉ’S THEOREM
- 種類：步數估計
定義,舉例,證明,
定義
r0=q1r1+r2，r2<r1 (r2,r1)
r1=q2r2+r3，r3<r2 (r3,r2)
r2=q3r3+r4，r4<r3 (r4,r3)
………………
rn-3=qn-2rn-2+rn-1，rn-1<rn-2 (rn-1,rn-2)
rn-2=qn-1rn-1+rn，rn-2<rn-1 (rn-1,rn)
rn-1=qnrn。 (rn,0)
相當於每一步都運用原理①把數字進行縮小，上面右邊就是每一步對應的縮小結果。我們注意到，我們只有到最後一步的時候，才知道rn是我們所求的最大公約數，所以稱n為輾轉相除法的步數。
舉例
比如計算(326,78)中，由於d(78)=2，用拉梅定理至多需要10步，但是實際上只需要5步。
證明
最後的餘數rn就是a和b的公約數。我們應該看到，依次得到的ri是遞減的，即有：r1>r2>r3>r4>……>rn-2>rn-1>rn。從而可以知道，所有的qi≥1。並且在最後一步的時候，qn≥2，因為若qn≤1，則有rn-1≤rn，與ri 的嚴格遞減矛盾。考慮菲波拉契數列：
F0=0，F1=1，Fn+1=Fn+Fn-1。
在輾轉相除法的那些方程里，從最後一步往前看。首先rn≥1=F2;rn-1=qnrn≥2=F3;更一般地，利用數學歸納法可以證明：
對j≥0有：rn-j≥Fj+2。
歸納步驟為：
rn-j-1=rn-jqn-j+rn-j+1
≥rn-j+rn-j+1(因為qn-j≥1)
≥Fn-j+Fn-j+1=Fj+3。
從而證明了rn-j≥Fj+2(你可以看到這個式子的左右兩邊角標之和為n+2)，那么自然有：
a=r1≥Fn+1。到這裡總算是找到了a和n的一個不等關係，我們就有可能通過他來得到關於n的一個估計。
幸好，在菲波拉契數列中有下面的性質：
Fn+1>γ，其中γ=(1+√5)/2,也就是我們的黃金分割比。利用這個性質，我們就可以將n提取出來，從而得到n的一個估計。那么：a≥Fn+1>γ，兩邊取常數對數：
lga>(n-1)lgγ>(n-1)/5。因為lgγ>1/5.
所以n-1<5lga<5(|lga|+1)
而|lga|+1其實就等於數a在十進制下數字的個數，比如23的個數就是2,568的數字個數就是3等，這個就給我們帶來了一個非常直觀化的估計。為了方便，我們記d(a)=|lga|+1,那么就有：
n<5d(a)+1≤5d(a)
