1次不定方程式ax+by=cの整数解の存在条件、格子点と直線の最短距離

スポンサーリンク
完全剰余系の基本定理}自然数n\ (≧2)と整数aが互いに素であるとき   1a,\ 2a,\ ・・・・・・,\ naをnで割ったときの余りはすべて異なる.    (1)}\ \ $ka,\ laをnで割ったときの余りが等しいと仮定}する.$    (1)}\ \ $このとき,\ la-ka=a(l-k)がnで割り切れるはずである.$    (1)}\ \ $ところが,\ nとaは互いに素}であり,\ かつ00であることも考慮すると,\ 00のときに整数解をもつことを示せば,\ b<0のときも整数解をもつことはほぼ自明である. 実際,\,3x+2y=1が解(1,\ -\,1)をもつことと3x-2y=1が解(1,\ 1)をもつことは本質的に等しい. b≧2のとき,\ 完全剰余系の基本定理を利用できる. bで割ったときの余りは0\,~\,b-1のb種類であり,\ b個の整数の余りはすべて異なる. よって,\ どれかは不明だが,\ b個の整数の中に余りが1になるものがただ1つ存在する}はずである. この整数をkaとおいて割り算の等式を作成}すると証明できる. \Longleftarrow は互いに素の証明なので,\ 素数の公約数をもつとして矛盾を示す(背理法).} 例えば,\ 9x+6y=1のとき3(3x+2y)=1より,\ 左辺が3の倍数となり矛盾する. 対偶「a,\,bが互いに素でないならばax+by=1の整数解が存在しない」を示すのもほぼ同じである. 次が同値であることも非常に重要である.  ax+by=1を満たす整数x,\ yが存在する\ ⇔\ すべての整数Nはax+byの形で表せる すべての整数Nがax+byの形で表せるとは,\ ax+by=Nの整数解が存在することを意味する. 例えば,\ 13は2x+9yの形で表すことも92x+25yの形で表すこともできる. 2x+9y=13,\ 92x+25y=13の整数解が存在することと同じである. \Longleftarrow は明らか,\ ⇒ も容易に示すことができる. ax+by=c型不定方程式でcの値が大きい場合,\,ax+by=1の整数解を求めてc倍するのであった. ax+by=1が(x,\ y)=(α,\ β)を解にもつとき,\ aα+bβ=1が成り立つ. 両辺をN倍}するとa(Nα)+b(Nβ)=Nより,\ ax+by=Nは(x,\ y)=(Nα,\ Nβ)を解にもつ.    $集合IをI=\{ax+by\ |\ x,\ yは整数\}$で定める.    $m,\ n\in Iとすると,\ m=ax_1+by_1,\ n=ax_2+by_2$とおける.    $m-n}=(ax_1+by_1)-(ax_2+by_2)=a(x_1-x_2)-b(y_1-y_2)\ \in I}$    $kを整数とすると km}=k(ax_1+by_1)=a(kx_1)+b(ky_1)\ \in I}$    $I$に属する最小の自然数を$d$}とすると,\ $d=ax_0+by_0\ (x_0,\ y_0:整数)}$とおける.    任意の$s\in I$に対し,\ $s=dq+r\ $を満たす整数$q,\ r$が存在する.    $dq\in I$より,\ $r=s-dq\in I}$である.    さらに,\ $0≦ $と自然数$d$の最小性}により $r=0}$    よって\ \ $s=dq}$    ここで $a=a・1+b・0\in I,\ \ b=a・0+b・1\in I$    $d$は$a,\ b$の正の公約数であり,\ $a,\ b$は互いに素}であるから,\ $d=1}$である.    $1=ax_0+by_0}$より,\ $ax+by=1を満たす整数x,\ yが存在する.} 実は,\ 集合の観点からの証明がより本質的である. 高校数学では見慣れない考え方で,\ 受験における重要度も低いので上級者向けである. まず,\ 準備としてIの任意の要素m,\ nに対し,\ m-n\in I,\ km\in I}であることを示す. m,\ nがIの要素であるとき,\ その差や整数倍した数もまたIの要素になる}ということである. ここからが本題である.\ 自然数の部分集合には最小要素dが存在する}ことを利用する. Iの任意の要素sをdで割ったときの等式を作成し,\ その余りrに着目する.} dがIの要素なので,\ その整数倍した数であるdqもまたIの要素である. さらに,\ sとdqがIの要素なので,\ その差r=s-dqもまたIの要素である. rの範囲とdが最小の自然数であることを考慮するとr=0が確定し,\ このときs=dqとなる. こうして,\ Iの任意(すべて)の要素sが最小の自然数dの整数倍である}ことが示される. ここで,\ aもbもIの要素であるから,\ aもbもdの整数倍である. 言い換えるとdはa,\ bの公約数}ということであり,\ d=1と定まる. この証明は,\ 整数全体の集合をZとするとき,\ I=Z}を示したことにもなっている. I=Zは,\ すべての整数がax+byの形で表されることを意味する. Iの要素dを整数倍した数もIの要素であるから,\ dZ\subset Iである. 一方,\ Iのすべての要素はdの整数倍であるから,\ I\subset dZである. dZ\subset IかつI\subset dZより,\ I=dZ}となる.\ 特に,\ d=1のとき,\ I=Zである.  整数論の基本定理を一般化した以下も重要である. a,\ bを0でない整数とするとき  cはg(a,\ b)の倍数}\ ⇔\ ax+by=c\ を満たす整数x,\ yが存在する \\ \ \,$a,\ b$の最大公約数を$g$とすると,\ $a=ga',\ b=gb'\ (a',\ b':互いに素な整数)}$とおける. \ \,$c$が$g$の倍数であるとき $ga'x+gb'y=gc$\ より $a'x+b'y=c}$ \ \,$a',\ b'$は互いに素なので,\ $a'x+b'y=1を満たす整数x,\ yが存在する.$} \ \,$a'x+b'y=1が(x,\ y)=(α,\ β)を解にもつとき,\ a'α+b'β=1が成り立つ.$  ∴ cがg(a,\ b)の倍数であるとき,\ ax+by=cを満たす整数x,\ yが存在する.}$} \ \,$a,\ b$の最大公約数を$g$とすると,\ $a=ga',\ b=gb'\ (a',\ b':互いに素な整数)}$とおける.  ∴ ax+by=cを満たす整数x,\ yが存在するとき,\ cはg(a,\ b)の倍数である.}$ g(a,\ b)はa,\ bの最大公約数である.\ \ g(a,\ b)=gとおいて証明する. ⇒ は,\ gを約分すると係数が互いに素である1次不定方程式に帰着する. よって,\ 整数論の基本定理を利用でき,\ さらに両辺をc倍すると証明できる. 点$(x_1,\ y_1)と直線ax+by+c=0の距離の公式\ d=ax_1+by_1+c{√{a^2+b^2$を利用して,\ $xy座標平面における格子点と直線35x+21y=15との距離の最小値を求めよ.$ \\   $xy座標平面上の格子点の座標を(m,\ n)とする.$   $点と直線の距離の公式より    $35m+21n-15=0}のとき7(5m+3n)=15$より,\ これを満たす$m,\ n$は存在しない.   $(m,\ n)=(1,\ -\,1)}\ はこの方程式の解である.$ x座標もy座標も整数であるような点を格子点という. 点と直線の距離の公式(数II})の適用により,\ 分子35m+21n-15}の最小値に帰着する. ここで,\ 35m+21n-15}は0以上の整数である. 整数の最大・最小問題では,\ しらみつぶしする方針が有効}であることが少なくない. つまり,\ 35m+21n-15}が0,\ 1,\ 2,\ ・・・\ になりうるか否かを小さい方から順に調べていけばよい. 35m+21n-15}=0のとき,\ (7の倍数)=15となるから矛盾である. 5,\ 3は互いに素であるから,\ 整数解が存在するはずである. 整数解を1組見つけると分子が1になりうる}から,\ このとき距離が最小になる.