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