概念
拉梅定理，是對輾轉相除法的步數估計，用輾轉相除法求(a,b).設r0=b，r1=a，設b≥a。反覆運用除法算式，得到一系列整數qi，ri和下面的方程：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為輾轉相除法的步數。
內容
設b≥a都是正整數，d(a)是a的十進制表示式中數字的個數，若n為輾轉相除法計算最大公因數(a,b)的步數，則：n≤5d(a)比如計算(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＞γn-1，其中γ=(1+√5)/2,也就是我們的黃金分割比。利用這個性質，我們就可以將n提取出來，從而得到n的一個估計。那么：a≥Fn+1＞γn-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)
