n元1次不定方程式の解の存在条件



$2\ 元 \ 1\ 次不定方程式の解の存在条件は、ユークリッドの互除法をつかう方法で教科書にも書かれていますが、$
$3\ 元以上については、可換環で定義されるイデアルで考えると、意外に分かり易いので、まとめてみました。$


$1 \quad 整数のイデアル$

$\quad 整数全体の集合 \ Z\ の部分集合 \ A\ が$

$\quad $(i)$\ \ x \in A,\quad y \in A \quad ならば \quad x \pm y \in A$

$\quad $(ii)$\ \ x \in A,\quad m \in Z \quad ならば \quad mx \in A$

$\quad を満たすとき、A\ を \ Z\ のイデアルといいます。$

$\quad なお、x \in A \quad ならば \quad x-x =0 \in A ,\quad 0-x=-x \in A$


$\quad 整数 \ a\ の倍数全体の集合を \ (a)\ で表すと$

$\quad $(i)$\ \ x \in (a),\quad y \in (a) \quad ならば \quad x \pm y \in (a)$

$\quad $(ii)$\ \ x \in (a),\quad m \in Z \quad ならば \quad mx \in (a)$

$\quad が成りたつから \ (a)\ は \ Z\ のイデアルです。これを \ a\ で生成された単項イデアルといいます。$

$定理1 \qquad Z\ における任意のイデアル \ A\ は単項イデアルである。$
$\hspace{3em} すなわち、A=(a)\ となる整数 \ a\ が存在する。$

$(証明)$

$\quad A=\{0\} \quad ならば \ \ a=0 \ がある。$

$\quad A \ne \{0\} \quad ならば \ \ A\ には \ 0\ 以外の整数 \ c\ がある。$

$\qquad c \in A \quad ならば \quad -c \in A \quad だから \quad c ,\ \ -c \ \ のうち一方は正である。$

$\quad A\ の元のうち、正の整数全体を \ B\ とすると、B\ は整列集合だから \ B\ には最小数 \ a\ がある(整列原理)。$

$\quad 任意の \ \ x \in A \ \ に対し、除法の原理により \quad x=aq+r \ \ (0 \leqq r < a)\ \ となる整数 \ q,\ r \ \ がただ \ 1\ 通りに$

$\quad 定まるから \qquad r=x-aq $

$\quad r \ne 0 \quad ならば \quad 0 < r < a \quad だから \quad r \in B \ \ で \ a\ が最小数であることに矛盾する。よって \quad r=0$

$\quad すると、x=aq \quad となり、x \in (a) \quad すなわち \quad A \subset (a)$

$\quad また、(a)\ は \ Z\ のイデアルだから \quad (a) \subset A$

$\quad したがって \quad A=(a)$


$2 \quad n\ 個の整数から作られるイデアル$

$\quad a_1,\ a_2,\ \cdots ,\ a_n \ \ を整数として　L=a_1m_1+a_2m_2+ \cdots +a_nm_n\ \ (m_i \in Z) \ の形の整数全体を集合 \ A\ とする。$

$\quad p \in A,\quad q \in A \quad をとると \quad p=a_1k_1+a_2k_2+ \cdot +a_nk_n ,\quad q=a_1l_1+a_2l_2+ \cdot +a_nl_n \quad とおける。$

$\quad このとき$

$\qquad p \pm q =a_1(k_1 \pm l_1)+a_2(k_2 \pm l_2)+ \cdots +a_n(k_n \pm l_n) \in A$

$\qquad j \in Z \quad として \quad jp=a_1(jk_1)+a_2(jk_2)+ \cdot +a_n(jk_n) \in A$

$\quad よって、A\ はイデアルである。これを \ \ a_1,\ a_2,\ \cdots ,\ a_n \ \ で生成されたイデアルといい、(a_1,\ a_2,\ \cdots ,\ a_n )\ と表す。$


$\quad 集合\ A\ の正の要素の集まりのうち、最小の正の整数を \ \ d=a_1u_1+a_2u_2+ \cdots +a_nu_n \ \ とする。$

$\quad 定理 \ 1\ より、Z\ における任意のイデアルは単項イデアルであったから、イデアル \ \ (a_1,\ a_2,\ \cdots ,\ a_n )\ も$

$\quad 単項イデアルです。$

$\quad よって、(a_1,\ a_2,\ \cdots ,\ a_n )=(d) \quad すなわち \quad L=a_1m_1+a_2m_2+ \cdots +a_nm_n \quad は \ d\ の倍数となる。$


$\quad この \ d\ について次の定理が成りたつ。$

$定理2 \qquad (a_1,\ a_2,\ \cdots ,\ a_n )=(d)\quad で定まる整数 \ d\ は　a_1,\ a_2,\ \cdots ,\ a_n \ \ の最大公約数である。$

$(証明)$

(i)
$\qquad 1\cdot a_1 + 0\cdot a_2 + \cdots + 0\cdot a_n=a_1$
$\qquad 0\cdot a_1 + 1\cdot a_2 + \cdots + 0\cdot a_n=a_2$
$\hspace{3em} \vdots$
$\qquad 0\cdot a_1 + 0\cdot a_2 + \cdots + 1\cdot a_n=a_n$

$\quad だから、a_1,\ a_2,\cdots ,\ a_n \quad はすべて \ d\ の倍数である。$

$\quad すなわち、d\ は、a_1,\ a_2,\ \cdots ,\ a_n \ \ の公約数となるから \quad d \leqq (a_1,\ a_2,\ \cdots ,\ a_n )$

$\quad なお、ここで、記号\ \ (a_1,\ a_2,\ \cdots ,\ a_n )\ \ は \ \ a_1,\ a_2,\ \cdots ,\ a_n の最大公約数を表すが、イデアルも同じ記号が$

$\quad 用いられます。$


(ii)
$\quad d=a_1u_1+a_2u_2+ \cdots +a_nu_n \ \ は \ L\ の形の数だから、a_1,\ a_2,\ \cdots ,\ a_n の公約数(最大公約数を含む)$

$\quad の倍数だから \qquad d \geqq (a_1,\ a_2,\ \cdots ,\ a_n )$

$\quad $(i),(ii)$より \qquad d=(a_1,\ a_2,\ \cdots ,\ a_n )$


$(別証) \qquad d\ が最大公約数であることの、高校生にもわかるような、イデアルをつかわない証明です。$

$\quad d\ が、a_1,\ a_2,\ \cdots ,\ a_n \ \ の公約数ならば \quad a_1=db_1,\ a_2=db_2,\ \cdots , \ a_n=db_n \ \ (b_1,\ b_2,\ \cdots,\ b_n は整数)\ とおける。$

$\quad b_1,\ b_2,\ \cdots,\ b_n \ \ が互いに素であれば、d\ は最大公約数となる。$

$\quad もし、d\ が最大公約数でないならば$

$\qquad b_1,\ b_2,\ \cdots,\ b_n \ \ は \ 2\ 以上の公約数 \ p\ をもつから \quad b_1=pc_1,b_2=pc_2,\cdots , bn=pc_n \quad とおける。$

$\qquad このとき、a_1=dpc_1,\ a_2=dpc_2,\ \cdots,\ a_n=dpc_n$

$\quad d \ は \ L\ の形の数(正の最小数)だから \quad d=a_1u_1+a_2u_2+ \cdots +a_nu_n \ \ とおける。$

$\qquad d=dpc_1u_1+dpc_2u_2+ \cdots +dpc_nu_n \qquad 両辺を \ d\ (>0)\ で割って$

$\qquad 1=pc_1u_1+pc_2u_2+ \cdots +pc_nu_n $

$\qquad 1=p(c_1u_1+c_2u_2+ \cdots +c_nu_n) $

$\quad p \geqq 2 \ \ で、c_1u_1+c_2u_2+ \cdots +c_nu_n \ \ は整数だから、これは矛盾である。$

$\quad したがって、p=1 \ \ となり、d\ は最大公約数となる。$


$ここが一番わかりづらいところなので、具体例で説明します。$

$\quad イデアル \quad L=12x+18y \ \ (x,\ y\ は整数)\ \ について$

$\quad L=6(2x+3y)\ \ は \ \ x=-1,\ y=1\ \ (x=2,\ y=-1\ \ でもよい)\ のとき \ L=6 \ が最小の正の整数となるから$

$\quad d=6 \quad したがって、L\ の形の数は、すべて \ 6\ の倍数である。$

$\quad なお、12\ と \ 18\ の公約数は \ \ 2,\ 3,\ 6\ であるが、2\ と \ 3\ は \ L\ の形の数ではない。$

$\quad つまり、L\ の形の最小の正の整数 \ 6\ が、12\ と \ 18\ の最大公約数となっている。$


$3 \quad 1\ 次不定方程式 \quad a_1x_1+a_2x_2+ \cdots + a_nx_n=b \quad に整数解が存在する条件$

$定理3 \qquad 1\ 次不定方程式 \quad a_1x_1+a_2x_2+ \cdots + a_nx_n=b \quad に整数解が存在するための条件は$
$\hspace{3em} (a_1,\ a_2,\ \cdots ,\ a_n) |b \quad である。$

$(証明)$

$(1)\ \ 必要条件$

$\quad 整数解 \ \ x_1^*,\ x_2^*,\ \cdots ,\ x_n^* \ \ が存在すれば \quad b=a_1x_1^* + a_2x_2^* + \cdots + a_nx_n^*$

$\quad 右辺は \ \ a_1,\ a_2,\ \cdots ,\ a_n\ \ で生成されるイデアルだから単項イデアル \ (d)\ に等しくなる \ d\ がある。$

$\quad 各係数は \ d\ の倍数だから \ b\ は \ d\ の倍数となり、d|b \ \ すなわち \ \ (a_1,\ a_2,\ \cdots ,\ a_n) |b \ \ である。$

$(2)\ \ 十分条件$

$\quad d|b \ \ ならば \ \ b\ は \ d の倍数だから \quad b \in (d)=(a_1,\ a_2,\ \cdots ,\ a_n)$

$\quad したがって、b=a_1u_1+a_2u_2+ \cdots + a_nu_n \quad をみたす整数 \ \ u_1,\ u_2,\ \cdots ,\ u_n \ が存在する。$


$4 \quad 1\ 次不定方程式 \quad a_1x_1 + a_2x_2 + \cdots + a_nx_n=b \ \ の解法$

$\qquad a_1x_1+a_2x_2+ \cdots + a_nx_n=b \hspace{15em}①$

$\quad に整数解が存在するとき、(a_1,a_2,\cdots ,a_n)=d\ \ について \ \ d|b \ \ だから \quad a_k=a'_{k}d \ \ (k=1,\ 2,\ \cdots ,\ n),$

$\quad b=b'd \quad とおける。これらを①に代入して \ d\ で割ると$

$\qquad a_1'x_1+a'_2x_2+ \cdots + a_n'x_n=b' \qquad (a'_1,\ a'_2 ,\ \cdots ,\ a'_n )=1$

$\quad そこで、あらためて \quad a_1x_1+a_2x_2+ \cdots + a_nx_n=b \qquad (a_1,\ a_2 ,\ \cdots ,\ a_n )=1 \quad を考えれば十分である。$

$(1)\ \ n=2 \ \ のとき$

$\qquad ax+by=c \quad ただし \ \ (a,\ b)=1 $

$\quad 1\ 組の解を \ \ x_0,\ y_0 \ \ とすると \quad ax_0+by_0=c$

$\quad 辺々引いて \quad a(x-x_0)+b(y-y_0)=0$

$\quad a(x-x_0)=-b(y-y_0)$

$\quad (a,\ b)=1 \quad だから \quad a|y-y_0 \quad よって \quad y-y_0=at \ \ (t\ は任意の整数)とおける。$

$\quad a(x-x_0)=-abt \qquad x-x_0=-bt$

$\quad 逆に、このとき$

$\quad a(x_0-bt)+b(y_0+at)=ax_0+by_0=c \quad だから \quad x=x_0-bt , \quad y=y_0+at \quad は解である。$


$(2)\ \ n > 2 \ \ のとき$

$\quad a_1x_1+a_2x_2+ \cdots + a_nx_n=b \qquad (a_1,\ a_2 ,\ \cdots ,\ a_n )=1 \hspace{10em}①$

$\quad (a_2,\ a_3 ,\ \cdots ,\ a_n )=c_1 \quad とおくと \quad a_k=c_1a'_k \ \ (k=2,\ 3,\ \cdots ,\ n)$

$\quad a_2x_2+a_3x_3+ \cdots + a_nx_n=c_1u_1 \quad とおけるから$

$\quad a'_2x_2+a'_3x_3+ \cdots + a'_nx_n=u_1 \qquad (a'_2,\ a'_3 ,\ \cdots ,\ a'_n )=1 \hspace{10em}②$

$\quad ①は \quad a_1x_1+c_1u_1=b \qquad (a_1,c_1)=1$

$\quad これを解いて、x_1,\ \ u_1\ \ を求め、②に代入すれば未知数を \ 1\ つ減らすことができる。$


$例題$

$\quad 10x+6y-9z=1 \ \hspace{30em}(1)$

$\quad (6,\ 9)=3 \quad だから \quad 6y-9z=3u \quad とおくと \quad 2y-3z=u \ \hspace{12em}(2)$

$\quad (1)は \quad 10x+3u=1 \qquad (10,\ 3)=1 \hspace{23em}(3)$

$\quad これをみたす解の \ 1\ つは \quad x=1,\ \ u=-3 \quad だから \quad x=1-3t,\quad u=-3+10t$

$\quad (2)で \ u=1\ \ とおいた解の \ 1\ つは \ \ y=2,\ \ z=1 \quad だから \quad 2 \times 2 -3 \times 1=1 $

$\quad 両辺に \ u\ をかけて \quad 2 \times 2u-3 \times u=u \ \hspace{21em}(4)$

$\quad (2)-(4) \ \ より \quad 2(y-2u)-3(z-u)=0 \qquad \therefore \ \ y-2u=3s,\quad z-u=2s$

$\quad よって$

$\qquad y=2u+3s=2(-3+10t)+3s=-6+20t+3s$

$\qquad z=u+2s=-3+10t+2s$

$\quad したがって \quad x=1-3t, \quad y=-6+20t+3s,\quad z=-3+10t+2s \quad (t,\ s\ \ は任意の整数)$



ページの先頭へ↑




メインメニュー　に戻る