§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$の場合です。