引き続きシルヴァーマン『はじめての数論』の演習問題をやっていきます．
今回取り組んでいくのは，演習問題 6.6 です．
問題と回答
問a
(a) 方程式 $3x + 5y = 4$ は $x \geq 0$ かつ $y \geq 0$ である解を持たない理由を説明せよ．
「理由を説明せよ」とありますが，証明すればいいだけですね．
しらみつぶしに $x,y$ の可能性を調べればいいです．調べるべき候補は高々数個しかないので，これはやればできます．
問b
(b) $x \geq 0$ かつ $y \geq 0$ である $3x+5y$ の形をしたいくつかの数からなるリストを作成せよ．そしてそれが不可能である値に関する予想を立てよ．それからその予想が正しいことを証明せよ．
この問題，どこかで見たことあるので大学入試くらいのレベルの問題だと思います．
まず $3x + 5y \; (x≧0,y≧0)$ の形の数のリスト作成ですが，これは実際にやってみればいいですね．
数が順序良く表に現れるわけではないので少し見づらいですが，表に現れない最大の数は７である……ように見えます．現時点では証明できてないので「たぶん７」としか言えませんが，８以上の数はどうやら $3x + 5y \; (x≧0,y≧0)$ の形に必ず表せるようです．
つまりは，次の予想を得るわけです．
これを証明していきましょう．
この命題はしらみつぶしに調べても証明にならないので，ちゃんと考える必要があります．
証明 まず線形代数の類推から，$3x + 5y$ というのが線形写像に見えるということが気になります．つまりは，解集合 $V$ はおそらく１次元の空間で，１つのパラメータで記述できるだろうと予想されます．
実際には $V$ は線形空間ではないのでちゃんと考える必要がありますけど．
そこで $f : \mathbb{Z}^ 2 \to \mathbb{Z}$ を $f(x,y) = 3x + 5y$ によって定義します．集合 $\ker f$ をパラメトライズにより表示しましょう．
$3x + 5y = 0$ という式を解くことができます．これを実行すると $x = 5t, y=-3t$ というように，$t \in \mathbb{Z}$ をパラメータとして表示されることがわかります．これが $\ker f$ です．
それでは整数 $n ≧ 0$ が与えられたとして $f^ {-1}(n)$ を考えていきましょう．これも線形代数の類推でできますね．
$3$ と $5$ は互いに素なので，$2 \times 3 + (-1) \times 5 = 1$ というように生成するイデアルに１が含まれます．これに $n$ を乗じて
$$ 2n \times 3 + (-n) \times 5 = n $$
です．この式と $3x + 5y = n$ で辺々引いて
$$ (x-2n) \times 3 + (y+n) \times 5 = 0 $$
つまり $(x-2n, y+n) \in \ker f$ です．
先ほど $\ker f$ のパラメータ表示を決定しましたので，これによって $f^ {-1}(n)$ のパラメータ表示もわかります．つまり
$$ x = 5t + 2n \ y = -3t - n $$
です．
あとは，不等式に整数解があるかどうかを求める問題に持っていきます．
「$n= 3x + 5y \; (x≧0,y≧0)$ と表すことができる」という命題のことを $P(n)$ と書くことにします．これは，ある $(x,y) \in f^ {-1}(n)$ であって，$x ≧ 0$ かつ $y ≧ 0$ なるものがあることと同値です．
したがって，不等式
$$ \frac{-2n}{5} \leq t \leq \frac{-n}{3} $$
に整数解があることと，$P(n)$ は同値です．したがって，$n \geq 15$ のときには区間の端から端までの長さが１以上になるため確実に $P(n)$ が成り立つことがわかります．
後は，$1 \leq n \leq 15$ についてしらみつぶしに調べればよいです．□
なんとか証明ができました．
線形結合の形をしているので，線形代数の類推が使えるのがいいですね．
