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

一次不定方程式の解の存在

定理 4
$a$と$b$は互いに素な整数である．このとき， 一次不定方程式$ax+by=k$には整数解が存在する. ■

$a>b\ge 0$のとき解をもつことが示せれば，例えば$a<0$なら $(-a)(-x)+by=k$を考えればこの場合も整数解があることがわかる． よって$a$と$b$は$a>b\ge 0$である互いに素な整数とする．

この定理には三通りの証明法がある．それを実行し比較検討しよう．

$b$についての数学的帰納法による証明

$b=0$ のとき, $(a,\,b)=1$ より $a=1$．ゆえに方程式は $1\cdot x+0\cdot y=k$ となるから，解 $(k,\,0)$ をもつ.

$0\le j<b$の$j$と$c>j$で$j$と互いに素な任意の$c$に対して$cx+jy=k$が解をもつとする. このとき $ax+by=k\ (a>b\ge 0)$が解をもつことを示す．

$$a=bq+r\ \ (0\leq r<b)$$

とする．このとき，

$$ax+by=(bq+r)x+by=b(qx+y)+rx$$

$a$と $b$ が互いに素なので $b$ と $r$ も互いに素である． ゆえに，仮定より $bX+rY=k$ は解 $(X_0,\,Y_0)$ をもつ．この解に対して $\left\{\begin{array}{l} qx_0+y_0=X_0\\ x_0=Y_0\end{array}\right.$ を解くと $\left\{\begin{array}{l} x_0=Y_0\\ y_0=X_0-qY_0 \end{array}\right.$ となる．

この $x_0,\ y_0$は $ax+by=k\ (a>b\ge 0)$の解となっている．実際

$$\begin{eqnarray*} ax_0+by_0 &=& aY_0+bX_0-bqY_0\\ &=& bX_0+rY_0=k \end{eqnarray*}$$

つまり，$b$ のときも成立する．

よって, 数学的帰納法により, すべての$b\ (b\ge 0)$ と, $a>b$ なる $a$ に対し $ax+by=k$ は解をもつ. □

鳩の巣原理

有限個のもののなかに， ある条件を満たすものが存在することを示す根拠としてよく用いられるのが 鳩の巣原理とか部屋割り論法とかいわれる次の原理である． 同等な二つの形が用いられる．

(i)

$m$人を$n$部屋に分ける． $m>n$なら，2人以上入る部屋が存在する．

(ii)

$n$人を$n$部屋に分ける． 相部屋になる者がないなら，すべての部屋に入る．

「鳩の巣原理」を用いる方法

$i=0,\,\cdots,\,b-1$ に対して $ai$ を $b$ で割った余りを $r_i$ とする. 各 $r_i$ は0から $b-1$ のどれかの値をとる． $0\le i,\ j \le b-1$に対して$r_i$ と $r_j$ が $r_i=r_j$ とする.

$$\begin{eqnarray*} && ai=bq_i+r_i\\ && aj=bq_j+r_j \end{eqnarray*}$$

より

$$a(i-j)=b(q_i-q_j)$$

$a$ と $b$ が互いに素なので $i-j$ が $b$ の倍数である.

$$0-(b-1)\le i-j \le b-1-0$$

より，この範囲の$b$の倍数は，$i-j=0$ 以外にない. 対偶をとると,

$$i\neq j\quad \Longrightarrow\quad r_i\neq r_j$$

$0\le i \le b-1$の$b$個の$i$に対して， 同じ範囲の値$r_i$が対応し，これらのうちに同じ値がない． 鳩の巣原理によって $r_i\ (0\le i \le b-1)$は0から$b-1$の各値を一つずつとる．

$k$を$b$で割って商が$q$，余りが$s$とする． $r_i=s$となる$i$が存在する． つまり

$$ai=bq_i+s$$

となる$i$と$q_i$が存在する．$s=k-bq$なので

$$ai+b(q-q_i)=k$$

つまり $(x,\,y)=(i,\,q-q_i)$ が $ax+by=k$ の解である. □

注意 1.4.1        これは解の作り方も教えている．例えば $37x+13y=1$ の一組の解を見つけるためには次のようにすればよい．

$u=1,\ 2,\ \dots,\ 12$ に対して $37u$ を$13$で割った余りを書いていく．

$$11,\ 9,\ 7,\ \cdots$$

かならず1が出てくる．実際

$$37\times6=13\times 17+1\quad \Rightarrow \quad 37(6)+13(-17)=1$$

ゆえに $(x,\ y)=(6,\ -17)$ が解である．

自然数の部分集合に最小要素が存在することを用いる証明

整数からなる集合$A$を

$$A=\{\ ax+by\ \vert\ x,\ y\in \mathbb{Z}\}$$

で定める．$A$ の要素で正のものからなる集合は自然数の部分集合なので, そのなかに最小のものが存在する．それを$d$とし，

$$d=ax_0+by_0$$

とする． $A$の任意の要素$ax+by$を$d\ (\ >0)$ で割る.

$$ax+by=dq+r \ (0\le r<d)$$

である．これから

$$r=ax+by-dq=a(x-qx_0)+b(y-qy_0)$$

なので，$r$も$A$の要素である． $r>0$なら$d$が$A$の要素のなかで正で最小のものであることに矛盾する． よって$r=0$である．

$A$の任意の要素は$d$の倍数であることが示された． 逆に$d$の倍数 $nd=a(nx_0)+b(ny_0)$は$A$の要素である．

次に $a=a\cdot1+b\cdot 0$なので$a\in A$，同じく $b \in A$も成立する． よって$a$と$b$は$d$の倍数，つまり $d$ は $a$ と $b$ の公約数である． ところが$(a,\,b)=1$なので，$d=1$である．

ゆえに$A$は整数の集合と一致する．したがって任意の整数$k$に対して 方程式$ax+by=k$ には解が存在する. □

この三つの証明のなかで，未知数が3個以上ある場合に拡張しうるのはどれか．

数学的帰納法は$b=0$ のとき未知数がひとつ減るだけでしかない． したがって未知数に関する帰納法と $b$ に関する数学的帰納法を組み合わせなければならない． 不可能ではないが，もっと簡明にできないか． 第二の証明も未知数の個数に関する数学的帰納法が必要になる． 第三の証明はどうだろうか．これは明らかに一般の場合にそのまま拡張される．

一般の場合の証明

ここでは第三の場合の証明のなかで用いられた方法を取りだして補題とし， それを用いて一般の場合を証明しよう．

補題 1
整数からなる集合 $A$ は次の性質を持つ．

$$a,\ b \in A \Rightarrow a-b \in A$$

このとき $A$ は$A$に属する正で最小の要素の倍数全体からなる集合である． ■

証明     条件から$0=a-a \in A$である． また$-a=0-a$から $a\in A$ なら $-a \in A$ である．したがって$a,\ b\in A$に対して

$$a+b=a-(-b)　\in A$$

である．

$A$ の任意の要素 $a$ と整数 $n$ に対して $na \in A$ であることを数学的帰納法で示す．$n=1$ なら明らか． $(n-1)a \in A$ と仮定すれば

$$na=(n-1)a+a \in A$$

である．よって示された．

さて，集合 $A$ に含まれる正で最小の要素を $d$ とする． $A$ の任意の要素 $x$ を $d$ で割ったとき商が $q$，余りが $r$ であるとする．

$$x=dq+r,\ 0\le r <d$$

すると上に示したことから $dq \in A$ である．よって

$$r=x-dq \in A$$

ここでもし $r \ne 0$ なら $d$ より小さい正数 $r$ が $A$ に属することになり $d$ の最小性に反する．

$$∴\quad r=0$$

つまり$x=dq$となり，$A$ の任意の要素は $d$ の倍数であることが示された．$d$の倍数が$A$に属することはすでに示されている．□

定理 5 (一次不定方程式の解の存在定理)
     整数 $a_1,a_2,\ \cdots ,\ a_n,\ k$ を係数とする一次不定方程式

$$a_1x_1+a_2x_2+\cdots +a_nx_n =k$$ (1.2)

が解をもつための必要十分条件は， 整数 $k$ が整数 $a_1，\ a_2，\ \cdots ,\ a_n$ の最大公約数 $d=(a_1，\ a_2,\ \cdots ,\ a_n)$ で割り切れることである．■

証明      集合

$$J=\{a_1x_1+a_2x_2+\cdots +a_nx_n \, \vert \, x_1,\ x_2 , \cdots ,\ x_n は整数 \,\}$$

を考える． $J$の任意の2つの要素の差が再び$J$に属することは明らかである． したがって$J$は$J$ に含まれる正で最小の整数 $e$の倍数全体からなる集合である．

$e$は$J$の要素なので

$$e=\sum_{k=1}^na_kl_k$$ (1.3)

となる $l_k\ (k=1,\ 2,\ 3,\ \cdots ,\ n)$ がある． したがって$d\vert e$である．

一方 $a_1=a_1\cdot1+a_2\cdot0+\cdots+a_n\cdot0$などから$a_i\in J$が各$i$について成り立つ． それらが$e$の倍数なので，$e$は $a_1，\ a_2,\ \cdots ,\ a_n$の公約数である． つまり$e\vert d$である．

$$∴\quad e=d$$

$J$が$d$の倍数全体の集合であることが確定したので， 方程式(1.2)が解をもつことと，$k$が$d$の倍数であることの同値性が示された． □ 次: 一次不定方程式の一般解と解の構成 上: 一次不定方程式 前: 不定方程式