2 変数の数学的帰納法(自作問題31)

この記事の所要時間: 314

問題.

今回は,自作問題の31番,2 変数の絡んだ数学的帰納法の問題です.

問題.

任意の非負整数 \(p, n\) について,\((p+1)^{p^n}\) を \(p^{n+1}\) で割った余りが 1 であることを示せ.

この問題はもともと,2 変数の入った問題ではなく,\(p\) の部分に具体的な数値の入った次のような問題でした.

元の問題.

任意の非負整数 \(n\) について,\(8^{7^n}\) を \(7^{n+1}\) で割った余りが 1 であることを示せ.

 この問題をなにかの問題集で見て解いているときに,7 の部分が他の自然数でも成り立つのではないか? と考えて試した結果この問題ができました.

解答例.

タイトルに 2 変数,と書いてはいますが,基本的には \(n\) について数学的帰納法を用いることになります.

(i) \(p=0\) のとき
\begin{align*}
(p+1)^{p^n} &= 1^{0^n}\\
&= 1^0\\
&= 1.
\end{align*}よって,成り立つ.

(ii) \(p=1\) のとき
\begin{align*}
(p+1)^{p^n} &= 2^{1^n}\\
&= 2^1\\
&= 2\\
&\equiv 1\pmod{1^{n+1}}.
\end{align*}よって,成り立つ.

(iii) \(n=0\) のとき
\begin{align*}
(p+1)^{p^n} &= (p+1)^{p^0}\\
&= (p+1)^1\\
&= p+1\\
&\equiv 1 \pmod{p^{0+1}}.
\end{align*}よって,成り立つ.

(iv) \(p\geq 2, n\geq 1\) のとき
ここで帰納法を使います.
\(n=k\) で成り立つと仮定すると,
\((p+1)^{p^k}\equiv 1\pmod{p^{k+1}}\)
なので,\((p+1)^{p^k}-1=N\cdot p^{k+1}\) を満たす整数 \(N\) が存在する.
\(n=k+1\) のときを考えると,
\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*}となり,\(n=k+1\) のときも成立.

したがって,(iii), (iv) から \(p\geq 2, n\geq 0\) を満たす任意の \(p, n\) で成立する.
よって,任意の非負整数 \(n, p\) について \((p+1)^{p^n}\equiv 1\pmod{(p^{n+1}}\).

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加