整数$a_n=19^n+(-1)^{n-1}2^{4n-3}\quad (n=1,2,3,\dots )$のすべてを割り切る素数を求めよ．
(1986年度 東京工業大学 第1問)
当記事で紹介する解答は東京工業大学(東京科学大学)が示した解答ではありません．
まずは実験して$a_n$を割り切る素数を求める．あとは合同式を使って証明していこう．
まずは実験してみよう．
\[ a_1=19^1+(-1)^{1-1}2^{4\cdot 1-3}=21=3\times 7\]
\[ a_2=19^2+(-1)^{2-1}2^{4\cdot 2-3}=329=7\times 47\]
\[ a_3=19^3+(-1)^{3-1}2^{4\cdot 3-3}=7371=3^4\times 7\times 13\]
よって，すべての$a_n$は$7$で割り切れるのではないかと予想できる．
予想は証明して初めて真の命題となる．$7$を法とする合同式を用いて証明を試みよう．
\[ \begin{aligned}19^n+(-1)^{n-1}2^{4n-3}&\equiv (-2)^n+2\cdot (-1)^{n-1}2^{4n-4}\\ &=(-2)^n+2\cdot (-16)^{n-1}\\ &\equiv (-2)^n+2\cdot (-2)^{n-1}\\ &=(-2)^n-(-2)^n=0\pmod{7}\end{aligned}\]
$m$は正の整数とする．2つの整数$a,b$について$a-b$が$m$の倍数であるとき，$a$と$b$は$m$を法として合同であるといい，式で
\[ \bm{a\equiv b\pmod{m}}\]
と表す．このような式を合同式という．
いとも簡単に解けてしまったが，もう少し深堀りすることにしよう．
難易度:★★★☆☆
\[ \begin{aligned}19^n+(-1)^{n-1}2^{4n-3}&\equiv (-2)^n+2\cdot (-1)^{n-1}2^{4n-4}\\ &=(-2)^n+2\cdot (-16)^{n-1}\\ &\equiv (-2)^n+2\cdot (-2)^{n-1}\\ &=(-2)^n-(-2)^n=0\pmod{7}\end{aligned}\]
よって，$\color{red}7$は$a_n$のすべてを割り切る素数である．
高校数学の教科書には，合同式は発展的な内容として扱われている．解答1と発想は同じだが，合同式を用いずとも証明することができる．
\[ \begin{aligned}&19^n+(-1)^{n-1}2^{4n-3}\\ =&19^n+2\cdot (-1)^{n-1}2^{4n-4}\\ =&19^n+2\cdot (-16)^{n-1}\\ =&(7\cdot 2+5)^n+2\cdot \{ 7\cdot (-3)+5\} ^{n-1}\\ =&\sum_{k=0}^{n}{}_n\mathrm{C}_k(7\cdot 2)^k5^{n-k}+2\sum_{k=0}^{n-1}{}_n\mathrm{C}_k\{ 7\cdot (-3)\} ^k5^{n-k-1}\\ =&5^n+\sum_{k=1}^{n}{}_n\mathrm{C}_k(7\cdot 2)^k5^{n-k}+2\cdot 5^{n-1}+2\sum_{k=1}^{n-1}{}_n\mathrm{C}_k\{ 7\cdot (-3)\} ^k5^{n-k-1}\\ =&7\cdot 5^{n-1}+7\cdot 2\sum_{k=1}^{n}{}_n\mathrm{C}_k14^{k-1}5^{n-k}+7\cdot 2\cdot (-3)\sum_{k=1}^{n-1}{}_n\mathrm{C}_k(-21)^{k-1}5^{n-k-1}\\ =&7\left\{ 5^{n-1}+2\sum_{k=1}^{n}{}_n\mathrm{C}_k14^{k-1}5^{n-k}+2\cdot (-3)\sum_{k=1}^{n-1}{}_n\mathrm{C}_k(-21)^{k-1}5^{n-k-1}\right\} \end{aligned}\]
少々複雑な式変形であるが，証明することはできた．
難易度:★★★☆☆
\[ \begin{aligned}&19^n+(-1)^{n-1}2^{4n-3}\\ =&19^n+2\cdot (-1)^{n-1}2^{4n-4}\\ =&19^n+2\cdot (-16)^{n-1}\\ =&(7\cdot 2+5)^n+2\cdot \{ 7\cdot (-3)+5\} ^{n-1}\\ =&\sum_{k=0}^{n}{}_n\mathrm{C}_k(7\cdot 2)^k5^{n-k}+2\sum_{k=0}^{n-1}{}_n\mathrm{C}_k\{ 7\cdot (-3)\} ^k5^{n-k-1}\\ =&5^n+\sum_{k=1}^{n}{}_n\mathrm{C}_k(7\cdot 2)^k5^{n-k}+2\cdot 5^{n-1}+2\sum_{k=1}^{n-1}{}_n\mathrm{C}_k\{ 7\cdot (-3)\} ^k5^{n-k-1}\\ =&7\cdot 5^{n-1}+7\cdot 2\sum_{k=1}^{n}{}_n\mathrm{C}_k14^{k-1}5^{n-k}+7\cdot 2\cdot (-3)\sum_{k=1}^{n-1}{}_n\mathrm{C}_k(-21)^{k-1}5^{n-k-1}\\ =&7\left\{ 5^{n-1}+2\sum_{k=1}^{n}{}_n\mathrm{C}_k14^{k-1}5^{n-k}+2\cdot (-3)\sum_{k=1}^{n-1}{}_n\mathrm{C}_k(-21)^{k-1}5^{n-k-1}\right\} \end{aligned}\]
よって，$\color{red}7$は$a_n$のすべてを割り切る素数である．
ところで本問は，すべての正の整数に関する命題であるから，$n$に関する数学的帰納法で証明することもできそうだ．
$n=1$のとき，$a_1=21$は$7$の倍数．これは明らかである．
$n=k$のとき，すなわち$a_k$が$7$の倍数であると仮定すると
\[ \begin{aligned}a_{k+1}&=19^{k+1}+(-1)^k2^{4k+1}\\ &=19^{k+1}+2\cdot (-1)^k2^{4k}\\ &=19^{k+1}+2\cdot (-16)^k\\&=19\cdot 19^k+(-16)\cdot 2\cdot (-16)^{k-1}\\ &=35\cdot 19^k+(-16)\cdot \{ 19^k+2\cdot (-16)^{k-1}\} \\ &=7\cdot 5\cdot 19^k-16a_k\end{aligned}\]
よって，$a_{k+1}$も$7$の倍数である．
式変形に少し工夫が必要だが，示すことはできた．
難易度:★★★☆☆
すべての$a_n$が$7$の倍数であることを，$n$に関する数学的帰納法で示す．
$n=1$のとき，$a_1=21$は$7$の倍数．
$n=k$のとき，すなわち$a_k$が$7$の倍数であると仮定すると
\[ \begin{aligned}a_{k+1}&=19^{k+1}+(-1)^k2^{4k+1}\\ &=19^{k+1}+2\cdot (-1)^k2^{4k}\\ &=19^{k+1}+2\cdot (-16)^k\\&=19\cdot 19^k+(-16)\cdot 2\cdot (-16)^{k-1}\\ &=35\cdot 19^k+(-16)\cdot \{ 19^k+2\cdot (-16)^{k-1}\} \\ &=7\cdot 5\cdot 19^k-16a_k\end{aligned}\]
よって，$a_{k+1}$も$7$の倍数である．
以上より，$\color{red}7$は$a_n$のすべてを割り切る素数である．
さて，ここまで3通りの解答を紹介した．ここからは，この問題をさらに深堀りしていく．