難関大学合格にむけた数学の入試問題の解説をしています。問題はこちら(画像をクリックするとPDFファイルで開きます。)ラメの定理と呼ばれる、ユークリッドの互除法のアルゴリズムの回数に関する上限を与える定理について考えてみます。今回はラメの定理の主張を、誘導を付ける形での問題形式として考えてみることにします。ユークリッドの互除法のアルゴリズムが最も長引くケースにフィボナッチ数列が関わってくる部分に面白さを感じます。こちら(画像をクリックするとPDFファイルで開きます。2つの正整数の最大公約数を求めるときに用いられる「ユークリッドの互除法」と呼ばれるアルゴリズムについて、原理と証明を考えてみます。...続きを見るで原理とイメージ寄りの話をしています。満たす正の整数とする。この原理を用いて2つの数の最大公約数を探すプロセスを、ユークリッドの互除法と言います。数が大きくなれば、直接素因数分解して共通素因数を求めることが難しくなります。このユークリッドの互除法はどんどん、割り算をして余りを出すことで、数を小さくしていき最大公約数を求めるアルゴリズムです。最大公約数を求めてみます。\(37\)このとき、最大公約数を求めるまでに行った割り算の回数は6回です。