問題#B010 ★★☆☆
$n$を正の整数とする。
（１）$9^n-4^n$は$5$の倍数であることを示せ。
（２）$13^n-9^n-4^n$は$36$の倍数であることを示せ。
《ポイント》
こちらも#B009と同様、合同式の威力を味わえる問題です。（合同式についての詳しい内容は「整数第２章第３節」を参照してください）
また、因数分解をしても簡単に示すことができます。その際は$$a^n-b^n = (a-b)(a^{n-1} + a^{n-2}b+ \cdots + ab^{n-2}+b^{n-1})$$という公式を利用することになります。（式変形については「整数第２章第２節第４項」を参照してください）
なお、本問は数学的帰納法によっても証明することができます。
《解答例》
（１）
$$\begin{align} 9^n-4^n & \equiv (-1)^n-(-1)^n \pmod{5} \\ &=0 \end{align}$$
故に $9^n-4^n$ は$5$の倍数である。
□
《（１）別解１ 》
$$\begin{align}& \ \ \ \ \ 9^n-4^n \\ &= (9-4)(9^{n-1} + 9^{n-2} \cdot 4+ \cdots + 9 \cdot 4^{n-2}+4^{n-1}) \\ &= 5N \end{align}$$となる。ここで$N$は整数であり、$N=9^{n-1} + 9^{n-2} \cdot 4+ \cdots + 9 \cdot 4^{n-2}+4^{n-1}$である。
故に $9^n-4^n$ は$5$の倍数である。
□
《（１）別解２ 》
$9^n-4^n$ が$5$の倍数であることを数学的帰納法によって示す。
$n=1$のとき、$9-4=5$ となり成立している。$n=k$のとき $9^k-4^k$ が$5$の倍数であると仮定する。
$$\begin{align}& \ \ \ \ \ 9^{k+1}-4^{k+1} \\
&=9 \cdot 9^k-4 \cdot 4^k \\
&=(10-1) \cdot 9^k-(5-1) \cdot 4^k \\
&=5(2 \cdot 9^k-4^k) – (9^k-4^k) \end{align}$$
$2 \cdot 9^k-4^k$ は整数であるから第1項は$5$の倍数であり、仮定より $9^k-4^k$ は$5$の倍数であるから、$9^{k+1}-4^{k+1}$ も$5$の倍数である。故に $n=k+1$ のときも成立する。
以上より、数学的帰納法から $9^n-4^n$ がすべての正の整数$n$に対して$5$の倍数であることが示された。
□
（２）
$13^n-9^n-4^n$ が$4$でも$9$でも割り切れることを示せばよい。
$$\begin{align} 13^n-9^n & \equiv 1^n-1^n \pmod{4} \\ &=0 \end{align}$$
となるから $13^n-9^n$ は$4$の倍数である。
$$\begin{align} 13^n-4^n & \equiv 4^n-4^n \pmod{9} \\ &=0 \end{align}$$
となるから $13^n-4^n$ は$9$の倍数である。
よって $13^n-9^n-4^n$ は$36$の倍数であることが示された。
□
※（２）でも別解が考えられますが、（１）とほぼ同様の方針なので割愛します。
《コメント》
数学的帰納法は汎用性が高いですが記述量が多くなってしまうという欠点もあります。因数分解もポピュラーな解法ですが、合同式を使えば本問のような問題は文字通り瞬殺です。ご覧の通り、合同式を使った解答の記述量は余りにも少ないため、採点者の心証を損ねるといって毛嫌いする人達や入試で使ってはならないと頑なに信じる人達がいますが、個人的にはこんなに便利な道具を知っているのに使わない手は無いと思います。ただ、使う際には一言で良いので簡単に定義を述べるなどした方が良いかもしれませんね。