整数の合同

整数問題を解くにあたって、すごい力を発揮するのは合同式。大学の数学科とかにいくとすぐに同値類を習って、その代表例として出てきます。が、受験数学終わったばかりの生徒に「剰余類」なんていわれても、意外となんで剰余なんていうのかすぐにはピンと来なかったりします。

これから、これを利用する問題も扱っていくかもしれないので、一応、資料としてご覧下さい。

2数 a, b が　ｐを法として合同 ⇔ a-b がｐで割り切れる。つまり整数ｋを用いて、a-b=pkとかける。 （あるいは、pで割った余りが等しい） これを a≡ｂ　（mod p）で表す。

例えば、
11≡6≡1　（mod 5）
11≡8≡5≡2　 (mod 3)　という感じです。

この合同式においては、割り算以外の計算は普通の四則演算と同様にできるところがすごいところ。すなわち、

a≡b , c≡d (mod p) ならば, a±c≡b±d (mod p)　ac≡bd (mod p)

とくに、積がOKってことから、何回も使うと、
a≡b (mod ｐ) ならば　a^k≡b^k (mod ｐ)

証明は、a-b=pk とかやって計算していけばできます。

なお、割り算に関しては、

ac≡bc (mod p)でpとcが互いに素 ならば、a≡b (mod p)

とかが成り立ちます。ほか、ｐが素数だったりするとさらにいろいろ・・・

使用例
　倍数判定法　（ページの真ん中あたりにmod を利用した証明があります。）
　一次不定方程式の定理　（下のほうの一次不定方程式の解法�Bです。）
　合同式の練習問題　
　フェルマー数を用いた素数が無限個であることの証明
幾何の本を読んでみたら、証明の中で、「mod π/2」とかいう表記をしていました。いちいち整数mを使って表すより、すっきりします。

参考文献
初めて学ぶ人のための群論入門　横田一郎　著　現代数学社
大学への数学　マスターオブ整数　東京出版
大学入試数学の五面相　石谷　茂　著　現代数学社



数学のページに戻る

トップに戻る