拡張ユークリッド互除法を行列で書く

拡張ユークリッド互除法で実際に不定方程式の解を求めるとき、私は行列算で書くのが好きなのですがあんまりそういう解説を見掛けないのと、実は私もそれを思い出すのにいちいち20分ぐらいかかってしまうという理由でここにメモしておきます。

拡張ユークリッド互除法で $11a+7b=1$ なるa,bを求める方法は、通常次のように「代入」を用いて説明されます:
まず、

とあまりを計算する。これらのうち、「あまり=(gcd)」となっている式までを上から「あまり=わられる数-わる数×商」の形に書き直す。

となる。これを下から順に代入して、

これで、a=2、b=(-3)と求まった。

が、数に数を代入というのが気持ち悪いし、「整理する」のところで何を「係数」と見做して整理していいのかよく分からなくなるので、しばらくすると簡単にやり方を忘れて困ってしまう。そこで、これを行列算で書き直してみる。

ユークリッドの互除法では、(割られる数, 割る数)というペアから(割る数, あまり)というペアを計算するという操作を繰り返す。例えば上の例では、(11, 7)→(7, 3)→(3, 1)→(1, 0)となっている。
このペアに注目して、上の4本の式を行列算で書き直してみる。すると、次のようになる。

$\begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}\begin{pmatrix}11\\7\end{pmatrix} = \begin{pmatrix}7\\4\end{pmatrix}$ (イ)
$\begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}\begin{pmatrix}7\\4\end{pmatrix} = \begin{pmatrix}4\\3\end{pmatrix}$ (ロ)
$\begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}\begin{pmatrix}4\\3\end{pmatrix} = \begin{pmatrix}3\\1\end{pmatrix}$ (ハ)
$\begin{pmatrix}0 & 1 \\\ 1 & -3\end{pmatrix}\begin{pmatrix}3\\1\end{pmatrix} = \begin{pmatrix}1\\0\end{pmatrix}$ (ニ)

ペアの第2要素は第1要素に移るので、係数行列の1行目はかならず(0, 1)になり、2行目はあまりを求めるところなので、(1, -商)となっている。
しらべたかったのは、(11, 7)に何をかけていくと(1, 0)にできるかということなので、まず(イ)の両辺に(ロ)の係数行列をかけてみる。すると、

$\begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}\begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}\begin{pmatrix}11\\7\end{pmatrix} =\begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix} \begin{pmatrix}7\\4\end{pmatrix}$ (イの両辺にロの行列をかける)
$= \begin{pmatrix}4\\3\end{pmatrix}$ (ロを「代入」)

代入するにも、先の章とは違って行列の形が変な代入を防いでくれる。あとは同様のことをすればよく、少し考えると右から

$(ニの行列)(ハの行列)(ロの行列)(イの行列)\begin{pmatrix}11\\7\end{pmatrix} = \begin{pmatrix}1\\0\end{pmatrix}$

となることがわかる。これはまさに我々がはじめ求めたかった形になっていて、答を求めるには左の行列積の連鎖を計算すればよい。

$(ニの行列)(ハの行列)(ロの行列)(イの行列)$
$= \begin{pmatrix}0 & 1 \\\ 1 & -3\end{pmatrix} \begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}\begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}\begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}$
$= \begin{pmatrix}2 & -3 \\\ -7 & 11\end{pmatrix}$

((ちなみにこれを手計算するときは2つずつ組にしてかけ算するとちょっと楽)あとはこの第1行をとって(あるいは両辺に(1, 0)をかけて)、a=2, b=-3がわかる。

まあこう覚えておくと、アルゴリズムにするときもちょっと思い出しやすいんじゃないかなあと思う。