ユークリッドの互除法の解析を続ける．

　ユークリッドの互除法が最悪の場合は隣接するフィボナッチ数である場合に生じることになる．その場合の除算ステップは高々

　　［ｌｏｇ（３−φ）Ｎ／ｌｏｇφ］

である．

（証）ｕ＝Ｆn+1，ｕ＝Ｆn （ｍｏｄｖ）

　　　Ｆn+1＜Ｎ→φ^n+1／√５＜Ｎ→φ^n＜√５／φ・Ｎ＝（３−φ）Ｎ

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　除算ステップの回数は

　　［ｌｏｇ（３−φ）Ｎ／ｌｏｇφ］

＝２．０７８ｌｎＮ＋．６７２３

＝４．７８５ｌｏｇ10Ｎ＋．６７２３

＝４．８ｌｏｇ10Ｎ−０．３２

を超えないのである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝