ユークリッドの互除法

ユークリッドの互除法について、ここでは、計算法を中心にして述べる。

1. 問題

整数 a, b が与えられているとする。このとき、 d = gcd(a, b) および

ax + by = d

を満たす x, y を具体的に計算するには、どのようにすればよいか。

2. 方針

整数を成分にもつ二次正方行列 A で、 det(A) = ±1 かつ

(\begin{matrix}l \\ m \end{matrix}) = A (\begin{matrix}a \\ b \end{matrix})

の m ができるだけ絶対値が小さくなるようなものを順次探す。

3. 手順

o) まずは A = E (単位行列) にとる。必然的にこのとき l = a, m = b である。

(計算):次の i),ii) を繰り返す

i) m=0 なら (仕上げ) に進む。 ii) l を m で割った商を l, 余りを r とおくと、

l = mq + r (|r| < |m|)

という関係式が成り立つ。

(\begin{matrix}l \\ m \end{matrix}) = (\begin{matrix}q & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix}m \\ r \end{matrix})

なる関係に着目する。右辺にでてくる二次行列の逆行列は直ちに計算できて、

(\begin{matrix}m \\ r \end{matrix}) = (\begin{matrix}0 & 1 \\ 1 & −q \end{matrix}) (\begin{matrix}l \\ m \end{matrix})

ゆえに

(\begin{matrix}m \\ r \end{matrix}) = (\begin{matrix}0 & 1 \\ 1 & −q \end{matrix}) A (\begin{matrix}a \\ b \end{matrix})

つまり、 A のところを

(\begin{matrix}0 & 1 \\ 1 & −q \end{matrix}) A

に置き換えれば、 m のところが r に置き換わる結果になり、計算が少し進んだことになる。 (仕上げ) さて、 m = 0 になったはずである。このとき、

A = (\begin{matrix}x & y \\ z & w \end{matrix})

とおくと、

(\begin{matrix}l \\ 0 \end{matrix}) = (\begin{matrix}x & y \\ z & w \end{matrix}) (\begin{matrix}a \\ b \end{matrix})

だから、

(I)  ax + by = l

が成り立つ。他方、 det(A) = ±1 に注意すると、

(\begin{matrix}a \\ b \end{matrix}) = ± (\begin{matrix}w & −y \\ −z & x \end{matrix}) (\begin{matrix}l \\ 0 \end{matrix})

だから、 (II) a, b は l の倍数である。

(I),(II) をあわせると、 l は a, b の最大公約数 d と等しくなければならないことが分かる。

すなわち、 (仕上げ) まですすんだところで A の成分の x, y と、 l が求めるものになる。