手順

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

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

i) $m$=0 なら (仕上げ) に進む。

ii) $l$ を $m$ で割った商を $l$, 余りを $r$ とおくと、

$$l= m q +r \qquad (\vert r\vert<\vert m\vert)$$

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

$$\begin{pmatrix} l\\ m \end{pmatrix}= \begin{pmatrix} q & 1\\ 1 & 0 \end{pmatrix}\begin{pmatrix} m\\ r \end{pmatrix}$$

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

$$\begin{pmatrix} m\\ r \end{pmatrix}= \begin{pmatrix} 0 & 1\\ 1 & -q \end{pmatrix}\begin{pmatrix} l\\ m \end{pmatrix}$$

ゆえに

$$\begin{pmatrix} m\\ r \end{pmatrix}= ... ...in{pmatrix} 0 & 1\\ 1 & -q \end{pmatrix}A \begin{pmatrix} a\\ b \end{pmatrix}$$

つまり、$A$ のところを

$$\begin{pmatrix} 0 & 1\\ 1 & -q \end{pmatrix}A$$

に置き換えれば、$m$ のところが $r$ に置き換わる結果になり、 計算が少し進んだことになる。

(仕上げ)さて、 $m=0$ になったはずである。 このとき、

$$A= \begin{pmatrix} x& y \\ z& w \end{pmatrix}$$

とおくと、

$$\begin{pmatrix} l \\ 0 \end{pmatrix}= \begin{pmatrix} x& y \\ z& w \end{pmatrix}\begin{pmatrix} a \\ b \end{pmatrix}$$

だから、

$$a x +b y=l$$ (I)

が成り立つ。

他方、 $\operatorname{det}(A)=\pm 1$ に注意すると、

$$\begin{pmatrix} a \\ b \end{pmatrix}= \pm \begin{pmatrix} w& -y \\ -z& x \end{pmatrix}\begin{pmatrix} l \\ 0 \end{pmatrix}$$

だから、

(II) $a,b$ は $l$ の倍数である。

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

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