COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

ユークリッドの互除法

ユークリッドの互除法

問題≪ラメの定理≫

 $a,$ $b$ を $a > b \geqq 1$ なる整数とし, ユークリッドの互除法の計算 \begin{align*} a &= bq_1+r_1, \quad 0 < r_1 < b, \\ b &= r_1q_2+r_2, \quad 0 < r_2 < r_1, \\ &\ \,\vdots \\ r_{l-2} &= r_{l-1}q_l+r_l, \quad 0 = r_l < r_{l-1} \end{align*} により整数 $l$ と $q_1,$ $\cdots,$ $q_l,$ $r_1,$ $\cdots,$ $r_l$ を定める. また, 数列 $\{ F_n\}$ を \[ F_1 = F_2 = 1, \quad F_{n+2} = F_n+F_{n+1}\] で定め, $\alpha$ を $x^2 = x+1$ の正の解とする. 次のことを示せ.
(1)
$b \geqq F_{l+1}$ が成り立つ.
(2)
$F_{n+1} \geqq \alpha ^{n-1}$ が成り立つ.
(3)
$\alpha ^5 > 10$ である.
(4)
$b$ の桁数が $m$ のとき, $l \leqq 5m$ が成り立つ.

解答例

(1)
与式から \begin{align*} b &\geqq r_1+r_2, \\ &\ \,\vdots \\ r_{k-2} &\geqq r_{k-1}+r_{k} \quad (2 < k < l), \\ &\ \,\vdots \\ r_{l-2} &> r_{l-1} > r_l = 0 \end{align*} が成り立つので, $r_{l-1} = 1,$ $r_{l-2} = 2,$ $\cdots,$ $r_{k-2} = r_{k-1}+r_{k},$ $\cdots,$ $b = r_1+r_2$ のとき, つまり $b = F_{l+1}$ のとき $b$ は最小となる. よって, $b \geqq F_{l+1}$ である.
(2)
$F_{n+1} \geqq \alpha ^{n-1}\ \cdots [*]$ を数学的帰納法で示す.
(i)
$F_2 = 1,$ $F_3 = 2 > \dfrac{1+\sqrt 5}{2} = \alpha$ から, $n = 1,$ $2$ のとき $[*]$ が成り立つ.
(ii)
$n = k,$ $k+1$ ($k$: 正の整数)のとき $[*]$ が成り立つとすると, $\alpha ^2 = 1+\alpha$ であるから \begin{align*} F_{k+3} &= F_{k+1}+F_{k+2} \\ &\geqq \alpha ^{k-1}+\alpha ^k = \alpha ^{k-1}(1+\alpha ) \\ &= \alpha ^{k-1}\alpha ^2 = \alpha ^{k+1} \end{align*} となり, $n = k+2$ のとき $[*]$ が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して $[*]$ が成り立つ.
(3)
$\alpha = \dfrac{1+\sqrt 5}{2}$ であるから, $(1+\sqrt 5)^5 > 10\cdot 2^5 = 320$ を示せばよい. \begin{align*} &(1+\sqrt 5)^5 = (1+\sqrt 5)^4(1+\sqrt 5) \\ &= \{ (1+\sqrt 5)^2\} ^2(1+\sqrt 5) = (6+2\sqrt 5)^2(1+\sqrt 5) \\ &= (56+24\sqrt 5)(1+\sqrt 5) = 176+80\sqrt 5 \end{align*} であるから, $80\sqrt 5 > 144$ を示せばよい. これは $(80\sqrt 5)^2 = 32000 > 20736 = 144^2$ から従う.
(4)
$b < 10^m$ であるから, (1), (2) とあわせると \[\alpha ^{l-1} \leqq F_{l+1} \leqq b < 10^m\] が成り立つ. よって, \[ 10^{l-1} < \alpha ^{5(l-1)} < 10^{5m}\] であるから, $l-1 < 5m$ つまり $l < 5m+1$ が得られる. $l$ は整数であるから, $l \leqq 5m$ が成り立つ.

背景

 本問で示した, 次の事実は「ラメの定理」として知られている: 正の整数 $a,$ $b\ (a > b)$ の最大公約数を求めるユークリッドの互除法の計算回数は, $b$ の桁数の $5$ 倍以下である. この定理により, $b$ が $100$ 桁の整数でも, $a,$ $b$ の最大公約数は高々 $500$ 回の計算で求まることがわかる.