一次不定方程式と行列 - NTMRの数学メモ

　自然数 $m,n$ に対して不定方程式 $mx+ny={\rm gcd}(m,n)$ の整数解 $(x,y)$ の１つを、行列を用いて求める方法について考えます。

　前半は高校数学で扱うように、ユークリッド互除法を用います。

【前半】
$r_0=m,r_1=n$ とおくと, ある非負整数 $r_2,r_3, \cdots ,r_n, q_1,q_2, \cdots , q_{n-1}$ が存在して,
　 $r_0=r_1q_1+r_2 \hspace{5pt} (0 \lt r_2 \lt r_1)$
　 $r_1=r_2q_2+r_3 \hspace{5pt} (0 \lt r_3 \lt r_2)$
　 $\hspace{15pt} \vdots$
　 $r_{n-2}=r_{n-1}q_{n-1}+r_n \hspace{5pt} (0 \lt r_n \lt r_{n-1})$
が成り立つ.

すなわち, 整数 $k \, (2 \leq k \leq n)$ に対して
　 $r_{k-2}=r_{k-1}q_{k-1}+r_k$
より
　 $r_k=r_{k-2}-r_{k-1}q_{k-1}$
であるから, $x_k,y_k$ を整数とすると,
　 $r_{k-1}x_k+r_ky_k \\ = r_{k-1}x_k+(r_{k-2}-r_{k-1}q_{k-1})y_k \\ = r_{k-2}y_k +r_{k-1}(x_k-q_{k-1}y_k)$
が成り立つ.

ここで
　 $x_{k-1}=y_k \\ y_{k-1}=x_k-q_{k-1}y_k$
とおくと $x_{k-1},y_{k-1}$ は整数で,
　 $r_{k-2}x_{k-1}+r_{k-1}y_{k-1}=r_{k-1}x_k+r_ky_k$
が成り立つ.
よって $x_n=0, y_n=1$ とすると,
　 $r_0x_1+r_1y_1 = r_1x_2+r_2y_2 = \cdots = r_{n-1}x_n+r_ny_n=r_n$
となり, 特に $r_n={\rm gcd}(r_0,r_1)$ のとき
　 $r_0x_1+r_1y_1={\rm gcd}(r_0,r_1) \hspace{5pt} \therefore mx_1+ny_1={\rm gcd}(m,n)$
が成り立つので $(x,y)=(x_1,y_1)$ は不定方程式 $mx+ny={\rm gcd}(m,n)$ の整数解の１つである.

　　さて、後半ではようやく行列を使います。

【後半】
整数 $k \, (2 \leq k \leq n)$ に対して
　 $x_{k-1}=y_k \\ y_{k-1}=x_k-q_{k-1}y_k$
より,
　 $\left( \begin{array}{c} x_{k-1} \\ y_{k-1} \end {array} \right) = \begin{pmatrix} 0 & 1 \\ 1 & -q_{k-1} \end{pmatrix} \left( \begin{array}{c} x_k \\ y_k \end {array} \right)$
したがって,
　 $\left( \begin{array}{c} x_1 \\ y_1 \end {array} \right) \\ = \begin{pmatrix} 0 & 1 \\ 1 & -q_1 \end{pmatrix} \left( \begin{array}{c} x_2 \\ y_2 \end {array} \right) \\ = \begin{pmatrix} 0 & 1 \\ 1 & -q_1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -q_2 \end{pmatrix} \left( \begin{array}{c} x_3 \\ y_3 \end {array} \right) \\ \hspace{15pt} \vdots \\ = \begin{pmatrix} 0 & 1 \\ 1 & -q_1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -q_2 \end{pmatrix} \cdots \begin{pmatrix} 0 & 1 \\ 1 & -q_{n-1} \end{pmatrix}\left( \begin{array}{c} x_n \\ y_n \end {array} \right) \\ = \begin{pmatrix} 0 & 1 \\ 1 & -q_1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -q_2 \end{pmatrix} \cdots \begin{pmatrix} 0 & 1 \\ 1 & -q_{n-1} \end{pmatrix}\left( \begin{array}{c} 0 \\ 1 \end {array} \right)$

　具体例で試してみましょう。

　 $19=11 \cdot 1+8 \\ 11=8 \cdot 1+3 \\ 8=3 \cdot 2+2 \\3=2 \cdot 1+1$
であり,
　 $\begin{pmatrix} 0&1 \\ 1&-1 \end{pmatrix} \begin{pmatrix} 0&1 \\ 1&-1 \end{pmatrix} \begin{pmatrix} 0&1 \\ 1&-2 \end{pmatrix} \begin{pmatrix} 0&1 \\ 1&-1 \end{pmatrix} \left( \begin{array}{c} 0 \\1 \end{array} \right) \\ = \begin{pmatrix} 0&1 \\ 1&-1 \end{pmatrix} \begin{pmatrix} 0&1 \\ 1&-1 \end{pmatrix} \begin{pmatrix} 0&1 \\ 1&-2 \end{pmatrix} \left( \begin{array}{c} 1 \\-1 \end{array} \right) \\ = \begin{pmatrix} 0&1 \\ 1&-1 \end{pmatrix} \begin{pmatrix} 0&1 \\ 1&-1 \end{pmatrix} \left( \begin{array}{c} -1\\3 \end{array} \right) \\ = \begin{pmatrix} 0&1 \\ 1&-1 \end{pmatrix} \left( \begin{array}{c} 3\\-4 \end{array} \right) \\ = \left( \begin{array}{c} -4\\7 \end{array} \right)$
ここで $19 \cdot (-4) + 11 \cdot 7 =1$ であるから, $(x,y)=(-4,7)$ は不定方程式 $19x+11y=1$ の解の１つである.

[補足(2021/03/31)] $3=2 \cdot 1+1$ の後、 $2=1 \cdot 2+0$ まで計算しないと気持ち悪い！という場合は $\left( \begin{array}{c} 0 \\ 1 \end{array} \right)$ を $\begin{pmatrix} 0&1 \\ 1&-2 \end{pmatrix} \left( \begin{array}{c} 1 \\ 0 \end{array} \right)$ に置き換えれば良さそうです。