ユークリッドの互除法 - 現実と数学の区別が付かない

正整数 $m,n$ の最大公約数（the greatest common divisor）を $\mathrm{gcd}(m,n)$ で表します． $\mathrm{gcd}(m,n)$ の計算方法として，ユークリッドの互除法がよく知られています．
ja.wikipedia.org

$\mathrm{gcd}(m,n)$ に対しては，\begin{align}am+bn=\mathrm{gcd}(m,n)\end{align}となる整数 $a,b$ が存在します（上記Wikipediaの「拡張された互除法」の項を参照）．また， $m,n$ は共に $\mathrm{gcd}(m,n)$ の倍数なので，\begin{align}m=k\cdot \mathrm{gcd}(m,n),~~n=\ell\cdot\mathrm{gcd}(m,n)\end{align}となる自然数 $k,\ell$ が存在します．ユークリッドの互除法を利用して $\cfrac{n}{m}=\cfrac{\ell}{k}$ と約分を計算することが出来ますが，一旦 $\mathrm{gcd}(m,n)$ を計算して，それから $m,n$ を $\mathrm{gcd}(m,n)$ で割り算をするのは結構面倒に感じることがあります．

今回紹介するのは，ユークリッドの互除法の計算を一工夫することで上記の\begin{align}\mathrm{gcd}(m,n),a,b,k,\ell\end{align} を一度に全部に計算する方法です．

ユークリッドの互除法はイデアルの生成系の書き換え

正整数 $m,n$ に対するユークリッドの互除法は，数列 $a_i$ を
\begin{align}
\left\{
\begin{array}{l}
a_1=m,~ a_2=n,\\
a_{i+2}=(\mbox{$a_{i+1},~a_i$ の大きい方を小さい方で割った余り})
\end{array}
\right.
\end{align}と定義し，初めて $0$ となる直前の $a_i$ が $\mathrm{gcd}(m,n)$ となるというものですが，この記事では次のように定義します．

正整数のペア $m,n$ から始め，大きい方の数を「大きい方の数を，小さい方の数で割った余り」に取り換えるという操作を，片方が $0$ になるまで繰り返す．

例えば $455,663$ の場合は\begin{align}
455,663 \longrightarrow 455,208 \longrightarrow 39, 208 \longrightarrow 39, 13 \longrightarrow 0,13
\end{align}といった具合で， $\mathrm{gcd}(455,663)=13$ が求まります．

同じ数を2回書くので表記としては冗長ですが，ユークリッドの互除法を「イデアルの生成系の書き換え」と解釈するとこのように書くことが妥当に思えます．

可換環 $R$ に対し， $a_1,\dots,a_r\in R$ が生成するイデアルを \begin{align} \langle a_1,\dots,a_r\rangle=\{a_1x_1+\dots+a_rx_r \mid x_1,\dots,x_r \in R\}\end{align}と書くことにします．任意の $a,b,q\in R$ に対し \begin{align}\langle a,b\rangle=\langle a, b-aq\rangle \end{align}であることが簡単に証明できます．このことから，ユークリッドの互除法の計算過程に現れる数のペアが生成する有理整数環 $\mathbb{Z}$ のイデアルは変わらないことが分かります．先ほどの $455,663$ を例に取ると\begin{align}
\langle 455,663\rangle = \langle 455,208 \rangle= \langle 39, 208 \rangle = \langle 39, 13 \rangle = \langle 13 \rangle
\end{align}となります．

これをちゃんと理解すると，ユークリッドの互除法の計算過程で正の数こだわる必要はなく，負の数を使ってもいいことが分かります．例えば
\begin{align}\langle 102,531\rangle=\langle 102,21\rangle=\langle -3,21\rangle=\langle 3\rangle\end{align}より $\mathrm{gcd}(102,531)=3$ というように計算できます．

また， $\mathrm{gcd}(m,n)\in\langle m,n\rangle$ なので $am+bn=\mathrm{gcd}(m,n)$ となる整数 $a,b$ が存在することも自然に分かります．

アルゴリズム

$\mathrm{gcd}(m,n)$ と
\begin{gather}am+bn=\mathrm{gcd}(m,n)\\
m=k\cdot \mathrm{gcd}(m,n),~~n=\ell\cdot\mathrm{gcd}(m,n)
\end{gather}を満たす $a,b,k,\ell$ を一度に全て計算する方法を紹介しましょう．

方法自体は単純で $\left[ \begin{array}{c:cc} m & 1 & 0\\ n & 0 & 1 \end{array} \right]$ という行列を用意して，第１列だけ見るとユークリッドの互除法になるように行基本変形していくだけです．

まず具体例を見てみます． $455$ と $663$ の場合，

$\left[ \begin{array}{c:cc} 455 & 1 & 0\\ 663 & 0 & 1 \end{array} \right] \xrightarrow{\mbox{第2行から第1行の1倍を引く}} \left[ \begin{array}{c:cc} 445 & 1 & 0\\ 208 & -1 & 1 \end{array} \right]$

$\hspace{36mm} \xrightarrow{\mbox{第1行から第2行の2倍を引く}} \left[ \begin{array}{c:cc} 39 & 3 & -2\\ 208 & -1 & 1 \end{array} \right]$

$\hspace{36mm} \xrightarrow{\mbox{第2行から第1行の5倍を引く}} \left[ \begin{array}{c:cc} 39 & 3 & -2\\ 13 & -16 & 11 \end{array} \right]$

$\hspace{36mm} \xrightarrow{\mbox{第1行から第2行の3倍を引く}} \left[ \begin{array}{c:cc} 0 & 51 & -35\\ 13 & -16 & 11 \end{array} \right]$
この計算結果から， $455$ と $663$ の最大公約数は $13$ で，

$\left[ \begin{array}{cc} 51 & - 35 \\ {-}16 & 11 \end{array} \right] \left[ \begin{array}{c} 455\\ 663 \end{array} \right] = \left[ \begin{array}{c} 0\\ 13 \end{array} \right]$
であることが分かります (ガウスの消去法で逆行列を計算する方法と同じ考え方です)．行列の第2行目 $\left[-16,11\right]$ から
\begin{align}
(-16)\cdot 455+11\cdot 663=13
\end{align}であることが分かり，行列の第1列目 $\left[51,-35\right]$ から， $455, 663$ がそれぞれ最大公約数 $13$ の何倍であるかの情報
\begin{align}
455=13\times35,~~ 663=13\times 51
\end{align}が得られます．

定理の形にまとめておきます．

$m,n$ を正整数とする． $\left[ \begin{array}{c:cc} m & 1 & 0\\ n & 0 & 1 \end{array} \right]$ を，第1列だけ見るとユークリッドの互除法になるように行基本変形をすると，
$\left[ \begin{array}{c:cc} g & a & b\\ 0 & c & d \end{array} \right]$ または $\left[ \begin{array}{c:cc} 0 & c & d\\ g & a & b \end{array} \right]$
という形の行列になる( $g>0,a,b,c,d$ は整数)．このとき $m$ と $n$ の最大公約数は $g$ であり \begin{gather}
a m+b n=g\\
m=|d| \cdot g,~~ n=|c|\cdot g
\end{gather}が成り立つ．

一応証明しておきましょう．

$\mathrm{gcd}(m,n)=g$ であることはユークリッドの互除法で最大公約数が求まることから分かります．第1列だけ見るとユークリッドの互除法になるように行基本変形をしていくということは，左から $\left[ \begin{array}{cc} 1 & -q\\ 0 & 1 \end{array} \right]$ または $\left[ \begin{array}{cc} 1 & 0\\ {-}q & 1 \end{array} \right]$ という形の基本行列 (ただし $q$ は正整数) を掛けていくということです．いずれの場合も同様なので，最終的に $\left[ \begin{array}{c:cc} g & a & b\\ 0 & c & d \end{array} \right]$ となる場合だけを考えます．第2，3列からなる2次正方行列 $\left[ \begin{array}{cc} a & b\\ c & d \end{array} \right]$ は，初期状態が単位行列で，それに変形過程の行基本変形に対応する基本行列が左からかけられていったものなので，それらの基本行列の積になっています．
つまり， $\left[ \begin{array}{c:cc} m & 1 & 0\\ n & 0 & 1 \end{array} \right]$ に左から $\left[ \begin{array}{cc} a & b\\ c & d \end{array} \right]$ を掛けると $\left[ \begin{array}{c:cc} g & a & b\\ 0 & c & d \end{array} \right]$ となるということです．

特に $\left[ \begin{array}{cc} a & b\\ c & d \end{array} \right] \left[ \begin{array}{c} m\\ n \end{array} \right] = \left[ \begin{array}{c} g\\ 0 \end{array} \right]$ が成り立ちます．よって $am+bn=g$ です．

また， $cm+dn=0$ が成り立っていますが，これは $(c,d)$ が syzygy加群\begin{align}
\mathrm{Syz}(m,n):=\{(r_1,r_2)\in \mathbb{Z}^2\mid r_1m+r_2n=0\}
\end{align}の元であることを示しています．syzygy加群 $\mathrm{Syz}(m,n)$ は $\left(\frac{n}{g},-\frac{m}{g}\right)$ で生成されます．このことから， $\mathrm{Syz}(m,n)$ の元 $(r_1,r_2)$ で $\mathrm{gcd}(|r_1|,|r_2|)=1$ を満たすものは $\mathrm{Syz}(m,n)$ の生成元である $\pm \left(\frac{n}{g},-\frac{m}{g}\right)$ しかないことが分かります．

一方で $\left[ \begin{array}{cc} a & b\\ c & d \end{array} \right]$ は行列式が $1$ である行列の積なので，この行列自身の行列式も $1$ です．よって $\begin{align} \mathrm{det} \left[ \begin{array}{cc} a & b\\ c & d \end{array} \right]=ad-bc=1 \end{align}$ となります．これは $\mathrm{gcd}(|c|,|d|)=1$ であることを示しています．よって $(c,d)$ は $\mathrm{Syz}(m,n)$ の生成元であり， $|c|=\frac{n}{g}, |d|=\frac{m}{g}$ が成り立ちます．つまり $m=|d| \cdot g,~~ n=|c|\cdot g$ となります．

応用

約分

第184回数学検定 1級 1次：計算技能検定で出題された問題を解いてみましょう．
http://amateurmath.web.fc2.com/files/184-1-1.pdf

次の分数は約分できますか。できるならば、約分してもっとも簡単な分数で表し、できないならば「約分できない」と答えなさい。
\begin{align}\frac{10033}{12877}\end{align}

行基本変形
$\left[ \begin{array}{c:cc} 10033 & 1 & 0\\ 12877 & 0 & 1 \end{array} \right] \to \left[ \begin{array}{c:cc} 10033 & 1 & 0\\ 2844 & -1 & 1 \end{array} \right] \to \left[ \begin{array}{c:cc} 1501 & 4 & -3\\ 2844 & -1 & 1 \end{array} \right]$

$\to \left[ \begin{array}{c:cc} 1501 & 4 & -3\\ 1343 & -5 & 4 \end{array} \right] \to \left[ \begin{array}{c:cc} 158 & 9 & -7\\ 1343 & -5 & 4 \end{array} \right] \to \left[ \begin{array}{c:cc} 158 & 9 & -7\\ 79 & -77 & 60 \end{array} \right]$

$\to \left[ \begin{array}{c:cc} 0 & 163 & -127\\ 79 & -77 & 60 \end{array} \right]$ より， \begin{align}\frac{10033}{12877}=\frac{127}{163} \end{align}

合同式での乗法逆元

第372回数学検定 1級 1次：計算技能検定で出題された問題を解いてみましょう．
http://amateurmath.web.fc2.com/files/372-1-1.pdf

次の合同方程式の解のうち、 $0 \le x < 79$ を満たす整数 $x$ を求めなさい。\begin{align}
65x \equiv 3 ~(\mathrm{mod} ~79)\end{align}

行基本変形
$\left[ \begin{array}{c:cc} 65 & 1 & 0\\ 79 & 0 & 1 \end{array} \right] \to \left[ \begin{array}{c:cc} 65 & 1 & 0\\ 14 & -1 & 1 \end{array} \right] \to \left[ \begin{array}{c:cc} {-}5 & 6 & -5\\ 14 & -1 & 1 \end{array} \right]$

$\to \left[ \begin{array}{c:cc} {-}5 & 6 & -5\\ {-}1 & 17 & -14 \end{array} \right] \to \left[ \begin{array}{c:cc} {-}5 & 6 & -5\\ 1 & -17 & 14 \end{array} \right]$
より $(-17)\cdot 65 \equiv 1 ~(\mathrm{mod} ~79)$ ．\begin{align}
65x &\equiv 3 ~&(\mathrm{mod} ~79)\\
(-17)\cdot65x &\equiv (-17)\cdot3 ~&(\mathrm{mod} ~79)\\
x &\equiv -51 ~&(\mathrm{mod} ~79)\\
x &\equiv 28 ~&(\mathrm{mod} ~79)
\end{align}なので，条件を満たすものは $x=28$ .