合同式（mod）

整数の合同 整数問題を解くにあたって、すごい力を発揮するのは合同式。大学の数学科とかにいくとすぐに同値類を習って、その代表例として出てきます。が、受験数学終わったばかりの生徒に「剰余類」なんていわれても、意外となんで剰余なんていうのかすぐにはピンと来なかったりします。 これから、これを利用する問題も扱っていくかもしれないので、一応、資料としてご覧下さい。 2数 a, b が ｐを法として合同 ⇔ a-b がｐで割り切れる。つまり整数ｋを用いて、a-b=pkとかける。 （あるいは、pで割った余りが等しい） これを a≡ｂ （mod p）で表す。 例えば、 11≡6≡1 （mod 5） 11≡8≡5≡2 (mod 3) という感じです。 この合同式においては、割り算以外の計算は普通の四則演算と同様にできるところがすごいところ。すなわち、