整数第２章第３節　２．合同式の応用例

解答例（mod非対応）

二項定理を利用すると、$$\begin{array}{rl}{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{array}$$と書けるから、$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非対応）

$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^2$を$5$で割ったときの余りは$0、1、4$に限ることが示された。

解答例（mod非対応）

$$\begin{array}{rl}{n}^5-n& =n(n^4-1)\\ & =n(n^2-1)(n^2+1)\\ & =(n-1)n(n+1)(n^2+1) \end{array}$$より、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$のとき、$$\begin{array}{rl}{n}^5-n& =(n-1)n(n+1)(n^2+1)\\ & =5\underset{―}{k(5k+1)(5k+2)(25k^2+10k+2)}\end{array}$$となる。下線部は整数だから、$n^5-n$は$5$の倍数である。

ⅲ）$n=5k+2$のとき、$$\begin{array}{rl}{n}^5-n& =(n-1)n(n+1)(n^2+1)\\ & =(5k+1)(5k+2)(5k+3)(25k^2+20k+5)\\ & =5\underset{―}{(5k+1)(5k+2)(5k+3)(5k^2+4k+1)}\end{array}$$となる。下線部は整数だから、$n^5-n$は$5$の倍数である。

ⅳ）$n=5k+3$のとき、$$\begin{array}{rl}{n}^5-n& =(n-1)n(n+1)(n^2+1)\\ & =(5k+2)(5k+3)(5k+4)(25k^2+30k+10)\\ & =5\underset{―}{(5k+1)(5k+2)(5k+3)(5k^2+6k+2)}\end{array}$$となる。下線部は整数だから、$n^5-n$は$5$の倍数である。

ⅴ）$n=5k+4$のとき、$$\begin{array}{rl}{n}^5-n& =(n-1)n(n+1)(n^2+1)\\ & =(5k+3)(5k+4)(5k+5)(25k^2+40k+17)\\ & =5\underset{―}{(k+1)(5k+3)(5k+4)(25k^2+40k+17)}\end{array}$$となる。下線部は整数だから、$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$で割り切れることが示された。