トップ› 東京大学› 2008年› 理系第5問

東京大学 2008年理系第5問解説

方針・初手

（1）は $m$ についての命題であるため、数学的帰納法を用いるのが自然である。$\boxed{3^{k+1}}$ を $\boxed{3^k}$ を用いて表し、因数分解によって「3を素因数としていくつ持つか」に注目して証明を進める。

（2）は（1）の誘導を活用する。$n$ を27で割った商と余りを利用して $\boxed{n}$ を分解し、余りに関する条件に帰着させるのが定石である。

解法1

(1)

$m$ を0以上の整数とする。$\boxed{3^m}$ が $3^m$ で割り切れ、$3^{m+1}$ では割り切れないこと、すなわち

$$ \boxed{3^m} = 3^m \cdot M \quad (M \text{ は3で割り切れない整数}) \quad \cdots (*) $$

と表せることを、$m$ についての数学的帰納法で示す。

(i)

$m=0$ のとき

$\boxed{3^0} = \boxed{1} = 1$ であり、$1 = 3^0 \cdot 1$ と表せる。$M=1$ は3で割り切れないため、$(*)$ は成り立つ。

(ii)

$m=k$ ($k$ は0以上の整数) のとき、$(*)$ が成り立つと仮定する。

すなわち、$\boxed{3^k} = 3^k \cdot M$ （$M$ は3で割り切れない整数）と表せるとする。 $m=k+1$ のときを考えると、

$$ \boxed{3^{k+1}} = \frac{10^{3^{k+1}}-1}{9} = \frac{(10^{3^k})^3-1}{9} $$

ここで、$X = 10^{3^k}$ とおくと、

$$ \boxed{3^{k+1}} = \frac{X^3-1}{9} = \frac{X-1}{9}(X^2+X+1) = \boxed{3^k}(X^2+X+1) $$

と因数分解できる。帰納法の仮定より、$\boxed{3^k} = 3^k \cdot M$ であり、$X = 9 \cdot \boxed{3^k} + 1 = 9 \cdot 3^k \cdot M + 1 = 3^{k+2}M + 1$ と表せる。これを用いて $X^2+X+1$ を計算すると、

$$ \begin{aligned} X^2+X+1 &= (3^{k+2}M+1)^2 + (3^{k+2}M+1) + 1 \\ &= 3^{2k+4}M^2 + 2 \cdot 3^{k+2}M + 1 + 3^{k+2}M + 1 + 1 \\ &= 3^{2k+4}M^2 + 3 \cdot 3^{k+2}M + 3 \\ &= 3(3^{2k+3}M^2 + 3^{k+2}M + 1) \end{aligned} $$

ここで、$N = 3^{2k+3}M^2 + 3^{k+2}M + 1$ とおくと、$N$ は整数であり、$N \equiv 1 \pmod 3$ であるから、$N$ は3で割り切れない。したがって、

$$ \boxed{3^{k+1}} = 3^k \cdot M \cdot 3N = 3^{k+1} \cdot MN $$

となり、$MN$ も3で割り切れない整数である。よって、$m=k+1$ のときも $(*)$ は成り立つ。

（i）, （ii）より、すべての0以上の整数 $m$ について、$\boxed{3^m}$ は $3^m$ で割り切れるが、$3^{m+1}$ では割り切れないことが示された。

(2)

自然数 $n$ は、整数 $q \ge 0$ と $0 \le r < 27$ を満たす整数 $r$ を用いて、$n = 27q + r$ と一意に表せる。このとき、

$$ \begin{aligned} \boxed{n} &= \frac{10^{27q+r}-1}{9} \\ &= \frac{10^r(10^{27q}-1) + 10^r - 1}{9} \\ &= 10^r \cdot \frac{10^{27q}-1}{9} + \frac{10^r-1}{9} \\ &= 10^r \cdot \boxed{27q} + \boxed{r} \end{aligned} $$

（ただし、$r=0$ のときは $\boxed{0} = 0$ と定義しておく）ここで、

$$ \boxed{27q} = \frac{10^{27q}-1}{9} = \frac{(10^{27})^q-1}{9} = \frac{10^{27}-1}{9} \left\{ (10^{27})^{q-1} + (10^{27})^{q-2} + \cdots + 1 \right\} $$

であるから、$\boxed{27q}$ は $\boxed{27}$ の倍数である。（1）の結果において $m=3$ とすると、$\boxed{3^3} = \boxed{27}$ は $3^3 = 27$ で割り切れる。ゆえに、$\boxed{27}$ は27の倍数であり、したがって $\boxed{27q}$ も27の倍数である。よって、

$$ \boxed{n} \equiv \boxed{r} \pmod{27} $$

となり、$\boxed{n}$ が27で割り切れることと、$\boxed{r}$ が27で割り切れることは同値である。

次に、$0 \le r < 27$ において、$\boxed{r}$ が27で割り切れるような $r$ を求める。 $\boxed{r}$ が27で割り切れるならば、$\boxed{r}$ は9で割り切れる。 $\boxed{r}$ は1が $r$ 個並んだ整数であるから、各位の数の和は $r$ であり、これが9の倍数になる必要がある。 $0 \le r < 27$ より、$r$ は $0, 9, 18$ のいずれかである。

(ア)

$r=0$ のとき

$\boxed{0} = 0$ は27で割り切れる。

(イ)

$r=9$ のとき

（1）の結果において $m=2$ とすると、$\boxed{3^2} = \boxed{9}$ は $3^2=9$ で割り切れるが、$3^3=27$ では割り切れない。よって、27の倍数ではない。

(ウ)

$r=18$ のとき

$$ \boxed{18} = \frac{10^{18}-1}{9} = \frac{(10^9-1)(10^9+1)}{9} = \boxed{9}(10^9+1) $$

ここで、$10 \equiv 1 \pmod 3$ より、$10^9+1 \equiv 1^9+1 = 2 \pmod 3$ であるから、$10^9+1$ は3の倍数ではない。また、（イ）より $\boxed{9}$ は9で割り切れるが27では割り切れないため、$\boxed{9} = 9 \cdot K$ （$K$ は3の倍数でない整数）と表せる。ゆえに、$\boxed{18} = 9 \cdot K(10^9+1)$ となり、$K(10^9+1)$ は3で割り切れないため、$\boxed{18}$ は27で割り切れない。

以上より、$\boxed{r}$ が27で割り切れるための必要十分条件は $r=0$ である。 $r=0$ であることは、$n$ が27で割り切れることと同値であるため、$n$ が27で割り切れることが、$\boxed{n}$ が27で割り切れるための必要十分条件であることが示された。