初等整数論講義/第1章/一次の不定方程式

§3. 一次の不定方程式

1. 本節で論ずるのは

$ax + by + cz = k$

のような二つ以上の未知数を含む一つの一次方程式が与えられて，しかも係数 $a, b, c, k$ が整数であるとき，その方程式のすべての整数解を求めるという問題である．

後に説明するように，この方程式が整数解を有するならば，無数の整数解がある．この意味において古来それを不定方程式と呼んでいたのであるが，代数的方程式論における不定と区別するために，近時は整係数の方程式の整数解を求めることを Diophantus の問題，したがってその方程式を Diophantus の方程式ともいう．

Diophantus は西暦約 350 年の頃アレキサンドリアに生存していたとされている．方程式，特に一次方程式の解法は Diophantus の著書に初めて載せられたものであるが，その時代を考えて想像されるように，主として有理数特に整数を取り扱ったものである．

定理 1.7．

一次の不定方程式

$ax + by + cz = k$

が解を有するがために必要かつ十分な条件は $k$ が $d = (a, b, c)$ で割り切れることである （変数の数は任意）．

［注意］

変数 $x, y, z$ に任意の整数値を与えるときに，一次形式 $ax + by + cz$ がとるところの値を，この一次形式によって表わされる数という．この用語によれば，上の定理を次のようにいい表わすことができる．

一次形式

$f(x, y, z) = ax + by + cz$

によって表わされる数は $d = (a, b, c)$ の倍数の全体である．

［証］

$0$ はもちろん一次形式 $f$ によって表わされる数である（例えば $x = y = z = 0$ または $x = b, y = -a, z = 0$ などとするとき， $f = 0$ ）．また $k$ が $f$ によって表わされるならば， $-k$ も $f$ によって表わされることはもちろんである（変数の符号を変えればよい）．

さて $f$ によって表わされる整数の中の最小の正なるものを $k_0$ として

(2)

$ax_0 + by_0 + cz_0 = k_0$

と置く．また $f$ によって表わされる任意の整数を $k$ として

(3)

$ax + by + cz = k$

と置く．

しからば $k$ は $k_0$ の倍数である．なぜならば，もしも $k$ が $k_0$ の倍数でなくて

$k = qk_0 + r, \qquad 0 < r < k_0$

ならば，(2)，(3) によって

$r = k - qk_0 = a(x - qx_0) + b(y - qy_0) + c(z - qz_0)$

であるから， $k_0$ よりも小さい正の整数 $r$ が $f$ によって表わされることになる．これは矛盾である．故に $k$ は $k_0$ で割り切れる．

しかるに $a = a \cdot 1 + b \cdot 0 + c \cdot 0$ は $f$ によって表わされる数であるから， $a$ は $k_0$ で割り切れる．同様に $b, c$ も $k_0$ で割り切れる．すなわち $k_0$ は $a, b, c$ の公約数であるが， $k_0$ は(2)によって $d = (a, b, c)$ の倍数（定理 1.1）であるから， $k_0 = d$ ．故に $d$ は一次式 $f$ によって表わされる．

$d = ax_0 + by_0 + cz_0$ ．

すでに $d$ が $f$ によって表わされるならば， $d$ の任意の倍数は $f$ によって表わされる数である．また逆に $f$ によって表わされる数はもちろん $d$ の倍数である（定理 1.1）から，定理は証明されたのである．

［注意］

上記の証明では定理 1.2のみを根拠にして§2の定理を一つも用いなかった．よってこの証明の中で定理 1.4が再び証明されている．すなわち $k_0$ が $a, b, c$ の公約数であることが示され，同時にまた(2)によって $k_0$ が $a, b, c$ の任意の公約数の倍数であることがわかるから， $k_0$ は最大公約数である．

定理 1.6も上記の定理から導かれる． $(a, b) = 1$ ならば， $ax + by = 1$ なる整数 $x, y$ があるから， $acx + bcy = c$ ．故に $ac$ が $b$ で割り切れるならば，左辺の二つの項が $b$ で割り切れるから， $c$ が $b$ で割り切れる．すなわち定理 1.6である．

2. 方程式（1）の一般の解は次のようにして求められる．

［例］

(4)

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

最小の係数 $32$ で他の係数を割れば，

$57 = 32 \times 2 - 7$ ，

$68 = 32 \times 2 + 4$ ，

よって

(5)

$x' = x + 2y - 2z$

と置けば，

( $4^*$ )

$32x' - 7y - 4z = 1$ ．

同様に，

$32 = 4 \times 8$ ，

$7 = 4 \times 2 - 1$ ，

よって

(6)

$z' = 8x' - 2y - z$

と置けば，（ $4^*$ ）から

( $4^{**}$ )

$y + 4z' = 1$ ．

（ $4^{**}$ ）の一般解として

$y = 1 - 4z'$

（ $x'$ ， $z'$ は任意の整数）

を得る．それを（6）に代入して

$z = 8x' + 7z' - 2$ ，

最後に（5）に代入して

$x = 17x' + 22z' - 6$ ，

故に（4）の一般解は

$\begin{cases} x = 17x' + 22z' - 6 \\ y = -4z' + 1 \\ z = 8x' + 7z' - 2 \end{cases}$

$x'$ ， $z'$ に任意の整数値を与えて，この式から（4）のすべての解を得るのである（補遺1参照）．

命題 1．

$ay - bx = k$ の一つの解を $x_0, y_0$ とすれば，一般の解は

$\begin{cases} x = x_0 + a't, \\ y = y_0 + b't. \end{cases}$

ただし $(a, b) = d, a = a'd, b = b'd$ で， $t$ は任意の整数である．

［証］

$ay - bx = k, ay_0 - bx_0 = k$ から，引いて

$a(y - y_0) = b(x - x_0),$

$\therefore a'(y - y_0) = b'(x - x_0).$

$(a', b') = 1$ であるから， $x - x_0$ は $a'$ で割り切れなければならない(定理 1.6)．いま $x - x_0 = a't$ と置けば $y - y_0 = b't$ ．すなわち上掲の通り， $x = x_0 + a't, y = y_0 = b't$ で，これが与えられた方程式を満足させることは明白である．

命題 2．

整数の集合があって，その集合に属する整数から加法と減法とによって作られる整数がやはりその集合に属するとする．このような集合はそれに属する最小絶対値( $\neq 0$ )の整数の倍数の全部から成り立つ．

ただし 0 なる数ただ一つだけから成り立つ集合は除く．

［証］

上記の集合(略して $M$ という)に含まれる 0 以外の整数の仲で最小絶対値を有するものを $k$ とする．しからば仮定によって $M$ は $k - k = 0$ を含み，したがって $0 - k = -k$ を含む．故に $k + k, k + k + k, \cdots , - k - k, \cdots$ すなわち $k$ のすべての倍数を含む．さて $a$ を $M$ に属する任意の整数として， $a = qk + k', - \le k' < |k|$ とすれば(定理 1.2)， $a$ も $qk$ も $M$ に属するから $a - qk = k'$ も $M$ に属する．故に $k$ に関する規約によって $k' = 0$ ．すなわち $a$ は $k$ の倍数である．