問題はこちら（画像をクリックするとPDFファイルで開きます。）
ラメの定理と呼ばれる、ユークリッドの互除法のアルゴリズムの回数に関する上限を与える定理について考えてみます。
今回はラメの定理の主張を、誘導を付ける形での問題形式として考えてみることにします。
ユークリッドの互除法のアルゴリズムが最も長引くケースにフィボナッチ数列が関わってくる部分に面白さを感じます。
ユークリッドの互除法って何？という方は
ユークリッドの互除法が何なんだ？という方は
確認
-
-
ユークリッドの互除法【原理の証明とイメージ】【2005年度 広島市立大学】
問題はこちら（画像をクリックするとPDFファイルで開きます。） ２つの正整数の最大公約数を求めるときに用いられる「ユークリッドの互除法」と呼ばれるアルゴリズムについて、原理と証明を考えてみます。 古典 ...
続きを見る
で原理とイメージ寄りの話をしています。
ユークリッドの互除法の原理
2 つの整数 \(a\) , \(b\) の最大公約数を \(G(a \ , \ b)\) と表します。
互除法の原理
\(a\) , \(b\) を \(a \gt b\) を満たす正の整数とする。
\(a\) を \(b\) で割った商を \(q\) , 余りを \(r\) とするとき、
\(G(a \ , \ b)=G(b \ , \ r)\)
が成立する。
この原理を用いて２つの数の最大公約数を探すプロセスを、ユークリッドの互除法と言います。
数が大きくなれば、直接素因数分解して共通素因数を求めることが難しくなります。
このユークリッドの互除法はどんどん、割り算をして余りを出すことで、数を小さくしていき最大公約数を求めるアルゴリズムです。
例えば
\(1517\) と \(851\) の最大公約数を求めてみます。
\(1517=851 \cdot 1+666\) より
\(G(1517 \ , \ 851)=G(851 \ , \ 666)\)
\(851=666 \cdot 1+185\) より、
\(G(851 \ , \ 666)=G(666 \ , \ 185)\)
\(666=185 \cdot 3+111\) より、
\(G(666 \ , \ 185)=G(185 \ , \ 111)\)
\(185=111 \cdot 1+74\) より、
\(G(185 \ , \ 111)=G(111 \ , \ 74)\)
\(111=74 \cdot 1+37\) より、
\(G(111 \ , \ 74)=G(74 \ , \ 37)\)
\(74=37 \cdot 2\) より、
\(G(74 \ , \ 37)=37\)
であり、求める最大公約数は \(37\)
このとき、最大公約数を求めるまでに行った割り算の回数は６回です。
今回は、このユークリッドの互除法の割り算の回数の上限についての次の定理
ラメの定理
\(a \gt b\) を満たす２つの正の整数 \(a\) , \(b\) について、\(b\) の桁数を \(M\) 桁とする。
このとき、ユークリッドの互除法によって最大公約数を求めるために行う割り算の回数 \(N\) について
\(N \leq 5M\)
が成立する。
を問題形式にして考えてみます。
問題はこちら（再掲）（画像をクリックするとPDFファイルで開きます。）
割り算の回数について
\(a=bq_{1}+r_{1}\) ( \(1\) 回目の割り算 )
\(b=r_{1}q_{2}+r_{2}\) ( \(2\) 回目の割り算 )
\(r_{1}=r_{2}q_{3}+r_{3}\) ( \(3\) 回目の割り算 )
\(r_{2}=r_{3}q_{4}+r_{4}\) ( \(4\) 回目の割り算 )
\( \ \ \ \ \vdots\)
\(r_{N-3}=r_{N-2}q_{N-1}+r_{N-1}\) ( \(N-1\) 回目の割り算 )
\(r_{N-2}=r_{N-1}q_{N}\) ( \(N\) 回目の割り算 )
\(N\) 回目の割り算の際の余り \(r_{N}\) が \(0\) になったとします。
一番割り算の回数が長引く場合
互除法のアルゴリズムは余りをどんどん考えていくため、この数列 \(\{r_{n}\}\) は
\(r_{1} \gt r_{2} \gt \cdots \gt r_{N-2} \gt r_{N-1} \gt r_{N}=0\)
という単調減少数列です。
\(N\) 回目の割り算で余り \(0\) になるわけなので、いつかは \(0\) になることを考えると、長引くケースというのは
余りが中々減っていかない場合
すなわち、
毎回の割り算における商が \(1\)
となるケースだとイメージができます。
例えば、\(43\) を \(13\) で割った余りは \(43=13 \cdot 3+4\) で、\(4\) 余ります。
- \(43\) から \(13\) を出来る限り取り除いたときの回数 ( \(3\) 回 ) が商
- これ以上取り除けずに残った数 \(4\) が余り
余りが減らないということは、取り除く回数 (商) が小さい方が望ましいわけです。
このことから、互除法のアルゴリズムが一番長引く場合というのは
\(a=b+r_{1}\) ( \(1\) 回目の割り算 )
\(b=r_{1}+r_{2}\) ( \(2\) 回目の割り算 )
\(r_{1}=r_{2}+r_{3}\) ( \(3\) 回目の割り算 )
\(r_{2}=r_{3}+r_{4}\) ( \(4\) 回目の割り算 )
\( \ \ \ \ \ \vdots\)
\(r_{N-3}=r_{N-2}+r_{N-1}\) ( \(N-1\) 回目の割り算 )
\(r_{N-2}=r_{N-1}+r_{N}\) ( \(N\) 回目の割り算 )
※ \(r_{N}=0\)
というように、毎回の商が \(1\) となるケース、つまり
\(r_{k-2}=r_{k-1}+r_{k}\)
というときであることが想像つきます。
これは、フィボナッチ数列が逆順に並んでいるというイメージです。
試しに実験してみる
フィボナッチ数列
\(1\) , \(1\) , \(2\) , \(3\) , \(5\) , \(8\) , \(13\) , \(21\) , \(34\) , \(55\) , \(89\) , \(144\) , \(233\)
と並べてみたときに、例えば
\(233\) と \(144\) の最大公約数について互除法のプロセスを行ってみます。
\(233=144+89\) ( \(r_{1}=89=F_{11}\) )
\(144=89+55\) ( \(r_{2}=55=F_{10}\) )
\(89=55+34\) ( \(r_{3}=34=F_{9}\) )
\(55=34+21\) ( \(r_{4}=21=F_{8}\) )
\(34=21+13\) ( \(r_{5}=13=F_{7}\) )
\(21=13+8\) ( \(r_{6}=8=F_{6}\) )
\(13=8+5\) ( \(r_{7}=5=F_{5}\) )
\(8=5+3\) ( \(r_{8}=3=F_{4}\) )
\(5=3+2\) ( \(r_{9}=2=F_{3}\) )
\(3=2+1\) ( \(r_{10}=1=F_{2}\) )
\(2=1\cdot2\)
というように、余りはフィボナッチ数列を逆順に並べている感じになります。
(1) , (2) ではそのあたりに関する議論について考えるわけです。
(3) 以降はこの (1) , (2) をヒントとして活用できるように設計がしてあります。
問題形式で考えることによって、このラメの定理の主張やストーリーを落とし込んでみてください。