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