トップ› 大阪大学› 1993年› 理系第1問

大阪大学 1993年理系第1問解説

方針・初手

漸化式によって定まる数列の各項の性質を調べる問題である。 (1)は偶奇に着目し、隣り合う2項の偶奇の推移を調べる。(2)は9を法とする合同式を利用し、整数の3乗を9で割った余りが限られた値になる性質を利用する。(3)は18が2と9の積であることから、(1)と(2)の結果を組み合わせて、「2の倍数かつ9の倍数」であることを示す。

解法1

(1)

与えられた漸化式 $x_{n+1} = x_n^3 + 1$ について、$x_n$ の偶奇に応じて $x_{n+1}$ の偶奇を調べる。

$x_n$ が偶数のとき、$x_n^3$ は偶数であるから、$x_n^3 + 1$ は奇数となる。よって $x_{n+1}$ は奇数である。

$x_n$ が奇数のとき、$x_n^3$ は奇数であるから、$x_n^3 + 1$ は偶数となる。よって $x_{n+1}$ は偶数である。

したがって、任意の負でない整数 $n$ に対して、$x_n$ と $x_{n+1}$ の一方は偶数であり、もう一方は奇数である。ゆえに、積 $x_n x_{n+1}$ は常に偶数となり、2で割り切れる。以上より、$0 \leqq n \leqq 2$ に対しても $x_n x_{n+1}$ は2で割り切れることが示された。

(2)

任意の整数 $k$ を用いて、$x_0$ を3で割った余りで分類する。

(i)

$x_0 = 3k$ のとき

$$ x_0^3 = 27k^3 = 9(3k^3) $$

よって、$x_0^3 \equiv 0 \pmod 9$ である。

(ii)

$x_0 = 3k+1$ のとき

$$ x_0^3 = (3k+1)^3 = 27k^3 + 27k^2 + 9k + 1 = 9(3k^3 + 3k^2 + k) + 1 $$

よって、$x_0^3 \equiv 1 \pmod 9$ である。

(iii)

$x_0 = 3k-1$ のとき

$$ x_0^3 = (3k-1)^3 = 27k^3 - 27k^2 + 9k - 1 = 9(3k^3 - 3k^2 + k) - 1 $$

よって、$x_0^3 \equiv -1 \equiv 8 \pmod 9$ である。

以上のことから、任意の整数 $x_0$ に対して、$x_0^3$ を9で割った余りは $0, 1, 8$ のいずれかである。 $x_1 = x_0^3 + 1$ であるから、$x_1$ を9で割った余りは、それぞれに1を加えて $1, 2, 9$（すなわち $0$）となる。したがって、$x_1$ を9で割った余りは $0, 1, 2$ のいずれかである。

(3)

$x_1 x_2 x_3$ が18で割り切れること、すなわち2の倍数かつ9の倍数であることを示す。

まず、(1)の結果から、$n=1$ のとき $x_1 x_2$ は2で割り切れる。したがって、その倍数である $x_1 x_2 x_3$ も2で割り切れる。

次に、9の倍数であることを示す。 (2)の結果より、$x_1$ を9で割った余りは $0, 1, 2$ のいずれかであるから、合同式を用いて法を9として場合分けを行う。

(ア)

$x_1 \equiv 0 \pmod 9$ のとき

$x_1$ が9の倍数であるから、積 $x_1 x_2 x_3$ は9の倍数である。

(イ)

$x_1 \equiv 1 \pmod 9$ のとき

漸化式より以下が成り立つ。

$$ x_2 = x_1^3 + 1 \equiv 1^3 + 1 = 2 \pmod 9 $$

$$ x_3 = x_2^3 + 1 \equiv 2^3 + 1 = 9 \equiv 0 \pmod 9 $$

したがって、$x_3$ が9の倍数となるため、積 $x_1 x_2 x_3$ は9の倍数である。

(ウ)

$x_1 \equiv 2 \pmod 9$ のとき

漸化式より以下が成り立つ。

$$ x_2 = x_1^3 + 1 \equiv 2^3 + 1 = 9 \equiv 0 \pmod 9 $$

したがって、$x_2$ が9の倍数となるため、積 $x_1 x_2 x_3$ は9の倍数である。

(ア)〜(ウ)のいずれの場合においても、$x_1 x_2 x_3$ は9で割り切れる。

以上より、$x_1 x_2 x_3$ は2で割り切れ、かつ9でも割り切れる。 2と9は互いに素であるから、$x_1 x_2 x_3$ はそれらの積である18で割り切れる。

解説

整数問題における典型的な「偶奇の議論」と「剰余の議論」を組み合わせた標準的な問題である。 (1)では、累乗を含んだ漸化式においても、項の偶奇が交互に入れ替わることを確認する。 (2)では、「3乗数を9で割った余りは $0, 1, 8$ に限られる」という有名な性質を利用している。この証明では、元の数を3を法として分類するのが最も手際がよい。 (3)では、大きな数を法とする整除性を示すために、互いに素な数の積に分解し（$18 = 2 \times 9$）、それぞれの倍数であることを示す定石を用いている。前の設問が強力な誘導になっていることを意識して解き進めることが重要である。