はじめに
ラメの定理 (Lame's theorem) はユークリッドの互除法による最大公約数 (GCD, Greatest Common Divisor) の計算に関して、必要なステップ数を評価する定理である。
THE EUCLIDEAN ALGORITHM II に定理のステートメントと証明が記載されているので、行間を補いつつ、紹介する。
準備
自然数 \(s, t \left( s \geq t \right)\) に対して GCD の計算に必要な割り算の回数が \(n\) であるとする。
- (1) \(s = t q_{1} + r_{1}, 0 < r_{1} < t\)
- (2) \(t = r_{1} q_{2} + r_{2}, 0 < r_{2} < r_{1}\)
- (3) \(r_{1} = r_{2} q_{3} + r_{3}, 0 < r_{3} < r_{2}\)
- (4) \(r_{2} = r_{3} q_{4} + r_{4}, 0 < r_{4} < r_{3}\)
- (5) \(r_{3} = r_{4} q_{5} + r_{5}, 0 < r_{5} < r_{4}\)
- \(\ldots\)
- (n-1) \(r_{n-3} = r_{n-2} q_{n-1} + r_{n-1}, 0 < r_{n-1} < r_{n-2}\)
- (n) \(r_{n-2} = r_{n-1} q_{n} + 0\)
ここで \(q_{i} \geq 1\) であるので
- (2') \(t \geq r_{1} + r_{2}\)
- (3') \(r_{1} \geq r_{2} + r_{3}\)
- (4') \(r_{2} \geq r_{3} + r_{4}\)
- (5') \(r_{3} \geq r_{4} + r_{5}\)
- \(\ldots\)
などを得る。
(2') と (3') より \(t \geq 2 r_{2} + r_{3}\) 、更に (4') より \(2 r_{2} + r_{3} \geq \left( 2 r_{3} + 2 r_{4} \right) + r_{3}\) を得る。同様に (5') より \(3 r_{3} + 2 r_{4} \geq \left( 3 r_{4} + 3 r_{5} \right) + 2 r_{4}\) など。この手順を続けていくと、係数にフィボナッチ数列が現れていることに気が付く。ここで \(F_{n}\) は \(n\) 番目のフィボナッチ数を表す。
余りの列は単調減少で \(r_{n - 1}\) は最後のゼロではない余りであるから
(上記より \(r_{n - 2} \geq 2\) に注意する)
従って
を得る。
ここまでの議論により \(s, t\) の GCD の計算に必要な割り算の回数を \(n\) としたとき \(t\) は \(n + 1\) 番目のフィボナッチ数以上になることが解った。
定理
二数の GCD を得るのに要する除算の回数は、二数の内の小さい方の数の桁数の 5 倍を超えない。
この定理は 1844 年に Gabriel Lamé によって示された。
証明
\(F_n\) を \(n\) 番目のフィボナッチ数とする。つまり
とする。この時、黄金比を \(\phi = \left( 1 + \sqrt{5} \right) / 2\) と書くと \(\phi\) と \(F_{n}\) に関して次が成り立つ。
このことは \(\phi^{2} = \phi + 1\) の両辺に \(\phi\) を乗じる操作を繰り返すことを考えると解る。詳細は THE GOLDEN RATIO; COMPUTATIONAL CONSIDERATIONS にて。
\(2 > \phi = \left( 1 + \sqrt{5} \right) / 2\) であるので
である。左辺は \(F_{n} + F_{n} + F_{n-1} = F_{n} + F_{n + 1} = F_{n + 2}\) であり、右辺は \(\phi^{n} = F_{n} \phi + F_{n - 1}\) であるので
を得る。
\(n\) を \(n - 1\) で置き換えて、先の結果 (\(t \geq F_{n + 1}\)) を使うと
を得る。
- \(d\) を \(t\) の桁数とすると \(d > \log t\)
- \(\log t > \left(n - 1 \right) \log \phi\)
- \(\log \phi > 1 / 5\)
従って \(d > \left(n - 1 \right)/5\) つまり \(n \le 5 d\) を得る。