2整数a,\ bを自然数mで割ったときの余りが等しい}}とする.$ \\[.2zh] このとき,\ $\bm{\textcolor{red}{aとbはmを法として合同である}}といい,\ \bm{\textcolor{red}{a\equiv b \pmod m}}\ と表す.$ \\\\ a\equiv b\pmod m\ は,\ そのままa合同bモッドmと呼ぶ. \\[1zh] 合同式は,\ \bm{整数の余りのみに着目した表記法}である. \\[.2zh] 問題を解くのに必須というわけではないので,\ 学校できちんと教わらないことも多い. \\[.2zh] しかし,\ 合同式を使いこなせるか否かで,\ 余りに関する問題の扱いに雲泥の差が生まれる. \\[.2zh] 大学受験では,\ 合同式の習得はほぼ必須と考えておいたほうがよい. \\[1zh] まずは,\ 簡単な例で合同式の理解を深めよう. \ \ 素直に意味を読み取ると,\ 「\,22と15と1は7で割ったときの余りが等しい」である. \\[.2zh] \ \ ただし,\ この場合は「\,22も15も7で割ったときの余りは1である」と読むほうがわかりやすい. \\[.2zh] \ \ \text{mod}\,7\ (7で割ったときの余り)の世界では,\ 22,\ 15,\ 1は同じものなのである. \\[1zh] \rei\ \ 23\equiv3\equiv-\,1\pmod4 (23を4で割ったときの余りは3,\ -\,1である) \\[.2zh] \ \ 実際の問題では,\ より\bm{絶対値が小さい剰余にする}と見通しがよくなることが多い. \\[.2zh] \ \ よって,\ \bm{負の剰余}にも慣れておく必要がある. \\[.5zh] \ \ 0から12までの整数を\text{mod}\,4でみるとこの表のようになる. \\[.2zh] \ \ \text{mod}\,4でみたとき,\ \bm{余り3を余り-1とみなすこともできる}のである. \\[.2zh] \ \ 余り2を余り-2とみなすこともできるが,\ 絶対値が同じものをあえて負にする必要性は低い. \\[1zh] また,\ \bm{合同式の様々な言い換え}をおさえておく. \\[.5zh] 合同式の性質}}a \equiv b \pmod m,\ c \equiv d \pmod m}}のとき$（$a,\ b,\ c,\ d:整数,\ m:自然数$） \\[1zh] \ \textcolor{blue}{和} \textcolor{red}{a+c \equiv b+d \pmod m} \\[.2zh] \ \textcolor{blue}{差} \textcolor{red}{a-c \equiv b-d \pmod m} \\[.2zh] \ \textcolor{blue}{積} \textcolor{red}{ac \equiv bd \pmod m} \\[.2zh] \ \textcolor{blue}{累乗} \textcolor{red}{a^n \equiv b^n \pmod m} 除法}}$（$x,\ y:整数,\ a,\ m:自然数$） \\[.7zh] \ \maru1\ \ $\bm{\textcolor[named]{ForestGreen}{\underline{aとmが互いに素}}}であるとき$ \\[ 特に[1]が重要である.\ 合同式を等式に変換すると容易に証明できる. \\[1zh] ac\equiv bdにおいてcをa,\ dをbにすると\ \ a^2\equiv b^2 これを繰り返すと\ \ a^n\equiv b^n \\\\ よりわかりやすいように,\ 具体例も示しておく. \\[.2zh] a,\ bをそれぞれ5で割ると1,\ 3余る数とすると,\ a=5q_1+\underline{1},\ \ b=5q_2+\underline{3}\ とおける. \\[.2zh] よって,\ a+bを5で割ったときの余りは4,\ abを5で割ったときの余りは3であるとわかる. \\[.2zh] この過程を考慮すると,\ 商q_1,\ q_2\,が関する部分は必ず5でくくれるから,\ 一切余りに影響しない. \\[.2zh] であるならば,\ 最初から余りの部分だけに着目し,\ 1+3=4,\ 1\times3=3\ と求めれば済む. \\[.2zh] これを実現するのが合同式であり,\ \bm{圧倒的に簡潔で本質的な記述が可能になる.} \\\\ さらに,\ 合同式の性質[1]の意義を以下の具体例で理解してほしい. \\[1zh] 24+57,\ 24\times57,\ 57^{100}\,を7で割ったときの余りを求めるとしよう. \\[.2zh] a\equiv b,\ c\equiv dのときa+c\equiv b+dとなることをを利用したわけである. \\[.2zh] 和ならば,\ 24+57=81を7で割って余り4と求めるてもそこまで時間はかからない. \\[.2zh] しかし,\ 積の場合,\ 24\times57を計算してから7で割るのはかなり面倒である. \\[.2zh] ましてや,\ 57^{100}\,に至っては計算すること自体が現実的に難しい. \\[.2zh] [1]は,\ \bm{計算してから余りを求めずとも,\ 余りを求めてから計算できる}ことを意味しているのである. \\[.2zh] また,\ 見方を変えると,\ [1]は普段の\bm{等式と同じ要領で代入できる}ことも意味している. \\[.2zh] これは,\ \bm{等式と同様に移項が可能}であることを意味する. \\[.2zh] \rei\ \ x+4\equiv2\pmod5\ のとき x\equiv2-4\equiv-\,2\equiv3\pmod5 \\[1zh] 以上のように,\ \bm{合同式は,\ 和・差・積に限れば,\ 普通の等式と同じように扱える.} \\[2zh] 一方で,\ \bm{合同式最大の弱点が除法}である. \\[.2zh] 等式とは異なり,\ \bm{合同式では安易に両辺を割ってはならない.} \\[1zh] \maru1は,\ \bm{a,\ mが互いに素ならば,\ 両辺をaで割ってよい}ことを意味する. \\[.2zh] \maru2は,\ \maru1を一般化したものであり,\ \bm{法も含めて両辺をmで割ることができる.} \\[.2zh] 合同式は,\ \bm{異なる法の2数にも弱い.} \\[.2zh] 例えば,\ x\equiv1\pmod5,\ y\equiv2\pmod7\ に対し,\ x+yがどうなるかは単純ではない. \\[2zh] [3]は,\ 次を合同式で表現したものである. \\[.5zh] \bm{積abが素数pの倍数ならば,\ aまたはbがpの倍数である(ユークリッドの補題).} \\[.2zh] これはpが素数だからこそ成り立つ定理である.\ 実際,\ a=2,\ b=3,\ p=6のときは成り立たない. 整数mは7で割ると3余り,\ 整数nは7で割ると5余るとする.$ \\[.2zh] \hspace{.5zw}$このとき,\ 次の式を7で割ったときの余りを求めよ.$ \\[1zh] いちいち\text{mod}\,7と記述するのが面倒なので,\ 一番最初に断っておいた. \\[.2zh] m\equiv3,\ n\equiv5を代入して計算していけばよい. \\[.2zh] 7で割ったときの余りであるから,\ \bm{0から6までの値で答えなければならない}ことに注意する. \\[1zh] \bm{7以上の数は先に余りにしてから計算する}と楽である. \\[.2zh] よって,\ (2)では36\cdot3\cdot5=540ではなく,\ \bm{36\equiv1}としてから計算している. \\[.2zh] (3)の9-125程度ならば計算してから余りを求めてもよいが,\ 9\equiv2,\ 125\equiv6を先に適用した. \\[.2zh] \bm{125\equiv6\equiv-\,1のように絶対値が小さい負の剰余}を利用するとさらに楽である. \\[1zh] なお-4を正の剰余に直すには,\ +\,7をすればよい. \\[.2zh] \bm{7で割ったときの余りは,\ 周期7で循環}しているからである. 仮に合同式を知らない場合,\ m=7p+3,\ n=7q+5などとおいて計算することになる. \\[.2zh] 比較すると,\ 合同式の有用性が一目瞭然である. \\[.5zh]
