完全剰余系の基本定理}自然数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になりうる}から,\ このとき距離が最小になる.
