自分用メモ。

Euclid整域

\(R\) はEuclid整域で、 \(R\) 上の関係 \(\prec\) はwell-foundedな前順序であるとする。

Euclid整域の公理：\(x, y\in R, y\ne 0\) に対して、\(x=qy+r, r\prec y\) を満たす \(q, r\in R\) が存在する（一意性は要求しない）。

特に、この公理から、 0 は \(\prec\) に関する最小元であることがわかる。

TODO: この定式化で良い？

互除法

\(x_0=x, x_1=y\) とおき、 \(\prec\) に関する減少列 \(\{x_k\}\) を \(x_{k-1}=q_{k} x_{k}+x_{k+1}\) を満たすように取る。（途中の商と余りには任意性があるが、ここでは1つ固定する）

関係 \(\prec\) がwell-foundedなので、この列は有限列である。つまり、ある \(n\) について \(x_{n+1}=0\) となる。このとき、 \(x_n\) が \(x\) と \(y\) の最大公約数である。

このとき、 \(x_n=u x + v y\) となる \(u\), \(v\) も同時に求めるのが、拡張されたユークリッドの互除法である。

列 \(\{x_k\}\) と初項 \(x_0, x_1\) の関係を、行列を使って書けば次のようになる：

\begin{align*}
\begin{pmatrix}x_k\\x_{k+1}\end{pmatrix}&=\begin{pmatrix}0&1\\1&-q_{k}\end{pmatrix}\begin{pmatrix}x_{k-1}\\x_{k}\end{pmatrix} \\
&=\begin{pmatrix}0&1\\1&-q_{k}\end{pmatrix}\cdots\begin{pmatrix}0&1\\1&-q_{1}\end{pmatrix}\begin{pmatrix}x_{0}\\x_{1}\end{pmatrix}.
\end{align*}

この右辺の係数を1つの行列で書きたい。そのために、数列 \(\{u_k\}\), \(\{v_k\}\) を、次により定める：

\begin{align*}
\begin{pmatrix}u_0&v_0\\u_1&v_1\end{pmatrix}&=\begin{pmatrix}1&0\\0&1\end{pmatrix},\\
\begin{pmatrix}u_k&v_k\\u_{k+1}&v_{k+1}\end{pmatrix}&=\begin{pmatrix}0&1\\1&-q_{k}\end{pmatrix}\begin{pmatrix}u_{k-1}&v_{k-1}\\u_{k}&v_{k}\end{pmatrix} & (k>0).
\end{align*}

すると、 \(\begin{pmatrix}0&1\\1&-q_{k}\end{pmatrix}\cdots\begin{pmatrix}0&1\\1&-q_{1}\end{pmatrix}=\begin{pmatrix}u_k&v_k\\u_{k+1}&v_{k+1}\end{pmatrix}\) なので、列 \(\{x_k\}\) と初項 \(x_0, x_1\) の関係は、

\[\begin{pmatrix}x_k\\x_{k+1}\end{pmatrix}=\begin{pmatrix}u_k&v_k\\u_{k+1}&v_{k+1}\end{pmatrix}\begin{pmatrix}x_{0}\\x_{1}\end{pmatrix}\]

となる。特に \(k=n\) の場合は

\[\begin{pmatrix}x_n\\0\end{pmatrix}=\begin{pmatrix}u_n&v_n\\u_{n+1}&v_{n+1}\end{pmatrix}\begin{pmatrix}x_{0}\\x_{1}\end{pmatrix}\]

であり、 \(x_n=u_n x_0+v_n x_1\) となる。この \(u_n\) と \(v_n\) が求める \(u\), \(v\) である。

行列を使わずに書くと、 \(u_k\), \(v_k\) の初期値は

\begin{align*}
u_0&=1, & v_0&=0, \\
u_1&=0, & v_1&=1,
\end{align*}

で、漸化式は

\begin{align*}
x_{k-1}&=q_k  x_k+x_{k+1} & \text{(除算)}, \\
u_{k+1}&=u_{k-1}-q_k u_k, \\
v_{k+1}&=v_{k-1}-q_k v_k
\end{align*}

である。

実装例

Haskell による実装例：

-- (u,v,g) = extGcd x y
-- abs g == gcd x y, g == u * x + v * y
extGcd :: Integer -> Integer -> (Integer,Integer,Integer)
extGcd = loop 1 0 0 1
  where
    loop u v u' v' x 0 = (u,v,x)
    loop u v u' v' x y = case quotRem x y of
      (q,r) -> loop u' v' (u - q * u') (v - q * v') y r

実行例：

*Main> extGcd 12 7
(3,-5,1)
*Main> 12 * 3 + 7 * (- 5)
1
*Main> extGcd 12 78
(-6,1,6)
*Main> 12 * (-6) + 78 * 1
6
*Main> extGcd 12 0
(1,0,12)
*Main> extGcd (-75) 36
(1,2,-3)
*Main> (-75) * 1 + 36 * 2
-3