3x+7y\ (x,\ y:整数)\ がすべての整数を表せることを示せ.$
(2)\ \ $3x+7y\ (x,\ y:自然数)\ が表せない最大の整数を求めよ.$
(3)\ \ $3x+7y\ (x,\ y:0以上の整数)\ が表せない最大の整数を求めよ.$ ax+byの形で表せる整数とax+by=N}$の解の構造 \\
本項の内容は,\ 前項で証明した整数論の基本定理の応用である.
$a,\ b$を0でない整数とする.
$整数a,\ bが互いに素}\ ⇔\ ax+by=1を満たす整数x,\ yが存在する$
$整数a,\ bが互いに素}\ ⇔\ すべての整数Nはax+by\ (x,\ y:整数)の形で表せる$
(1)\ \ $3x+7y=1は,\ 整数解(x,\ y)=(-\,2,\ 1)}$をもつ.
よって,\ $3x+7y=N\ (N:整数)}は,\ 整数解(x,\ y)=(-\,2N,\ N)}をもつ.$
∴ 3x+7yはすべての整数を表せる.}
整数Nが3x+7yの形で表せることは,\ 3x+7y=Nの整数解が存在することに等しい.
よって,\ 3x+7y=Nの整数解の1つを実際に示せばよい.}
3,\ 7は互いに素であるから,\ 3x+7y=1の整数解が存在する.
3x+7y=1の整数解の1つをN倍すると,\ 3x+7y=Nの整数解の1つが求まる}のであった.
3x+7y\ (x,\ y:自然数)が表せない最大の整数は\ \ 21}$
x,\ yの範囲が限定されると,\ ax+byの形ですべての整数を表すことができなくなる.
このとき,\ 表せない最大の整数,\ あるいは表せる最小の整数が興味の対象となる.
a0としたほうがよい.
ax+by=cの整数解の組数は,\ 整数kの個数と一致する}のであった.
よって,\ 整数kが存在しないような整数Nの最大値}が求める整数である.
整数kについて解き,\ 整数kの存在条件を考える.}
存在しない条件を直接考えるのは難しいので,\ まず存在する条件を考える.
とりうる値の範囲の幅が1より大きい}とき,\ 必ずその範囲内に整数kが存在する.
等号を含まないから,\のように幅がちょうど1のときは整数kが存在するとは限らない.
N≧22のとき幅が1より大きくなるから,\ 必ずその範囲内に整数kが存在する.
逆に言えば,\ N≦21のときは幅が1以下となり,\ 整数kが確実に存在する保証がなくなる.}
ように幅が1以下でも整数kが存在する可能性はあるので,\ まだ答えは確定しない.
21以下の整数Nについて,\ 整数kが存在するか否かを順に確認していく}ことになる.
本問の場合はN=21の時点で整数kが存在せず,\ N=20,\ 19,\ ･･･\ を調べずとも答えが確定する.
実は,\ ax+by\ (x,\ y:自然数)が表せない最大の整数はab}であることが知られている.
3(x+1})+7(y+1})\ (x,\ y:0以上の整数)は22以上のすべての整数を表せる$
別解は(2)を利用するものである.\ 一般化する場合にはこの考え方が必要になる.
文字の置換}により,\ (2)の条件を(3)の条件に変換する.
以上の結果を一般化したのが以下の定理である.
a,\ bが互いに素な自然数のとき$
\,[1]\ \ $ab+1以上のすべての自然数は,\ ax+by\ (x,\ y:自然数}\,)の形で表せる.$
\,[1]$’$\ \ $ax+by\ (x,\ y:自然数}\,)の形で表せない最大の自然数は\ \ ab$
\,[2]\ \ $(a-1)(b-1)以上のすべての自然数は,$
$ax+by\ (x,\ y:0以上の整数}\,)の形で表せる.$
\,[2]$’$\ \ $ax+by\ (x,\ y:0以上の整数}\,)の形で表せない最大の自然数は\ \ (a-1)(b-1)-1$}
まず,\ [1]の証明を示す.\ 証明の大筋は,\ ax+by=1の整数解の存在証明と同じである
N≧ ab+1を満たす自然数Nに対し,\ b個の自然数N-a,\ N-2a,\ ･･･,\ N-baを考える.
b個の整数のうち,\ 任意の2数をN-ka,\ N-la\ (1≦ k0,\ b>0よりq>0であるから,\ (x,\ y)=(p,\ q)はax+by=Nの自然数解である.
次に,\ [1]’の証明を示す.
ax+by=abとすると\ \ a(x-b)=-\,by x=-\,bk+b>0,\ y=ak>0より\ \ 0ab\ (N≧ ab+1)}のとき,\ 必ず自然数解が存在する}(必ず第1象限の格子点を通る).(n≦=”” ab-1)\=”” のとき,\=”” 自然数解が存在する場合もしない場合もある.
