書記が数学やるだけ#301 ユークリッドの互除法とフィボナッチ数列，ラメの定理

ユークリッドの互除法をよく見てみると，フィボナッチ数列が浮かび上がってくる。

問題

本問はラメの定理に基づいている。これは，ユークリッドの互除法の計算量が桁数の5倍以下であることを示している。

説明

というのも，ユークリッドの互除法において最も遅くなるパターンが，フィボナッチ数列の隣り合う項の場合である。

解答

ユークリッドの互除法が最も遅くなるパターンについて考えると，(1)の不等式が成り立つことが言える。

(2)はフィボナッチ数列と黄金比の関係から導出する。

この2つを組み合わせると，ラメの定理が導出できる。

本記事のもくじはこちら：