合同式は様々な場面で使える便利な記法です。見た目よりも難しくないですから、使い慣れてしまいましょう。
合同式の定義
$a$と$b$を$n$で割った余りが等しいとき、
$a$≡$b$($\rm{mod}$ $n$)
と書く。
例えば、
12≡2(mod 5)
と書けば、12と2は、5で割った余りが等しい
ということを意味します。
他にも、
12≡7(mod 5)
と書いて、12と7は、5で割った余りが等しい
としても構いません。
これ自体は大した意味を持ちません。余りのみに注目したいときに、省略して書ける便利な記法だということです。
合同式の利用
合同式の表記
27≡2≡－3(mod 5)
のように、つなげて書くこともできます。
(順に5の倍数を引いていっているだけです。)
2から5を引いたー3も5で割ると余り2なんです。
例題１
8≡1，9≡2，10≡3，11≡4(mod 7)
なので、
8×9×10×11≡1×2×3×4≡24≡3(mod 7)
より、余りは3です。
簡単すぎて不安になりますか？
8×9×10×11＝(7+1)×(7+2)×(7+3)×(7+4)と変形して、これを展開してみましょう。
$=7^{4}+1\cdot7^{3}+2\cdot7^{3}+3\cdot7^{3}+\cdots+1\cdot2\cdot3\cdot4$
7の倍数にならないものはどれですか？
7で割った余りを求めたいわけですが、注目しないといけないのは $1\cdot2\cdot3\cdot4$ だけです。
他の7の倍数は捨ててしまって構わないのです。
例題２
$7≡1({\rm mod}\,6)$なので、
$7^{100}≡1^{100}≡1({\rm mod}\,6)$
より、余りは１。
例題３
$2^{3}=8$とすれば7より大きくなりますから、8－7＝1とできますね。解答はこうです。
$2^{100}≡8^{33}\cdot2≡1^{33}\cdot2≡2({\rm mod}\,7)$
より、余りは２。
例題４
$2^{100}≡64^{16}\cdot2^{4}≡1^{16}\cdot16≡7({\rm mod}\,9)$
より、余りは7。
別解
「1」を作るのがポイントだったわけですが、「－1」を作っても上手くいくんです。
（9の倍数）－1となる数を、2の累乗で作れますか？
$2^{100}≡8^{33}\cdot2≡(-1)^{33}\cdot2≡-2≡7({\rm mod}\,9)$
より、余りは7。
