問題.
次の問に答えよ.
(1) \(n\) を正の整数, \(a = 2^n\) とする. \(3^a-1\) は \(2^{n+2}\) で割り切れるが \(2^{n+3}\) で割り切れないことを示せ.
(2) \(m\) を正の偶数とする. \(3^m-1\) が \(2^m\) で割り切れるならば \(m = 2\) または \(m=4\) であることを示せ.
(1) は典型的な数学的帰納法の問題です.
ちなみに, この問題をより一般化して,
「正の整数 \(n, p\) に対して, \(a = p^n\) とすると, \((p+1)^a-1\) は \(p^{n+2}\) で割り切れるが \(p^{n+3}\) で割り切れない」
ことを\(p\) と\(n\) の両方について帰納法を使うことで示すことができます.
(自作問題の問題31では, \((p+1)^{p^n}\) が \(p^{n+1}\) で割り切れることを問うています. )
さて, (2) では (1)利用します. \(m\) が 2 の累乗ではなく, 偶数となっている部分を上手く処理できるかがカギですね.
また,
\begin{align*}
X^s-1 = (X-1)(X^{s-1}+X^{s-2}+\cdots+X+1)
\end{align*}
の変形も覚えておきましょう.
解答例.
(1) 数学的帰納法を使います.
[1] \(n=1\) のとき
\(a = 2\) で, \(3^a-1 = 8\) は\(2^{1+2} = 8\) で割り切れ, \(2^{1+3} = 16\) では割り切れない.
よって, \(n=1\) のときは成り立つ.
[2] \(n = k\) \((k\geqq 1)\)のとき成り立つと仮定すると,
\(3^{2^k}-1\) が \(2^{k+2}\) で割り切れ, \(2^{k+3}\) で割り切れないので,
\begin{align*}
3^{2^k}-1 = 2^{k+2}p
\end{align*}
と書けます (\(p\) は奇数).
すると,
\begin{align*}
3^{2^{k+1}}-1 &= (3^{2^k})^2-1\\
&= (2^{k+2}p+1)^2-1\\
&= (2^{k+2}p)^2 + 2\cdot 2^{k+2}p + 1 – 1\\
&= 2^{2k+4}p^2 + 2^{k+3}p\\
&= 2^{k+3}p(2^{k+1}+1)
\end{align*}
(指数の計算 \(3^{2^{k+1}} = (3^{2^k})^2\) となる部分を間違えないように注意しましょう!!)
ここで, \(p\) は奇数で, \(k\geqq 1\) より \(2^{k+1}+1\) も奇数なので,
\(3^{2^{k+1}}-1\) は \(2^{k+3}\) で割り切れるが \(2^{k+4}\) では割り切れない.
よって, \(n = k + 1\) のときも成り立つ.
したがって, [1], [2] より, すべての正の整数 \(n\) について
\(3^{2^n}-1\) は \(2^{n+2}\) で割り切れるが, \(2^{n+3}\) では割り切れない.
(2) (1)で証明したことを利用していきます.
\(m\) が \(2^r\) で割り切れて \(2^{r+1}\) で割り切れないような \(r\geqq 1\) を選んで,
\(m = 2^r\cdot q\)
とおきます. (\(q\) は奇数)
\(3^m-1\) が 2 で何回割り切れるかを調べます.
\(b = 2^r\) とおいて,
\begin{align*}
3^m-1 &= 3^{bq}-1\\
&= (3^b)^q – 1\\
&= (3^b-1)\{(3^b)^{q-1}+(3^b)^{q-2}+\cdots+1\}
\end{align*}
(2 行目から 3 行目の変形がカギです. )
ここで, 右辺の \(3^b-1\) は (1) の結果から, \(2^{r+2}\) で割り切れ, \(2^{r+3}\) では割り切れません.
また, \((3^b)^{q-1}+(3^b)^{q-2}+\cdots+1\) は各項は 3 の累乗なので奇数で, \(q\) 個(奇数個) 足したものなので, 奇数, つまり 2 で割り切れません.
よって, \(3^m-1\) は \(2^{r+2}\) で割り切れ, \(2^{r+3}\) で割り切れないことが分かりました.
\(3^m-1\) が \(2^m\) で割り切れるためには,
\begin{align*}
m\leqq r+2
\end{align*}
つまり,
\begin{align*}
2^rq\leqq r+2
\end{align*}
が必要十分条件になっています.
\(r \geqq 3\) のときは, \(2^r > r+2\) となることが帰納法で示されるので, \(q\geqq 1\) に対して上の不等式は成り立ちません.
\(r=1\) のとき
\(2^r = 2\), \(r+2 = 3\) なので, 上の不等式を満たす \(q\) は \(q = 1\) のみ,
\(r=2\) のとき
\(2^r = 4\), \(r+2 = 4\) なので, 上の不等式を満たす \(q\) は \(q = 1\) のみ, となります.
したがって, \(m\) としては \(m = 2, 4\) のみとなります.