2008年度東大理系第5問

この記事の所要時間: 72

問題.

自然数 \(n\) に対し, \(\frac{10^n-1}{9}=\overbrace{111\cdots111}^{n個}\) を \(\fbox{$n$}\) で表す.
たとえば, \(\fbox{1}=1, \fbox{2}=11, \fbox{3}=111\) である.
(1) \(m\) を 0 以上の整数とする. \(\fbox{$3^m$}\) は \(3^m\) で割り切れるが, \(3^{m+1}\) では割り切れないことを示せ.
(2) \(n\) が 27 で割り切れることが, \(\fbox{$n$}\) が 27 で割り切れるための必要十分条件であることを示せ.

方針.

(1) について

\(\fbox{$3^m$}\) は 1 が \(3^m\) 個並んだ数で, \(\fbox{$3^{m+1}$}\) は 1 が \(3^{m+1}=3\cdot 3^m\) 個並んだ数なので, \(\fbox{$3^m$}\) が 3 個並んだ数とみなすこともできます. このことに気がつけば, \(m\) についての帰納法で証明できそうであると分かります.

(2) について

こちらは (1) と比べて難しいですが, まず最初に \(n\) が 9 で割り切れることが, \(\fbox{$n$}\) が 9 で割り切れるための必要十分条件であることをいいます. それを利用して証明していきます.

解答例.

(1) 帰納法を利用します.

[1] \(m=0\) のとき

\(\fbox{$3^0$}=1\) で, これは \(3^0=1\) で割り切れますが, \(3^1=3\) では割り切れません.

よって, \(m=1\) のときは成立.

[2] \(m=k\) のとき成り立っていると仮定します.

つまり, \(\fbox{$3^k$}\) は \(3^k\) では割り切れるが, \(3^{k+1}\) では割り切れないと仮定します.

すると, \(\fbox{$3^k$}=3^kp\), (但し \(p\) は 3 で割り切れない自然数) と書けます.

このとき,

\begin{align}
\fbox{$3^{k+1}$} &= \frac{10^{3^{k+1}}-1}{9}\\
&= \frac{(10^{3^k})^3-1}{9}\\
&= \frac{10^{3^k}-1}{9}\{(10^{3^k})^2+10^{3^k}+1\}\\
&= \fbox{$3^k$}\{(10^{3^k})^2+10^{3^k}+1\}\\
&= 3^kp\{(10^{3^k})^2+10^{3^k}+1\} \tag{\(\ast\)}
\end{align}

ここで, \(\{(10^{3^k})^2+10^{3^k}+1\}\) について,
一般に \(n\) は自然数としたとき \(10^n\) は 9 で割ると 1 余ります.
(\(10^n=9\fbox{$n$}+1\)からも分かると思います).

すると, \(\{(10^{3^k})^2+10^{3^k}+1\}\) を 9 で割ると余りが \(1^2+1+1=3\) になります.
9 で割って余りが 3 なので, 3 では割り切れるが, 9 では割り切れない, ともいえます.

よって, (\(\ast\)) の右辺は 3 で \(k+1\) 回割り切れるが \(k+2\) 回は割り切れないことがわかります.
つまり, \(m=k+1\) のときも成立です.

以上[1], [2] より すべての非負整数 \(m\) について, \(\fbox{$3^m$}\) は \(3^m\) で割り切れるが, \(3^{m+1}\) では割り切れないことが示されました.

(2) まず, \(n\) が 9 で割り切れることが, \(\fbox{$n$}\) が 9 で割り切れるための必要十分条件であることを示します.

\begin{align*}
\fbox{$n$} &= \overbrace{111\cdots111}^{n個}\\
&= 10^{n-1}+10^{n-2}+\cdots+10+1\\
&\equiv 1^{n-1}+1^{n-2}+\cdots+1+1\\
&\equiv n \pmod{9}
\end{align*}

(合同式を使いましたが, ここでは 9 で割った余りが等しいことを表す記号だと思ってください. 合同式について, 詳しくはこちら).

すると, \(\fbox{$n$}\) と \(n\) は 9 で割った余りが一致するので, \(n\) が 9 で割り切れることが, \(\fbox{$n$}\) が 9 で割り切れるための必要十分条件であることが言えました.

今わかっていることは

\(n\equiv0\pmod{9}\Leftrightarrow \fbox{$n$}\equiv0\pmod{9}\)

ここから, \(n\) が 27 で割り切れる場合を考えていきます.

\begin{align*}
\fbox{$n$}\equiv0\pmod{27} &\Leftrightarrow \fbox{$n$}\equiv0\pmod{9}\,かつ\,\fbox{$n$}/9\bmod{3}=0\\
&\Leftrightarrow n\equiv0\pmod{9}\,かつ\,\fbox{$n$}/9\bmod{3}=0 \tag{[\(\ast_1\)]}
\end{align*}

\(n\) が 9 で割り切れるとき, \(n=9b\), (\(b\) は自然数) とおくと,

\begin{align*}
\frac{\fbox{$n$}}{9} &= \frac{10^{9b}-1}{9\cdot 9}\\
&= \frac{10^9-1}{9\cdot 9}\left(10^{9(b-1)}+10^{9(b-2)}+\cdots+10^9+1\right)
\end{align*}

となり, (1) より \(\frac{10^9-1}{9\cdot 9}\) は 3 で割り切れない自然数であるから,

\begin{align*}
[\ast_1] &\Leftrightarrow n\equiv0\pmod{9}\,かつ\, 10^{9(b-1)}+10^{9(b-2)}+\cdots+10^9+1\equiv0\pmod{3}\\
&\Leftrightarrow n\equiv0\pmod{9}\,かつ\, b\equiv0\pmod{3}\\
&\Leftrightarrow n\equiv0\pmod{9}\,かつ\, \frac{n}{9}\equiv0\pmod{3}\\
&\Leftrightarrow n\equiv0\pmod{27}
\end{align*}

よって, \(\fbox{$n$}\) が 27 で割り切れることと \(n\) が 27 で割り切れることは同値であることが示せました.

追記.

問題にはなっていませんが, 今回 (2) の証明で用いた方法を繰り返すことで, 次の命題を示すことができます.

\(m\) を自然数とするとき,

自然数 \(n\) が \(3^m\) で割り切れることは, \(\fbox{$3^m$}\) で割り切れることの必要十分条件である.

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