合同式の定義と性質 a≡b (mod m)

スポンサーリンク
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などとおいて計算することになる. 比較すると,\ 合同式の有用性が一目瞭然である.