問題.
今回は,自作問題の31番,2 変数の絡んだ数学的帰納法の問題です.
任意の非負整数 について, を で割った余りが 1 であることを示せ.
この問題はもともと,2 変数の入った問題ではなく, の部分に具体的な数値の入った次のような問題でした.
任意の非負整数 について, を で割った余りが 1 であることを示せ.
この問題をなにかの問題集で見て解いているときに,7 の部分が他の自然数でも成り立つのではないか? と考えて試した結果この問題ができました.
解答例.
タイトルに 2 変数,と書いてはいますが,基本的には について数学的帰納法を用いることになります.(i) のとき
\begin{align*}
(p+1)^{p^n} &= 1^{0^n}\\
&= 1^0\\
&= 1.
\end{align*}
よって,成り立つ.
(ii) のとき
\begin{align*}
(p+1)^{p^n} &= 2^{1^n}\\
&= 2^1\\
&= 2\\
&\equiv 1\pmod{1^{n+1}}.
\end{align*}
よって,成り立つ.
(iii) のとき
\begin{align*}
(p+1)^{p^n} &= (p+1)^{p^0}\\
&= (p+1)^1\\
&= p+1\\
&\equiv 1 \pmod{p^{0+1}}.
\end{align*}
よって,成り立つ.
(iv) のとき
ここで帰納法を使います.
で成り立つと仮定すると,なので, を満たす整数 が存在する.
のときを考えると,
\begin{align*}
(p+1)^{p^{k+1}} &= (p+1)^{{p^k}\cdot p}\\
&= \{(p+1)^{p^k}\}^p\\
&= \{N\cdot p^{k+1}\}^p\\
&= \sum_{i=0}^p {}_pC_i\,\cdot (Np^{k+1})^i\\
&= {}_pC_0\,\cdot(Np^{k+1})^0+{}_pC_1\,\cdot(Np^{k+1})+\sum_{i=2}^p {}_pC_i\,\cdot (Np^{k+1})^i\\
&= 1+Np^{k+2}+\sum_{i=2}^p {}_pC_i\,\cdot (Np^{k+1})^i\\
&= 1+p^{k+2}\{N+N^2p^k\sum_{i=2}^p {}_pC_i\,\cdot (Np^{k+1})^i-2\}\\
&\equiv 1\pmod{p^{k+2}}
\end{align*}
となり, のときも成立.
したがって,(iii), (iv) から を満たす任意の で成立する.
よって,任意の非負整数 について .