こんにちは。horyです。
みなさん、合同式 (mod)って知っていますか？
「知ってはいるが使い方が良く分からない」「原理が良く分からない」という声をよく聞きます。
今回の記事では合同式の重要な性質と合同式を用いるメリット・デメリットを中心に記事をまとめました。
合同式とは・・・
まず、そもそも合同式とは「特定の数に注目したとき、全ての整数を特定の数で割った時の余りで判別する」という方法です。
例えば、「３」という数字に注目すると「4」・「5」・「6」は以下のように書けます。
kを整数として一般化すると・・・
次は合同式の面白い性質を紹介します。
問題 合同式の面白い性質
合同式について、和・差・積に関する性質です。
以下は問題になります。できなくてもいいので頭に入れておいてください。
「a≡a’」から「a-a’」はMで割り切れます。同様に「b-b’」もMで割り切れます。
以下では全てmod Mで考えます。なので、解答に(mod M)と書くのは省略します。
和の性質
上のことを証明します。P,Qを整数と考えます。
「①＋②」を考えます。
差の性質
和の性質で示した①から②を引きます。
積の性質
上の性質を証明します。ちょっとテクニックが必要です。
ここで、①と②を活用します。
合同式の長所と短所
以下は私の考える合同式(mod)の長所と短所です。
- 長所・・・計算や場合分けが楽になる
- 短所・・・計算や場合分けを省くことが多くなるため、計算することで発見できることを見落とす。
次からはmodを使わないと解けない問題・modを使うと楽になる(使わなくても解ける)問題を紹介します。
合同式を使わなければならない問題
以下は合同式を使わないと厳しい問題です。
このような問題では以下のことを意識します。
- 係数を低くする
- 次数を低くする
- 二項定理を考える
二項定理に関する記事はこちらに書かれているので読んでみてください
(1)解答・解説
（１）に関しては二項定理を意識して係数を低くします(mod 4用いて)。
上の式の赤い部分は必ず4の倍数になります。
そのため、mod 4を用いて係数を低くできます。
以上から余りは1です。
(2)解答・解説
（１）と同様に考えますが、次数を低くする作業を挟みます(以下mod 9で考える)。
係数を下げることには成功しましたが、このままではうまくいきません。
したがって余りは4になります。
合同式を使うとラクな問題 (使わなくても解けるよ)
以下はmodを使うとラクに解ける問題です。
解答・解説
まずは、式変形を行います。
以下はmod 9で考えます。
以上より、xは「9の倍数」「９で割って4余る数」「9でわって5余る数」になります。
これらを数えると32個になります。
ちなみに、modを用いない場合は・・・
のようにして一つずつ代入して計算することで求めます。
