次: 素数 上: 一次不定方程式 前: 一次不定方程式の解の存在

一次不定方程式の一般解と解の構成

一次不定方程式

$$a_1x_1+a_2x_2+\cdots +a_nx_n =k$$

の一般解と解を構成するアルゴリズムの存在について考える．

まず「一般解」を正確に定義しておこう．二変数の場合についてのべる． $x$ と $y$ との不定方程式 $f(x,y)=0$ がある． 関数 $p(x),\ q(x)$ が存在し，この不定方程式の任意の解を

$$x=p(t), \, y=q(t)$$

と表す整数$t$が存在し， 逆に任意の整数$t$に対して $x=p(t), \, y=q(t)$がこの不定方程式の整数解となるとき， $x=p(t), \, y=q(t)$ を不定方程式 $f(x,y)=0$ の一般解 という．

変数が多い場合も同様に定義される． ただし二変数の場合は任意整数を表す変数の個数は1個であったが， 一般には変数 $x,\ y,\ \cdots$の個数から1減じた個数の任意整数が必要である．

例 1.4.1  

$$32x+57y+68z=1$$

の一般解を求める． $(32,\ 57,\ 68)$ の最大公約数を求めるときと同様に， いちばん小さい32で他の二数を割る．

$$\begin{eqnarray*} 57&=&32 \times 1+25\\ 68&=&32 \times 2+4 \end{eqnarray*}$$

これを係数に代入し同様の操作を繰り返す．

$$\begin{eqnarray*} 32x+57y+68z&=&32x+(32 \times 1+25)y+(32 \times 2+4)z\\ &=... ...z)+(4\times 6+1)y+4z\\ &=&4\{8(x+y+2z)+6y+z\}+y+0(x+y+2z)\\ \end{eqnarray*}$$

ここで

$$l=8(x+y+2z)+6y+z=8x+14y+17z,\ m=y ,\ n=x+y+2z$$ (1.4)

とおく．

$$4l+m+0n=1$$

の一般解を求める．これは例えば．

$$l=t,\ m=1-4t ,\ n=s\quad t,\ s\ \in Z$$

がとれる．これより(1.4)は

$$\begin{eqnarray*} 8x+14y+17z&=&t\\ y&=&1-4t\\ x+y+2z&=&s \end{eqnarray*}$$

となる．これから一般解は

$$x=11-46t+17s,\ y=1-4t,\ z=-6+25t-8s\quad t,\ s\ \ は任意整数$$

となる．

今は，適宜（てきぎ）式を整理したのでわかりにくいが， この方法をまねて一般解を構成するアルゴリズムを定式化することができる．

上の例からわかることは， 除法をおこなうことで少ない変数の場合に帰着させ， 二変数の一般解を用いて一般解を構成できるのではないか，ということである． そのためにまず二変数の場合について，確認しなければならない．

二変数の場合の個別解を構成するアルゴリズム

まず一組の解を見いださなければならない．$3x+2y=1$ なら暗算でできる． しかし$127x+52y=1$となると，一組見つけるのも暗算というわけにはいかない． ところが，ユークリッドの互除法を用いて一組の解を構成する一般的な方法がある．

$a$ と $b$ の最大公約数が1より大きいとき， $k$ が，$a$と$b$ の最大公約数の倍数でなければ解はない． $k$ が最大公約数の倍数なら全体をその最大公約数で割って， 初めから $a$ と $b$ の最大公約数は１，つまり $a$ と $b$ は互いに素であるとしてよい． このとき $ax+by=1$ に解が見つかれば $x$ と $y$ の各々に $k$ を乗じることにより， $ax+by=k$ の解ができる． 結局 $a$ と $b$ が互いに素なときに $ax+by=1$ の解が構成できれば よいことがわかる．

1. $a>b$ とし， $a=bq+r,(0 \le r <b)$ とする．
2. $ax+by=(bq+r)x+by=rx+b(qx+y)$ であるから， $y'=qx+y$とおくと方程式$ax+by=1$ は方程式$rx+by'=1$ となる．
3. $rx+by'=1$ の解 $(x_0,y'_0)$ が構成できれば， $y_0=y'_0-qx_0$によって定めた$(x_0,y_0)$が$ax+by=1$の解となる．

これは解の存在証明の第一の方法と同じ内容であることに注意しよう． $a$ と $b$ が互いに素なら $b$ と $r$ も互いに素であるから，こうして係数のより小さい方程式が得られ，しかもその解からもとの方程式の解が構成できる．この過程を繰り返すと，最後は係数の一方は $1$ となる．

$sx+y=1$ または $x+ty=1$ の解として $(0,1)$ か $(1,0)$ をとれる． ここから逆に戻っていけば $ax+by=1$ の解が得られる．

この方法で $127x+52y=1$ の解を構成しよう． まず互除法で方程式を変換する．

1. $127x+52y=1$
2. $127=52 \cdot 2+23 \, , \, y'=2x+y \, , \, 23x+52y'=1$
3. $52=23 \cdot 2+6 \, , \, x'=x+2y' \, , \, 23x'+6y'=1$
4. $23=6 \cdot 3+5 \, , \, y''=3x'+y' \, , \, 5x'+6y''=1$
5. $6=5 \cdot 1+1 \, , \, x''=x'+y'' \, , \, 5x''+y''=1$

ここから逆に解を構成していく．

1. $(x'',y'')=(0,1)$
2. $x''=x'+y''$ より $(x',y'')=(-1,1)$
3. $y''=3x'+y'$ より $(x',y')=(-1,4)$
4. $x'=x+2y'$ より $(x,y')=(-9,4)$
5. $y'=2x+y$ より $(x,y)=(-9,22)$

確かに, $127 \cdot (-9) + 52 \cdot 22=-1143+1144=1$ である． これは二変数の不定方程式の解を構成する一般的な方法である．

二次行列による解の構成

この過程を具体的に記述するのは二次行列を使うのが適切である． 二次行列の演算と行列式についてまとめておこう．

行列 $\matrix{a}{b}{c}{d}$ とベクトル $\vecarray{x}{y}$ に対し， $\matrix{a}{b}{c}{d} \vecarray{x}{y} = \vecarray{ax+by}{cx+dy}$ と定める．

$A,B$ を二つの行列とし， $\overrightarrow{X}=\vecarray{x}{y}$ とする． このとき計算によって確認できるように，

$$A(B \overrightarrow{X})=(AB) \overrightarrow{X}$$

が成り立つ． また，行列 $\matrix{s}{t}{u}{v}$ に対して, $\left\vert A\right\vert=sv-tu$ とおくと,

$$\begin{eqnarray*} \left\vert\matrix{s}{t}{u}{v}\matrix{x}{y}{z}{w}\right\vert ... ...t \begin{array}{cc} x&y\\ z&w \end{array} \right\vert \end{eqnarray*}$$

が成り立つ． $\left\vert A\right\vert$のことを行列 $A$ の「行列式」という．

以上を前提に，二変数一次不定方程式の一般解の構成を含めて定理にまとめる．

定理 6

(1)

$a,b \in Z, \ a>b>0$ とする．$a$を$b$ で割った商を$q_0$ ，余りを $r_1$ とするとき， 次式が成り立つ．

$$\vecarray{a}{b}=\matrix{q_0}{1}{1}{0} \vecarray{b}{r_1}$$

(2)

同様の操作を繰り返すことにより，除法の列

$$a = q_0b+r_1 ,\ b = q_1r_1+r_2 ,\ \cdots , r_{k-1} = r_kq_k+r_{k+1}$$

に対して，

$$\vecarray{a}{b} =\matrix{q_0}{1}{1}{0}\matrix{q_1}{1}{1}{0}\cdots \matrix{q_k}{1}{1}{0} \vecarray{r_k}{r_{k+1}}$$

が得られる．ここで

$$\matrix{P_k}{X_k}{Q_k}{Y_k} =\matrix{q_0}{1}{1}{0} \matrix{q_1}{1}{1}{0} \cdots \matrix{q_k}{1}{1}{0}$$

と置く．このとき次式が成り立つ．

$$X_k=P_{k-1}, \ Y_k=Q_{k-1} , \ P_k Q_{k-1} - P_{k-1} Q_k=(-1)^{k+1}$$

(3)

$a$ と $b$ の最大公約数を $d$ とするとき，

$$\vecarray{a}{b}=\matrix{P_n}{P_{n-1}}{Q_n}{Q_{n-1}}\vecarray{d}{0}$$

となる番号 $n$ が存在する．

(4)

このとき， $x=(-1)^{n-1}Q_{n-1}, \ y=(-1)^n P_{n-1}$ が不定方程式 $ax+by=d$ の一組の解となる．

(5)

$ax+by=1$ の１組の解があるとし，それを $x_0 \, , \, y_0$ とする． このとき $ax+by=1$ の一般解は，

$$(x,\ y)=(x_0-bt ,\ y_0+at) ,\ t \in \mathbb{Z}$$

である．■

証明
(1)     $a=bq_0+r_1$ である. よって,

$$\vecarray{a}{b}=\vecarray{bq_0+r_1}{b}=\matrix{q_0}{1}{1}{0}\vecarray{b}{r_1}$$

(2)    

$$\begin{eqnarray*} \matrix{P_k}{X_k}{Q_k}{Y_k} &=& \matrix{P_{k-1}}{X_{k-1}}{Q_... ...atrix{P_{k-1}q_k+X_{k-1}}{P_{k-1}}{Q_{k-1}q_k+Y_{k-1}}{Q_{k-1}} \end{eqnarray*}$$

よって,

$$X_k=P_{k-1},\quad Y_k=Q_{k-1}$$

である．

$$\begin{eqnarray*} P_kQ_{k-1}-P_{k-1}Q_k &=& \left\vert \begin{array}{cc} ... ... q_k&1\\ 1&0 \end{array} \right\vert\\ &=& (-1)^{k+1} \end{eqnarray*}$$

(3)     $a$ を $b$ で割った除法の式を

$$a=bq_0+r_1$$

とする. この式の形より, $a$ と $b$ の公約数は $r_1$ を割り, $b$ と $r_1$ の公約数は $a$ を割るので, $a$ と $b$ の最大公約数と $b$ と $r_1$ の最大公約数は等しい(ユークリッドの互除法の原理)．

次に, 除法の原理より,

$$b>r_1\geq 0$$

である. 同様に

$$\vecarray{a}{b},\ \vecarray{b}{r_1},\ \vecarray{r_1}{r_2},\cdots$$

はそれぞれの組の最大公約数がつねに等しく, かつ

$$b>r_1>r_2\cdots$$

と減少してゆく列である．ゆえに, ある番号 $n$ が存在して,

$$r_n\ne 0,\quad r_{n+1}= 0$$

となる. このとき, $a$ と $b$ の最大公約数が $r_n$ と $0$ の最大公約数 ( 0は0でない任意の整数を約数にもつものとする)となるので, $r_n$ そのものが$a$と $b$ の最大公約数 $d$ である. つまり, この $n$ に対して,

$$\begin{eqnarray*} \vecarray{a}{b} &=& \matrix{q_0}{1}{1}{0}\matrix{q_1}{1}{1}{... ...}{0}\\ &=& \matrix{P_n}{P_{n-1}}{Q_n}{Q_{n-1}}\vecarray{d}{0} \end{eqnarray*}$$

となる.
(4)

$$\vecarray{a}{b}=\matrix{P_n}{P_{n-1}}{Q_n}{Q_{n-1}}\vecarray{1}{0}$$

の両辺に $\matrix{P_n}{P_{n-1}}{Q_n}{Q_{n-1}}$ の逆行列を左からかけると,

$$\matrix{P_n}{P_{n-1}}{Q_n}{Q_{n-1}}^{-1}=(-1)^{n+1}\matrix{Q_{n-1}}{-P_{n-1}}{-Q_n}{P_n}$$

であるから,

$$(-1)^{n+1}\matrix{Q_{n-1}}{-P_{n-1}}{-Q_n}{P_n}\vecarray{a}{b}=\vecarray{1}{0}$$

つまり,

$$a\{(-1)^{n+1}Q_{n-1}\}+b\{(-1)^nP_{n-1}\}=1$$

よって, $x=(-1)^{n-1}Q_{n-1}, \ y=(-1)^n P_{n-1}$ は $ax+by=1$ の解である.
(5)     $(x_0,y_0)$ を $ax+by=1$ の任意の解の組とすると,

$$\left\{ \begin{array}{rcl} ax+by&=& 1 \\ ax_0+by_0 &=& 1 \end{array} \right.$$

これより,

$$a(x-x_0)+b(y-y_0)=0$$

となり, $a$ と $b$ は互いに素であるから, $x-x_0$ は $b$ の倍数である. よって, $x-x_0=-bt\ (t\ は整数)$ とおくと, $y-y_0=+at$ となる. つまり, このときある $t$ に対し,

$$x=x_0-bt,\quad y=y_0+at$$

となる. 逆に, 任意の整数 $t$ に対し, $x=x_0-bt,\ y=y_0+at$ とおくと,

$$ax+by=a(x_0-bt)+b(y_0+at)=ax_0+by_0=1$$

となるので, $(x,\ y)$ は $ax+by=1$ の解である. □

例 1.4.2        $127x+52y=1$ の一般解を以上の方法で求めよう．

$$\begin{eqnarray*} \vecarray{127}{52} &=& \matrix{2}{1}{1}{0}\vecarray{52}{23} ... ...1}{0} \matrix{1}{1}{1}{0}\matrix{5}{1}{1}{0} \vecarray{1}{0} \end{eqnarray*}$$

そして,

$$\begin{eqnarray*} &&\matrix{2}{1}{1}{0}\matrix{2}{1}{1}{0} \matrix{3}{1}{1}{0}... ...atrix{5}{2}{2}{1}\matrix{23}{4}{6}{1} = \matrix{127}{22}{52}{9} \end{eqnarray*}$$

なので,

$$x=-9, \ y=22$$

が1組の解である. 実際,

$$127\cdot (-9)+52\cdot 22=-1143+1144=1$$

よって, 一般解は任意の整数 $t$ に対し, 次式で与えられる.

$$\left\{ \begin{array}{rcl} x&=&-9-52t \\ y&=&22+127t \end{array} \right.$$

$n$ 変数の場合に一般解を構成するアルゴリズム

このように二変数の場合について構成法が確立した． これをもとに一般の $n$ 変数の場合に，帰納的に解を構成していくことができる．

(1)

二変数の場合，ユークリッドの互除法によって個別解が求まり， それを用いて一般解を作ることができる．

(2)

$n-1$ 変数のとき一般解を構成することができるとする．

(3)

$a_1,\ a_2,\ \cdots ,\ a_n$で $a_1$ が絶対値最小とする．

$$a_k=q_ka_1+r_k,\ (k=2,\ 3,\ \cdots,\ n)$$

とする．はじめの方程式は

$$\begin{eqnarray*} a_1x_1+a_2x_2+\cdots +a_nx_n &=&a_1x_1+(q_2a_1+r_2)x_2+\cd... ... \\ &=&a_1(x_1+q_2x_2+\cdots+q_nx_n)+r_2x_2+\cdots+r_nx_n=k \end{eqnarray*}$$

となる．ここで $X_1=x_1+q_2x_2+\cdots+q_nx_n,\ X_k=x_k\ (k=2,\ \cdots,\ n)$ とおく．

$$a_1X_1+r_2X_2+\cdots+r_nX_n=k$$ (1.5)

ここで(1.5)の解 $X_1=\alpha_1,\ X_2=\alpha_2,\ \cdots,\ X_n=\alpha_n$ が構成できたとする． このとき

$$\begin{eqnarray*} k&=&a_1\alpha_1+r_2\alpha_2+\cdots+r_n\alpha_n\\ &=&a_1\a... ...\alpha_2-\cdots-q_n\alpha_n)+a_2\alpha_2 +\cdots+a_n\alpha_n \end{eqnarray*}$$

であるから

$$x_1=\alpha_1-q_2\alpha_2-\cdots-q_n\alpha_n,\ x_k=\alpha_k\ (k=2,\ \cdots,\ n)$$

は

$$a_1x_1+a_2x_2+\cdots +a_nx_n =k$$

の解である．

よって(1.5)の解が構成できればよい． ところが，方程式(1.5)を作った操作を繰り返すと， ついにはいずれかの係数が0になる． その0のものを除いた $n-1$ 変数の不定方程式は一般解が構成できる． 係数 0 の未知数を新たな任意整数におく． こうして得られた一般解から上の手順でもとの方程式の解を構成していけば， 必ずもとの不定方程式の解が構成される．□

一般的な構成アルゴリズムの存在は，解の存在証明の別解になっていることに注意しよう．

次: 素数 上: 一次不定方程式 前: 一次不定方程式の解の存在