ユークリッドの互除法の最悪ケース

結論は正しいけど導く過程が何か間違っている。

最悪のケースの美しさ

ここで、どんな場合に互除法が最も苦戦するかを考えてみましょう。余りで割ることを繰り返しているのですから、この余りがなるべく減らないような整数の対を用意すればいいことになります。m > n な自然数mを自然数nで割った余りの最大値はn-1ですから、「余りを最大にする最小のm」は、n + n - 1 = 2n - 1です。これが常に繰り返される場合、互除法の繰り返し数も最大になるわけです。

http://blog.livedoor.jp/dankogai/archives/50966150.html

がその次の

今度は、その互除法を逆から追って見ましょう。まずn = 1の場合。これだとmもまた1になります。n = 2 では?mは3。以下、nとmの対は(3,5),(5,8),(8,13)....と増えていきます。どこかで見た数ではありませんか?

そうです。フィボナッチ数です。互除法が最も苦戦するのは、数の対が隣り合うフィボナッチ数になっている時なのです。互除法での繰り返しは、(F(n+1), F(n))の組み合わせの時に、n回となります。

http://blog.livedoor.jp/dankogai/archives/50966150.html

の説明になっていない件について。「余を最大にする最小の m」 で 「常に繰り返される」というのが意味不明。とにかくこの m = 2n-1 という式と、下の最悪の場合であるフィボナッチ数列の説明は直接関係がない。実際 (2*5-1 = 9 ≠ 8) だし (2*8-1=15≠13) なので。

調べてみたら ここに非常にわかりやすい説明があった。