次: 解の発見法 上: 一次不定方程式 前: 差で閉じた部分集合

部屋割り論法

解の存在の証明には別の方法がある．その原理を説明する．

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

(i)

$m$人を$n$部屋に分けて入れる． $m\ge nq+1$なら，$q+1$人以上入る部屋が存在する．

(ii)

$n$人を$n$部屋に相部屋にならないように振り分ける． 各部屋に入るものが存在する．

これを用いて定理7(2)の証明をしよう． これは章末の演習問題14のように，入試問題でもよく出題される． 次の証明は演習問題14の(3)，(4)と同じ内容である．

部屋割り論法による定理7(2)の証明

$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次不定方程式の一般解

演習問題14(2)は次のように一般的に成り立つ．

定理 8        $a$と$b$を互いに素な整数とし，不定方程式$ax+by=1$の1つの整数解を $x_0,\ y_0$ とする． すべての整数解は次のように与えられる．

$$(x,\ y)=(x_0+bt,\ y_0-at),\ \quad (tは任意の整数)$$

証明      任意の整数解$x$と$y$をとる．$ax+by=1$と$ax_0+by_0=1$の辺々を引く．

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

$a$と$b$が互いに素なので，$x-x_0$は$b$の倍数．これを$bt$とおく． このとき $x=x_0+bt,\ y=y_0-at$となる．

逆にある整数$t$を用いてこの形に表される$x$と$y$は不定方程式を満たす． よって定理が示された． (証明終わり)

このよう一般的な形で表された解を一般解という． これは，直線 $ax+by=1$ 上には無数の格子点が等間隔に乗っていること， それらを一般的な形に書くことができることを意味している．