3.2 合同式の応用例
幾つかの例題について、合同式を使わない解法と使う解法とを比較してみましょう。
解答例（mod非対応）
二項定理を利用すると、$$\small \begin{align} 8^n &=(7+1)^n \\ &=7^n+{}_n\mathrm{C}_{1} \cdot 7^{n-1}+ \cdots + {}_n\mathrm{C}_{n-1} \cdot 7+1 \\ &=7N+1 \ \ (N \in \mathbb{N}) \end{align}$$と書けるから、$8^{n}$を$7$で割ったときの余りは$$1 \ \cdots \cdots (\text{答})$$である。
解答例（mod対応）
$\text{mod }7$で考える。$8 \equiv 1$より、$$8^n \equiv 1^n=1$$となるから、$8^{n}$を$7$で割ったときの余りは$$1 \ \cdots \cdots (\text{答})$$である。
（コメント）
ご覧の通り、やってることの本質はどちらも同じなのですが、mod対応の解法の方が記述量を抑えられます。第2章で見たような数学的帰納法を使った解答も考えられるので、その差は歴然ですね。合同式が試験時間を確保する強力なツールであることがお分かりいただけると思います。
解答例（mod非対応）
$n$を$5$で割ったときの余りで分類し、場合分けする。以下、$k$は$0$以上の整数とする。
ⅰ）$n=5k$のとき、$n^2=25k^2$となるから、$n^2$を$5$で割ったときの余りは$0$である。
ⅱ）$n=5k+1$のとき、$n^2=25k^2+10k+1=5(5k^2+2k)+1$となる。$5k^2+2k$は整数だから、$n^2$を$5$で割ったときの余りは$1$である。
ⅲ）$n=5k+2$のとき、$n^2=25k^2+20k+4=5(5k^2+4k)+4$となる。$5k^2+4k$は整数だから、$n^2$を$5$で割ったときの余りは$4$である。
ⅳ）$n=5k+3$のとき、$n^2=25k^2+30k+9=5(5k^2+6k+1)+4$となる。$5k^2+6k+1$は整数だから、$n^2$を$5$で割ったときの余りは$4$である。
ⅴ）$n=5k+4$のとき、$n^2=25k^2+40k+16=5(5k^2+8k+3)+1$となる。$5k^2+8k+3$は整数だから、$n^2$を$5$で割ったときの余りは$1$である。
以上の場合ですべての自然数を尽くしているから、$n^2$を$5$で割ったときの余りは$0、1、4$に限ることが示された。
解答例（mod対応①）
$\text{mod }5$で考える。
$n \equiv 0$のとき$n^2 \equiv 0$、$n \equiv 1$のとき$n^2 \equiv 1$、$n \equiv 2$のとき$n^2 \equiv 4$、$n \equiv 3$のとき$n^2 \equiv 9 \equiv 4$、$n \equiv 4$のとき$n^2 \equiv 16 \equiv 1$となる。
以上の場合ですべての自然数を尽くしているから、$n^2$を$5$で割ったときの余りは$0、1、4$に限ることが示された。
解答例（mod対応②）
$\text{mod }5$で考えると以下の表のように$5$で割ったときの余りが対応する。
| $n$ | ０ | １ | ２ | ３ | ４ |
| $n^2$ | ０ | １ | ４ | ４ | １ |
故に$n^2$を$5$で割ったときの余りは$0、1、4$に限ることが示された。
（コメント）
modを使うと解答の省スペース化が可能となります。その点でmodと表の組み合わせは、省スペース化とともに視覚に訴えることができる非常に便利な方法と言えますが、解答自体が非常に素っ気ないものとなってしまいます。
採点者の心証を損ねないためにも、
「整数$a、b$について、$a-b$が自然数$n$で割り切れることを$a \equiv b \pmod{n}$と表すことにする。」
などと合同式の定義くらいは添えておくと良いでしょう。
（※$a-b$が自然数$n$で割り切れることと$a \equiv b \pmod{n}$は同値です（前頁参照のこと））
解答例（mod非対応）
$$\small \begin{align} n^5-n &=n(n^4-1) \\ &=n(n^2-1)(n^2+1) \\ &=(n-1)n(n+1)(n^2+1) \end{align}$$より、3連続する整数の積を含むから$n^5-n$は$6$の倍数である。よって$n^5-n$が$30$で割り切れることを示すためには$n^5-n$が$5$で割り切れることを示せば良い。
$n$を$5$で割ったときの余りで分類し、場合分けする。以下、$k$は$0$以上の整数とする。
ⅰ）$n=5k$のとき、$n^5-n$は$5$の倍数である。
ⅱ）$n=5k+1$のとき、$$\small \begin{align} n^5-n &=(n-1)n(n+1)(n^2+1) \\ &=5 \underline{k(5k+1)(5k+2)(25k^2+10k+2)} \end{align}$$となる。下線部は整数だから、$n^5-n$は$5$の倍数である。
ⅲ）$n=5k+2$のとき、$$\small \begin{align} n^5-n &=(n-1)n(n+1)(n^2+1) \\ &=(5k+1)(5k+2)(5k+3)(25k^2+20k+5) \\ &=5 \underline{(5k+1)(5k+2)(5k+3)(5k^2+4k+1)} \end{align}$$となる。下線部は整数だから、$n^5-n$は$5$の倍数である。
ⅳ）$n=5k+3$のとき、$$\small \begin{align} n^5-n &=(n-1)n(n+1)(n^2+1) \\ &=(5k+2)(5k+3)(5k+4)(25k^2+30k+10) \\ &=5 \underline{(5k+1)(5k+2)(5k+3)(5k^2+6k+2)} \end{align}$$となる。下線部は整数だから、$n^5-n$は$5$の倍数である。
ⅴ）$n=5k+4$のとき、$$\small \begin{align} n^5-n &=(n-1)n(n+1)(n^2+1) \\ &=(5k+3)(5k+4)(5k+5)(25k^2+40k+17) \\ &= 5 \underline{(k+1)(5k+3)(5k+4)(25k^2+40k+17)} \end{align}$$となる。下線部は整数だから、$n^5-n$は$5$の倍数である。
以上より、$n^5-n$はすべての自然数$n$に対して$5$の倍数となるから、$n^5-n$が$30$で割り切れることが示された。
解答例（mod対応）
$\text{mod }5$で考える。
$n \equiv 0$のとき、$n^5-n \equiv 0-0=0$、
$n \equiv 1$のとき、$n^5-n \equiv 1^5-1=0$、
$n \equiv 2$のとき、$n^5-n \equiv 2^5-2=30 \equiv 0$、
$n \equiv 3$のとき、$n^5-n \equiv 3^5-3=3(3^4-1)=3 \cdot 80 \equiv 0$、
$n \equiv 4 \ (\equiv -1)$のとき、$n^5-n \equiv (-1)^5-(-1)=-1+1=0$となる。
よって$n^5-n$はすべての自然数$n$に対して$5$の倍数となるから、$n^5-n$が$30$で割り切れることが示された。
（コメント）
「$5$の倍数を作る」という目的意識を持って式変形すればmodを使う必要はありませんが、やはり答案を記述する労力が変わってきます。実際、mod対応の解答例を書く際に、頭を使うような場面はほとんどありません。このように2パターンの解答を書き比べてみると合同式の威力を実感できると思います。
とりあえず応用例の紹介はこのくらいにしておきましょう。勿論、合同式がいつでもどこでも万能という訳ではありません。ちゃんと文字で置いた方が解答が作りやすい場合も多いので、問題演習で勘所を掴んでいって欲しいと思います。