問題#B012 ★★☆☆
$n$を正の整数とするとき、$2^n+1$ は$15$で割り切れないことを示せ。
《ポイント》
「割り切れないこと」を示す問題はあまり見慣れないかもしれません。取り敢えず$15$が合成数なので$3$と$5$に分けて余りを考えましょう。
$2^n+1$ の値を小さい$n$で調べてみると、$3$、$5$、$9$、$17$、$33$、$\cdots$となるので、$n$が奇数のときにのみ$3$の倍数となることが予想できます。その上で $2^n+1$ が奇数のとき$5$の倍数にならないことを示せば解決しそうです。
《解答例》
$\begin{align}& \ \ \ \ \ 2^n+1 \\
&\equiv (-1)^n+1 \pmod{3} \end{align}$
となり $(-1)^n+1=0$ となるのは$n$が奇数のときに限る。そこで $0 \leqq k$ を満たす整数$k$を用いて $n=2k+1$ と表すと、
$\begin{align}& \ \ \ \ \ 2^{2k+1}+1 \\
&=2 \cdot 4^k+1 \\
&\equiv 2 \cdot (-1)^k+1 \pmod{5} \end{align}$
となるが、$2 \cdot (-1)^k+1$ はいかなる整数$k$に対しても$0$となることはない。故に $2^n+1$ は奇数のとき$5$の倍数にならない。
したがって $2^n+1$ はいかなる正の整数$n$に対しても$15$で割り切れない。
□
《コメント》
いきなり$15$を相手にすると大変なので、$3$と$5$に分けた方が議論しやすくなります。なお、倍数の証明では$2^n=(3-1)^n$や$4^k=(5-1)^k$などとして展開しても良いですし、$5$の倍数になるかどうかは$2^n$の一の位に着目しても良いでしょう。