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

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