§A4.1整除・余りとユークリッドの互除法

閑話休題：現役最古のアルゴリズム ユークリッドの互除法は、ユークリッドの『原論』（紀元前300年頃）第7巻に載っている手続きである。計算機科学者ドナルド・クヌースは著書『The Art of Computer Programming』で、互除法を「今なお使われている最古の非自明なアルゴリズム」と呼んだ。約2300年前に書かれた手順は、今日も電卓やコンピュータの中で、分数の約分や暗号処理に使われている。

1844年、フランスの数学者ガブリエル・ラメは、互除法の計算回数と入力の大きさの関係を、隣り合うフィボナッチ数を用いて明らかにした。ラメの結果は、具体的なアルゴリズムの実行時間を数学的に解析した最初期の成果とされ、しばしば「アルゴリズム解析という分野の誕生」の一つに数えられる。たとえば、$21$と$13$に互除法を適用すると、

となる。この計算では、最後の除法を除いて商が$1$であり、最後の商は$2$である。

$F_1=F_2=1$、$F_{n+2}=F_{n+1}+F_n$（$n\ge1$）によってフィボナッチ数を定める。正整数$A>B$に対して、最後の余り$0$の除法も含めて互除法が$k\ge2$回の除法を要するならば、$A\ge F_{k+2}$、$B\ge F_{k+1}$である。実際、余りを$r_0=A,r_1=B,\ldots,r_k>0,r_{k+1}=0$とし、各除法を$r_{i-1}=q_i r_i+r_{i+1}$（$1\le i\le k$）と書く。余りは狭義に減少するので、最後の商は$q_k\ge2$、それ以外の商は$q_i\ge1$である。したがって、$r_k\ge1=F_2$、$r_{k-1}=q_k r_k\ge2=F_3$であり、$r_i\ge r_{i+1}+r_{i+2}$（$0\le i\le k-2$）を逆向きに用いる帰納法から$r_i\ge F_{k-i+2}$（$0\le i\le k$）を得る。入力を$(A,B)=(F_{k+2},F_{k+1})$とすると、最後の商が$2$、それ以外の商が$1$となり、ちょうど$k$回で停止するので、二つの下界に等号が成立する。上の計算は$k=6$の場合である。