2.2.19

$$x,y \in \mathbb{N}$$として$$7x+11y=n$$で表せない最大の自然数$$n$$を求める。 $$u=7x+11y$$として$$x,y$$について$$u$$の値を百マス計算のように計算すると以下のようになる。

青字の部分で60から66までの数字が作れる。 後は適当に7を何回か足せば67以上の数字も全て作ることができる。 なぜなら作りたい数を$$u \geq 67$$としたとき$$u \equiv A\, \pmod{7}$$なる$$60 \leq A \leq 66$$ が必ず存在するので、適当な$$k$$に対して$$u = A + 7k$$が成り立つ。$$A$$は上の表から$$A=7m+11n$$の形での 表し方が分かっているので$$u=7(m+k)+11n$$で表せる。

一方59は上の表には存在しないので答えは59である。

次に一般的な解を考える。つまり正の整数$$a,b$$を固定し、自然数$$x,y$$について $$u(x,y) = ax+by$$と定める。このとき$$n=u(x,y)$$と表せない最大の自然数$$n$$を求める。

まずべズーの等式(あるいは拡張ユークリッドの互除法)から$$a,b$$の最大公約数が1でないときは存在しない(表せない数が無限に存在するため最大値はない)。 また$$a,b$$の少なくともどちらかが1であっても存在しない($$n = 1\times n$$より表せない数字がない)。

そこで$$2 \leq a < b$$かつこれらの最大公約数は1(つまり互いに素)であるとする。 先の具体例から$$a$$で割った余りを基準として考えると良さそうである。 そこで$$u(0,0), u(0,1), \ldots, u(0,a-1)$$を$$a$$で割った余りをそれぞれ$$r_0, r_1, \ldots, r_{a-1}$$とする。 $$a,b$$が互いに素であることからこれらは相異なる(互いに素#性質)(背理法を用いて示せる)。

まず$$u(0,a-1) = (a-1)b \leq n$$となる$$n$$はすべて表すことができる。なぜならある$$0 \leq i < a$$について $$r_i = n \bmod a$$となるものが存在する。いま$$u(0,i) \leq u(0,a-1) \leq n$$であるから適当な自然数$$k$$ を用いて$$n = u(0,i) + ak = u(k, i)$$で表せるからである。

次に$$L = u(0,a-1) - a + 1 \leq n < u(0,a-1)$$となる$$n$$も表せる。 $$u(0,a-1) - a \equiv r_{a-1}$$であるから、$$n$$を$$a$$で割った余りはそれぞれ $$r_{a-1}+1,\ldots,a-1,0,\ldots,r_{a-1}-1$$となる。つまり$$r_{a-1} \neq n \bmod a$$である。 これと$$u(0,a-2) \leq L$$から、$$0 \leq i \leq a-2$$かつ$$r_i = n \bmod a$$となる$$i$$が存在する。 よって適当な自然数$$k$$を用いて$$n = u(0,i) + ak = u(k, i)$$で表せる。

最後に$$n = L-1 =ab - a - b$$は表すことができない。 もし表せたとすると適当な自然数$$p,q$$が存在して$$ap+bq=n$$を満たす。両辺を$$a$$で割った余りを考えると $$bq \equiv n \bmod a \equiv r_{a-1}$$である。このようになる$$q$$は$$r_0,r_1,\ldots,r_{a-1}$$が 相異なる$$a$$未満の数であることから少なくとも$$a-1$$以上でなければならない。 しかし$$p$$は自然数であるから$$n = ap + bq \geq bq \geq b(a-1) = ab -b$$となり矛盾。

以上より$$2\leq a < b$$かつ$$a,b$$が互いに素なとき$$n=ab-a-b$$、 それ以外のときは存在しない。