検索用コード
完全剰余系の基本定理整数a,\ nが互いに素 1a,\ 2a,\ \cdots\cdots,\ naをnで割った余りは全て異なる.}}   \ \ $1a,\ 2a,\ \cdots,\ naの任意の2数を\\ とする.$ \\[.2zh]   \ \ $\textcolor{red}{ka,\ laをnで割ったときの余りが等しいと仮定}する.$ \\[.2zh]   \ \ $このとき,\ 差la-ka=a(l-k)がnで割り切れるはずである.$ \\[.2zh]   \ \ $ところが,\あり,\ \textcolor{red}{a,\ nは互いに素}である.$ \\[.2zh]   \ \ $よって,\ a(l-k)はnで割り切れない.$ \\[.2zh]   \ \ $これは\textcolor{red}{矛盾}である.$ \\[.5zh] \centerline{$\therefore \bm{余りは全て異なる. ax+by=1\ の整数解の存在を証明するための準備としてこの定理をまず証明する. \\ これはこれで重要な定理なので,\ 証明とともに知識として持っておくとよい. \\[1zh] 定理の意味がわかりにくいので,\ 具体例として,\ a=3,\ n=5\ の場合を示す. \\ 5で割ったときの余りは0~4の5種類があり得る. \\ 5個の整数の余りに,\ 5種類の余りが重複することなく1回ずつ現れるのである. \\ \bm{「a~naのn個の整数の余りにはn種類すべて現れる」}が定理の主張である. \\[1zh] 証明は\bm{背理法}を用いる.\ \bm{余りが等しいと仮定して矛盾を示す.} \\ このとき,\ 次の同値関係を利用する. \\ \bm{「a,\ bをnで割ったときの余りが一致」\ \Longleftrightarrow\ 「a-bがnで割り切れる」} \\[1zh] 実際には,\ 任意の2数を文字で設定して差をとる.\ 2数の大小関係も設定しておく. \\ 後は,\ a(l-k)がnで割り切れないことを示せばよい. \\ \bm{a,\ nは互いに素}という条件があるから,\ aがnで割り切れることはない. \\ また,\ lが最大のn,\ kが最小の1のとき,\ \bm{l-kが最大n-1}になる. \\ つまり,\ l-kがn以上になることはない. \\ \bm{nよりも小さいl-kがnで割り切れるはずはない}ので,\ 矛盾が示される. 整数論の基本定理}} \bm{\textcolor{cyan}{整数a,\ bが互いに素}}であるとき \\[.2zh] \bm{\textcolor{red}{  ax+by=1\ を満たす整数x,\ yが存在する.}}   \ \ $b個の整数1a,\ 2a,\ \cdots,\ baをbで割ったときの余りはすべて異なる.$ \\[.2zh]   \ \ $よって,\ \textcolor{red}{bで割ると1余る数が1つ存在}し,\ それを\textcolor{cyan}{xa}とする.$ \\[.2zh]   \ \ $商を\textcolor{cyan}{-y}とすると,\ \textcolor{red}{xa=b(-y)+1}\ が成立する.$ \\[.5zh] \centerline{$\therefore \bm{ax+by=1を満たす整数x,\ yが存在する.}$} \\\\\\   \ \ 上の定理は,\ 次の定理と同値である. 整数a,\ bが互いに素}}であるとき \\[.2zh] \bm{\textcolor{red}{任意の整数Nが,\ N=aX+bY\ (X,\ Y:整数)\ で表される.}} 証明の方法とともに知識として持っておくべき整数論の最重要定理である. \\ a,\ bが互いに素であれば,\ 必ず整数解(x,\ y)が存在するという主張である. \\ a,\ bは互いに素ならば何でもよい. \rei\ \ 3x+17y=1,\ 29x+85y=1 \\ 完全剰余系の基本定理を元に簡潔に導かれる(簡単ではない). \\[1zh] 1aからbaまでの\bm{b個の整数をbで割ったときの余り}を考える. \\ bで割ったときの余りは,\ 0~b-1のb種類があり得る. \\ 完全剰余系の基本定理より,\ b個の整数の余りはすべて異なる. \\ よって,\ どれかはわからないが\bm{1余るものが1つある}はずである. \\ これをxaとおき,\ \bm{bで割ったときの商(整数)を-y}として除法の等式を作る. \\ 整理するとax+by=1が得られる.\ この形を目指して-yとおいたわけである. \\ このようにして,\ \bm{xや-yの値はわからないが,\ その存在が示される.} \\[1zh] 1余る数の存在を示した論法を\bm{部屋割り論法(鳩ノ巣原理)}という. \\ 「少なくとも1つ存在する」という\bm{存在証明}の論法で,\ 同等な2つの表現がある. \\ 「n室の部屋にn+1人を入れると,\ 2人以上入る部屋が少なくとも1室ある」 \\ 「n人がn個の部屋に入るとき,\ 相部屋がなければ,\ 各部屋に1人ずつ人が入る」 \\ \bm{どれかを特定できなくても,\ その性質を満たすものが存在する事は証明できる.} \\[1zh] なお,\ \bm{a,\ bが互いに素でないとき,\ ax+by=1の整数解は存在しない.} \\ 左辺は3の倍数なので矛盾. \\[1zh] 同値な表現も重要である. \\ \bm{いかなる整数も,\ 互いに素な整数a,\ bを用いてaX+bYの形に表せる.} \\ もちろん,\ a,\ bは互いに素ならば何でもよい. \\ 例えば,\ 13を2X+9Yで表すことも92X+25Yで表すことも可能である. \\ 2X+9Y=13,\ 92X+25Y=13の整数解が存在することと同値である. \\[1zh] 証明は容易で,\ ax+by=1\ (x,\ yの存在が証明済み)\ の\bm{両辺をN倍}すればよい. \\ xy座標平面における格子点と直線35x+21y=15との距離の最小値を$ \\[.2zh]  $(7の倍数)=(7の倍数でない)\ より,\ これを満たすm,\ nは存在しない.方程式の解である.$ 点(x_1,\ y_1)と直線ax+by+c=0の距離の公式 分子の最小値に帰着するわけだが,\ a,\ bは整数であるから,\ \bm{分子は整数}である. \\ よって,\ \bm{最小値を求めるのではなく見つける}方針でいく. \\ つまり,\ 分子が0,\ 1,\ 2,\ \cdots にならないかを順番に調べていけばよい. \\ 結局,\ \bm{35m+21n=N\ を満たす整数解(m,\ n)の存在性に帰着}する. \\ (分子)=0\ となるとき,\ 整数解は存在しないからd=0となることはない. 5,\ 3は互いに素であるから,\ 整数論の基本定理より,\ 整数解が存在するはずである. \\ \bm{整数解を1つ見つけると分子が1になりうる}から,\ これが最小値であるといえる. \\ 定理を知識として持っていることで,\ このような解法が思い浮かぶのである.