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