整数問題の神すぎるツール”mod”を紹介‼︎　　　第2弾 〜modの力を体験しよう〜

整数問題を解くときに欠かせないmodについて解説していきたいと思います｡
これを知っているのといないのとでは大違いなので，ぜひ読んでみてください‼︎

1. 合同式の便利すぎる性質

第1弾の内容に入れ忘れていたのでまず合同式の性質について解説していきます‼︎
その前に…
合同式ってなんやねん‼︎
1+2=3 　　　　 …等式
3≡15 (mod12)  …合同式
　簡単に言えば，合同の記号≡を使った式が合同式ですね‼︎

復習になりますが，皆さんは等式では次のルールが成り立つことを知っていますよね?

　　 a = b ならば
　a+c = b+c　　(両辺に同じ数を足しても成り立つ)
　a-c  = b-c　　 (両辺から同じ数を引いても成り立つ)
　  ac = bc　　  (両辺に同じ数を掛けても成り立つ)
　a÷c = b÷c 　  (両辺を同じ数で割っても成り立つ)
　a^c = b^c　　 (両辺を累乗しても成り立つ)
　(↑この山みたいなマーク^は，aのc乗を表します)

それと同じように，合同式でもこのルールが使えます‼︎ただし，割 り 算 は 除 き ま す

mod n のもとで，
　    a ≡ b ならば
　a+c ≡ b+c　　(両辺に同じ数を足しても成り立つ)
　a-c  ≡ b-c　　 (両辺から同じ数を引いても成り立つ)
　  ac ≡ bc　　  (両辺に同じ数を掛けても成り立つ)
a÷c ≡ b÷c 　  (両辺を同じ数で割っても成り立つ)
　a^c ≡ b^c　　 (両辺を累乗しても成り立つ)

例えばmod12で15≡75なので，
　15-10 ≡ 75-10は成り立ちますが，
　15÷3  ≡ 75÷3
　　　5  ≡ 25　は成り立ちませんね｡

割り算もできるのには上の”ルール”で「c⊥n」が成り立つ必要があるのですが，そんなのあまり使わないので覚えなくていいです‼︎

2. 問題を解こう‼︎

準備は整いました｡いよいよ問題を解いていきましょう‼︎

問1　3^10を4で割った余りを求めよ｡

この問題，普通に解くと3の10乗を求めるという超面倒臭い計算をしなければなりません｡ここでmodの出番です‼︎

(解答)
　　余りをxとおくと，mod4のもとで，
　　　x≡3^10
　　　3≡-1より，
　　　x≡(-1)^10
　　　x≡1
　　よって，余りは1

どうでしょうか⁉︎
合同式を利用することで，3の10乗という面倒な計算を-1の10乗という簡単な計算に置き換えられるのですね｡このように，大きな数を小さな数に置き換えられるというのがmodの大きな強みとなります｡
ではもう1問いきましょう‼︎

問2　8^100を3で割った余りを求めよ｡

8の100乗なんて人間じゃ無理ですね(笑)｡問1と同じように合同式が使えます｡

(解答)
　mod3のもとで，
　　8^100≡(-1)^100≡1
　よって余りは1

8を-1に置き換えられるのが強すぎる…
この2つの問題はどちらも-1に置き換えられるので簡単ですが，そうはいかない場合もありますよね｡ということで次の問3を見てみましょう‼︎

問3　7^30を5で割った余りを求めよ｡

(解答)
　mod5のもとで，
　　7^30≡2^30
　　　　  ≡4^15
　　　　  ≡(-1)^15
　　　　  ≡-1
　　　　  ≡4
　よって余りは4

mod5で，7は-1と合同ではないので，置き換えられません。しかし，指数法則を使って4^15を作れれば4を-1に置き換えることができますよね｡このように，いかにして1や
-1などの累乗を簡単に計算できる数を作るかがポイントになります♪

3. 終わりに

今回はmodを使って問題を解いていきました｡ですがmodはまだまだ他にも使い方がたくさんあります｡第3弾では，いよいよ一次不定方程式などの問題を解いていく予定なので，是非見てみてください‼︎