ax+byで表せる整数とax+by=Nの解の構造

スポンサーリンク

本項目は発展的な内容です。

3x+7y\ (x,\ y:整数)\ がすべての整数を表せることを示せ.$ $3x+7y\ (x,\ y:自然数)\ が表せない最大の整数を求めよ.$ $3x+7y\ (x,\ y:0以上の整数)\ が表せない最大の整数を求めよ.$ {3x+7y=N\ を満たす整数解の1つを実際に示せばよい.} 3,\ 7は互いに素であるから,\ 整数論の基本定理より,\ 必ず整数解が存在する. 3x+7y=1\ の特殊解を求め,\ 両辺をN倍すると考える. 文字で一般化されているから,\ これですべての整数について示したことになる. 例えば,\ 100\ を表したければ,\ (x,\ y)=(-200,\ 100)\ とすればよいことがわかる. 実際,\ 3(-200)+7(100)=100\ となる. 整数kが常に存在する条件は 3x+7yが表せない最大の整数は\ 「整数を表せる」を{「3x+7y=N\ の自然数解(x,\ y)が存在する」}と考える. よって,\ 自然数解が存在しないようなNの値の最大値が求める整数である. まず,\ このax+by=c型の不定方程式の整数解を普通に求める. ここでは,\ と同じ特殊解を用いて求めた. 後はx,\ yが自然数になりうるNを考えればよいが,\ 流れがわかりにくい. となるような整数kが存在すればよいわけである. Nの場合も同様に,\ {kについての範囲に変形し,\ 整数kの存在条件を考える.} 整数kが必ず存在するためには,\ {とりうる値の範囲の差が1より大きければよい.} N₂2\ のとき,\ 差が1より大きくなるから,\ 必ずその間に整数kが存在する. 逆に言えば,\ {N₂1\ のとき,\ 整数kが存在するとは言い切れない.} 存在しないとも言い切れないので,\ 1つずつ確認しなければならない. つまり,\ N=21,\ 20,という順番で,\ kが存在するかを確認していく. N=21\ とすると,\ 整数kが存在しないから,\ 自然数解x,\ yも存在しない. 求めるのは自然数解が存在しない最大の数なので,\ N=21が答えとして確定する. 常に自然数3x+7yが表せない最大の整数は\ を利用するのが簡潔である.\ ややこしくなるので,\ 文字を変更する. で,\ 「3X+7Y\ (X,\ Y:自然数)\ は22以上のすべての整数を表せる」を得た. これを元に,\ 「3x+7y\ (x,\ y:0以上の整数)」が表せる整数を考えるのである. X,\ Y\ (自然数)\ をx,\ y\ (0以上の整数)\ で表して代入する. 「3X+7Y\ は22以上のすべての整数を表せる」 \「3(x+1)+7(y+1)\ は22以上のすべての整数を表せる」 \「3x+7y+10\ は22以上のすべての整数を表せる」 \「3x+7y\ は12以上のすべての整数を表せる」 後は,\ 11,\ 10,という順番でkが存在するかを確認していけばよい. ax+by=Nの整数解は,\ 図形的には{直線上の格子点である.$ 整数論の基本定理より,\ a,\ bが互いに素のとき,\ 必ず整数解が存在する. これは,\ 直線\ ax+by=N\ が必ず格子点を通ることを意味する. 傾きを考慮すると,\ この{直線上の格子点は,\ (b,\ -a)ごとに等間隔に並ぶ.} 特別に着目すべきなのは,\ {N=ab\ のとき}である. y=- abx+a\ より,\ {ちょうど(b,\ 0),\ (0,\ a)を通る.} よって,\ {N=ab\ のときは自然数解が存在しない}(第1象限の格子点を通らない). {Nab}\ (N ab+1)のとき,\ {必ず自然数解が存在する}(第1象限の格子点通過). Nab\ (N ab-1)\ のとき,\ 第1象限の格子点を通る場合も通らない場合もある. 以上から,\ のような定理が成立することがわかる. a,\ bが互いに素のとき$    ${ab+1以上の全ての自然数Nは,$              ${ax+by\ (x,\ y:自然数})で表せる.$    ${(a-1)(b-1)以上の全ての自然数Nは,$              ${ax+by\ (x,\ y:0以上の整数})で表せる. この定理は知識として持っておくとよい. は,\ {「ax+by\ (x,\ y:自然数)\ で表せない最大の自然数はab」}も重要である. は,\ から導かれる.\ のx,\ yをX,\ Yに変えて導く. 「ab+1以上の全ての自然数Nは,\ aX+bY\ (X,\ Y:自然数)で表せる」 ここで,\ のx,\ y\ (0以上の整数)\ と,\ X,\ Yの関係は X=x+1,Y=y+1 「ab+1以上の自然数Nは,\ a(x+1)+b(y+1)\ (x,\ y:0以上の整数)で表せる」 「ab+1以上の自然数Nは,\ ax+by+a+b\ (x,\ y:0以上の整数)で表せる」 「ab+1-a-b以上の自然数Nは,\ ax+by\ (x,\ y:0以上の整数)で表せる」 ここで,\ ab+1-a-b=a(b-1)-(b-1)=(a-1)(b-1)\ より,\ となる.
スポンサーリンク
スポンサーリンク
高校数学A 整数
受験の月をフォローする
受験の月
タイトルとURLをコピーしました