読者です 読者をやめる 読者になる 読者になる

ニ☆ウ☆ト☆ラ☆ボ

タイトルテスト中

整数係数連立一次方程式の整数解

雑記

例えば,

\[ \left\{ \begin{array}{rcrcrcrcl} 5x & + & 8y & + & 8z & - & 5w & = & 1 \\ 2x & + & 5y & + & z & - & 7w & = & -5 \\ x & + & y & + & 5z & + & 4w & = & 8 \end{array} \right. \]

の整数解を求めてみます.

1. こんな行列を作ります:

\[ \left( \begin{array}{cccc|c} 5 & 8 & 8 & -5 & 1 \\ 2 & 5 & 1 & -7 & -5 \\ 1 & 1 & 5 & 4 & 8 \\ \hline 1 & 0 & 0 & 0 & \\ 0 & 1 & 0 & 0 & \\ 0 & 0 & 1 & 0 & \\ 0 & 0 & 0 & 1 & \end{array} \right) \]

左上の行列に「行および列の基本変形」を行い, 対角成分以外を 0 にすることが目標です(必ずできます). 行の基本変形とは,

  1. ある行を -1 倍する.
  2. ある行とある行を入れ換える.
  3. ある行にある行を整数倍したものを加える.
という操作のことです. 列の基本変形も同様です.

2. 基本的な方針は, (1,1) 成分の絶対値がどんどん小さくなるように変形することです. ただし, 0 にしてはいけません. そのような変形は実際に可能です.

\[ \left( \begin{array}{cccc} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & & & \\ a_{31} & & & \end{array} \right) \]

例えば, \( a_{14} \) が \( a_{11} \) の倍数でないならば,

\[ a_{14} = a_{11} \times q + r, \quad 0 < r < | a_{11} | \] となりますが, そうすると, 列の基本変形(1列目の -q 倍を4列目に足す)により \[ \left( \begin{array}{cccc} a_{11} & a_{12} & a_{13} & r \\ a_{21} & & & \\ a_{31} & & & \end{array} \right) \] とでき, さらに, 列の入れ換えにより \[ \left( \begin{array}{cccc} r & a_{12} & a_{13} & a_{11} \\ * & & & \\ * & & & \end{array} \right) \]

とできるからです.

3. このようなことを繰り返すうちに, 1行目と1列目の数はすべて (1,1) 成分の倍数となります. この状態からさらに行および列の基本変形を行うと,

\[ \left( \begin{array}{cccc} * & 0 & 0 & 0 \\ 0 & & & \\ 0 & & & \end{array} \right) \]

という形にもっていけます.

4. あとは, 次から次へと内側の行列に同じ手順を行っていくと, 対角成分以外が 0 になります.

5. 実際, やってみます.

\( \left( \begin{array}{cccc|c} 5 & 8 & 8 & -5 & 1 \\ 2 & 5 & 1 & -7 & -5 \\ 1 & 1 & 5 & 4 & 8 \\ \hline 1 & 0 & 0 & 0 & \\ 0 & 1 & 0 & 0 & \\ 0 & 0 & 1 & 0 & \\ 0 & 0 & 0 & 1 & \end{array} \right) \)
\( \downarrow \)
\( \left( \begin{array}{cccc|c} 1 & 1 & 5 & 4 & 8 \\ 2 & 5 & 1 & -7 & -5 \\ 5 & 8 & 8 & -5 & 1 \\ \hline 1 & 0 & 0 & 0 & \\ 0 & 1 & 0 & 0 & \\ 0 & 0 & 1 & 0 & \\ 0 & 0 & 0 & 1 & \end{array} \right) \)
\( \downarrow \)
\( \left( \begin{array}{cccc|c} 1 & 0 & 0 & 0 & 8 \\ 2 & 3 & -9 & -15 & -5 \\ 5 & 3 & -17 & -25 & 1 \\ \hline 1 & -1 & -5 & -4 & \\ 0 & 1 & 0 & 0 & \\ 0 & 0 & 1 & 0 & \\ 0 & 0 & 0 & 1 & \end{array} \right) \)
\( \downarrow \)
\( \left( \begin{array}{cccc|c} 1 & 0 & 0 & 0 & 8 \\ 0 & 3 & -9 & -15 & -21 \\ 0 & 3 & -17 & -25 & -39 \\ \hline 1 & -1 & -5 & -4 & \\ 0 & 1 & 0 & 0 & \\ 0 & 0 & 1 & 0 & \\ 0 & 0 & 0 & 1 & \end{array} \right) \)
\( \downarrow \)
\( \left( \begin{array}{cccc|c} 1 & 0 & 0 & 0 & 8 \\ 0 & 3 & 0 & 0 & -21 \\ 0 & 3 & -8 & -10 & -39 \\ \hline 1 & -1 & -8 & -9 & \\ 0 & 1 & 3 & 5 & \\ 0 & 0 & 1 & 0 & \\ 0 & 0 & 0 & 1 & \end{array} \right) \)
\( \downarrow \)
\( \left( \begin{array}{cccc|c} 1 & 0 & 0 & 0 & 8 \\ 0 & 3 & 0 & 0 & -21 \\ 0 & 0 & -8 & -10 & -18 \\ \hline 1 & -1 & -8 & -9 & \\ 0 & 1 & 3 & 5 & \\ 0 & 0 & 1 & 0 & \\ 0 & 0 & 0 & 1 & \end{array} \right) \)
\( \downarrow \)
\( \left( \begin{array}{cccc|c} 1 & 0 & 0 & 0 & 8 \\ 0 & 3 & 0 & 0 & -21 \\ 0 & 0 & 8 & 10 & 18 \\ \hline 1 & -1 & -8 & -9 & \\ 0 & 1 & 3 & 5 & \\ 0 & 0 & 1 & 0 & \\ 0 & 0 & 0 & 1 & \end{array} \right) \)
\( \downarrow \)
\( \left( \begin{array}{cccc|c} 1 & 0 & 0 & 0 & 8 \\ 0 & 3 & 0 & 0 & -21 \\ 0 & 0 & 8 & 2 & 18 \\ \hline 1 & -1 & -8 & -1 & \\ 0 & 1 & 3 & 2 & \\ 0 & 0 & 1 & -1 & \\ 0 & 0 & 0 & 1 & \end{array} \right) \)
\( \downarrow \)
\( \left( \begin{array}{cccc|c} 1 & 0 & 0 & 0 & 8 \\ 0 & 3 & 0 & 0 & -21 \\ 0 & 0 & 2 & 8 & 18 \\ \hline 1 & -1 & -1 & -8 & \\ 0 & 1 & 2 & 3 & \\ 0 & 0 & -1 & 1 & \\ 0 & 0 & 1 & 0 & \end{array} \right) \)
\( \downarrow \)
\( \left( \begin{array}{cccc|c} 1 & 0 & 0 & 0 & 8 \\ 0 & 3 & 0 & 0 & -21 \\ 0 & 0 & 2 & 0 & 18 \\ \hline 1 & -1 & -1 & -4 & \\ 0 & 1 & 2 & -5 & \\ 0 & 0 & -1 & 5 & \\ 0 & 0 & 1 & -4 & \end{array} \right) \)

望む形になりました.

6. 方程式

\[ \left\{ \begin{array}{rcrcrcrcl} x' & & & & & = & 8 \\ & & 3y'& & & = & -21 \\ & & & & 2z' & = & 18 \end{array} \right. \]

を解いて(もちろん整数解を求める),

\[ \begin{pmatrix} x \\ y \\ z \\ w \end{pmatrix} = \begin{pmatrix} 1 & -1 & -1 & -4 \\ 0 & 1 & 2 & -5 \\ 0 & 0 & -1 & 5 \\ 0 & 0 & 1 & -4 \end{pmatrix} \begin{pmatrix} x' \\ y' \\ z' \\ w' \end{pmatrix} \]

を計算すると, もとの方程式の整数解が得られます. 整数解 (x',y',z',w') がないようならば, もとの方程式にも整数解はありません.

7. 実際やってみると, (x', y', z', w') = (8, -7, 9, t) (t は整数を動くパラメータ)なので,

\[ \begin{pmatrix} x \\ y \\ z \\ w \end{pmatrix} = \begin{pmatrix} 1 & -1 & -1 & -4 \\ 0 & 1 & 2 & -5 \\ 0 & 0 & -1 & 5 \\ 0 & 0 & 1 & -4 \end{pmatrix} \begin{pmatrix} 8 \\ -7 \\ 9 \\ t \end{pmatrix} = \begin{pmatrix} 6-4t \\ 11-5t \\ -9+5t \\ 9-4t \end{pmatrix} , \quad t \in \mathbb{Z} \]

がもとの方程式の整数解となります. おわり.

広告を非表示にする