問題はこちら（画像をクリックするとPDFファイルで開きます。）
シンプルな整数問題で、教訓を多く含む問題です。
場当たり的に解き進めても、腕力がある人はねじ伏せることができるでしょうが、できれば戦略的に解き進めていく態度で解けるようにしたいところです。
（以下ネタバレ注意）
+クリック（タップ）して続きを読む 自然数 \(n\) にまつわる証明問題ということで、数学的帰納法にとびついた人もいると思いますが、闇雲に飛びついてもそれは毒饅頭です。 以下失敗例です。 失敗例 (i) \(n=1\) のとき \(2^{1}+1=3\) で、これは 15 で割り切れない。 (ii) \(n=k\) \((k=1 \ , \ 2 \ , \ 3 \ \cdots)\) のとき \(2^{k}+1 \neq 15M\) (\(M\) は整数)と仮定する。 このとき、 \(2^{k+1}+1=2\cdot2^{k}+1\) 仮定より、\(2^{k} \neq 15M-1\) より、\(2^{k+1}+1 \neq 2 (15M-1)+1\) よって、 \(2^{k+1}+1 \neq 15 (2M-1)+14\) 帰納法の結論的には \(f(k+1)\) が 15 で割り切れない という結論を待っていました。 ところが言えた結論は \(f(k+1)\) が余り 14 とならない と言えただけです。 余り 14 が否定されただけなので、余り 0 かもしれません。 よって帰納法失敗です。 機械的に帰納法という解法を当てはめてもうまくいかないことが分かりました。 睨めっこするのではなく、手を動かして実験してみることにします。 実験 \(f(n)=2^{n}+1\) とおくと \(f(1)=3\) で、余りは 3 \(f(2)=5\) で、余りは 5 \(f(3)=9\) で、余りは 9 \(f(4)=17\) で、余りは 2 \(f(5)=33\) で、余りは 3 \(f(6)=65\) で、余りは 5 \(f(7)=129\) で、余りは 9 \(f(8)=257\) で、余りは 2 ということで、15 で割った余りは 3 , 5 , 9 , 2 という周期性をもつことが分かります。 この周期性が保証されれば、15 で割った余りの中に 0 が登場しないことが保証され、15 で割り切れないことが分かります。 今回の周期は 4 です。 つまり、\(f(n+4)\) と \(f(n)\) を 15 で割った余りが等しいことを示せばよいことになります。 合同式的には \(f(n+4) \equiv f(n)\) (mod 15) を示せばよいわけです。 これを示すには、\(f(n+4)-f(n)\) が 15 の倍数であることを目指します。 そうなると \((2^{n+4}+1)-(2^{n}+1)\) \(=2^{4}\cdot2^{n}-2^{n}\) \(=(2^{4}-1)2^{n}\) \(=15\cdot 2^{n}\) となり、解決します。 例えば \(3^{n}\) を 10 で割った余りを考えてみます。 10 で割った余りというのは 10進法における 1 の位 です。 \(3^{n}\) の 10進法における 1 の位は 3 , 9 , 7 , 1 の繰り返しです。 1 の位については以前登場した数と同じ数が登場すれば、同じことが繰り返される（周期性をもつ）ことになります。 \(2^{n}\) を 15 で割った余りは \(2^{n}\) の15進法における 1 の位 です。 先ほど述べたように、１の位は以前登場した数が再登場すれば繰り返しが起こるわけですが、15進法ということは数を 15 個しか使いません。 つまり 最大でも 16 回目には同じ数が登場する ということになるわけです。 このことから \(2^{n}\) を 15 で割った余りは周期性をもつことになります。 本問は \(+1\) がくっついていますが、それは１の位がずれるだけで、周期性を持つこと自体に変わりありません。 今述べたことは何進法でも変わりません。 したがって、自然数の累乗を何かで割った余りは周期性をもつことになります。 本問を通じて学べることは２つあります。 それは ①：行き詰まったときこそ、手を動かして実験することの大切さ ②：自然数の累乗を何かで割った余りは周期性をもつ ということです。 ①は分野を問わず大切なことで、実験して規則性などを見出しながら話を進めていくきっかけをつかむのは難問に立ち向かうにあたり必要な態度です。 ②は分野特有の重要事項で、整数問題を崩す一つのきっかけとなり得ます。闇雲に帰納法を用いても失敗する
何が失敗か
リカバリー
周期性の証明
自然数の累乗の余りについて
\(m\) で割った余りは \(m\)進法における１の位
本問で言うと
本問の教訓