おはようございます．
引っ越しで忙しいので最近数学の記事が書けていません．
本末転倒なので，今後は多少更新頻度を下げる予定です．
よろしくお願い致します．
今回は前回の記事の続きで，
シルヴァーマン『はじめての数論』の演習問題6.6をやっていきます．
問c
問題文
$(a,b)$ の以下の各値について，$x≧0$ かつ $y≧0$ であって $ax+by$ の形にはならない最大の数を求めよ．
(i) $(a,b)=(3,7)$
(ii) $(a,b)=(5,7)$
(iii) $(a,b)=(4,11)$
回答
各 $n$ について，$n = ax+by$ ($x≧0$, $y≧0$) と表せるかどうかを調べてリストを作っていきます．
計算機にやらせようかと思いましたが，まだ新PCに必要なソフトを入れられていないので，手計算でやります．
(i) 11
(ii) 23
(iii) 29
前回の記事で，少なくとも $ab$ 以上の数 $n$ は $n = ax+by$ ($x≧0$, $y≧0$) と表せることを示しましたが，実際には $ab$ よりもかなり小さいところに上限があるようです．
問d
問題文
$\gcd(a,b) = 1$ とせよ．(c) における結果を用いて，$x≧0$ かつ $y≧0$ であって $ax+by$ の形にはならない最大の数を，$a$ と $b$ で表した式を予想して与えよ．その予想を少なくとも２つ以上の $(a,b)$ についてチェックせよ．
回答
$ax+by$ ($x≧0$，$y≧0$) の形にはならない数の集合を $Neg(a,b)$ と表すことにします．(Negative からとっています)
$Neg(a,b)$ が有限集合であることは前回の記事で示しました．そこでその最大の元を $M$ と表すことにします．
問c についての結果から，次の予想が立てられます．
この予想をチェックせよという問題ですが，ここでは省略します．
問e
問題文
(d) において予想した式が正しいことを証明せよ．
回答
正直に言って，この問題は難しかったです．
前回の記事では $M \leq ab -1$ を示しましたが，このときはある区間に整数が含まれるかどうかという議論をしました．そのときの議論を，分母の大きさまで考慮に入れて精緻化すればできそうなんですが，それだといまいちわかりづらかったので別の方法で示すことにしました．
まず $ab-a-b$ が $Neg(a,b)$ の元であることを示しましょう．
(証明) 仮に $ab - a- b = ax + by$ ($x≧0$, $y≧0$) と表せたとしよう．すると $ab = a(x+1) + b(y+1)$ だから $b(y+1)$ は $a$ の倍数であり，$a(x+1)$ は $b$ の倍数である．
仮定から $a,b$ は互いに素なので，$y+1$ は $a$ の倍数であり，$x+1$ は $b$ の倍数である．したがって $x,y \geq 0$ により $y+1 \geq a$, $x+1 \geq b$ であることがわかる．
ゆえに $ab \geq a^ 2 + b^ 2$ であるが，この不等式から $a=b=0$ が導かれてしまうので矛盾．□
これで $ab - a- b \leq M$ が判ったことになります．あとは逆の不等式を示しましょう．……と考えていたのですが，よく考えたら命題１を示す必要はありませんでした．
次の命題２で一気にカタがつきます．
(証明) 同じことなので $M + a$ が $b$ の倍数ということだけ示す．
$M$ は定義から $Neg(a.b)$ の最大の元なので，$M + a$ は $Neg(a,b)$ の元ではない．したがって，ある $x \geq 0$ と $y \geq 0$ が存在して $M + a = ax + by$ と書くことができる．
これはつまり $M = a(x-1) + by$ ということである．$M \in Neg(a,b)$ なので係数 $x-1$ は負の数でなければならず，したがって $x=0$ である．よって $M+a$ は $b$ の倍数．□
命題2 によって，$a$ と $b$ が互いに素なので中国式剰余定理が使えます．$M$ を $ab$ で割った余りは $-a-b$ でなければならないことがわかります．$0 \leq M \leq ab-1$ は前回の記事ですでに示していましたので，これで $M = ab -a- b$ が示せたことになります．
「ある程度長い区間には整数が含まれる」ということを使った議論よりも，こちらの方がシンプルで見やすいと思います．
感想とまとめ
大変おもしろい問題でした．最初に具体例を計算した時点では，そもそも $Neg(a,b)$ が有限集合だということ自体私には見えていなかったので驚きました．
命題２があれば命題１は不要と書きましたが，命題２の証明を読んだ感じでは $ab - a - b \in Neg(a,b)$ と言ってるようには見えないので，もしかしたら必要なのかも？とちょっと悩ましく思っています．
たとえ必要だとしても上記のように簡単に示せるので，問題ないんですけどね．
