トップ› 東京大学› 2014年› 文系第4問

東京大学 2014年文系第4問解説

方針・初手

(1) は合同式の性質をそのまま用いることで容易に示せる。$a_n \equiv b_n \pmod p$ を利用して、漸化式の両辺の法 $p$ における合同を考える。

(2) は (1) で示した性質 $b_{n+2} \equiv b_{n+1}(b_n+1) \pmod{17}$ を用いて具体的に書き出し、計算していく。途中で同じ項の並びが現れれば、以降は周期的に繰り返されることを利用して計算を短縮する。

(3) は $b_{n+2}$ と $b_{m+2}$ をそれぞれ $b_n, b_{n+1}$ および $b_m, b_{m+1}$ で表し、与えられた等式と合同式を用いて $b_n \equiv b_m \pmod p$ を導く。$p$ が素数であることと $b_{n+1} > 0$ の条件が、合同式において両辺を $b_{n+1}$ で割るための鍵となる。

解法1

(1)

定義より、$a_n$ を $p$ で割った余りが $b_n$ であるから、任意の自然数 $n$ に対して以下が成り立つ。

$$ a_n \equiv b_n \pmod p $$

与えられた漸化式 $a_{n+2} = a_{n+1}(a_n + 1)$ の両辺について法 $p$ での合同式を考えると、合同式の性質より次が成り立つ。

$$ a_{n+2} \equiv a_{n+1}(a_n + 1) \equiv b_{n+1}(b_n + 1) \pmod p $$

一方で、$a_{n+2}$ を $p$ で割った余りが $b_{n+2}$ であるため、

$$ a_{n+2} \equiv b_{n+2} \pmod p $$

であり、かつ $0 \leqq b_{n+2} < p$ を満たす。したがって、$b_{n+2}$ は $b_{n+1}(b_n + 1)$ を $p$ で割った余りと一致する。（証明終）

(2)

$r=2$, $p=17$ のとき、(1) の結果より $b_{n+2}$ は $b_{n+1}(b_n + 1)$ を $17$ で割った余りである。条件より $a_1 = 2$, $a_2 = 3$ であるから、これらは $17$ 未満でありそのまま余りとなる。

$$ b_1 = 2 $$

$$ b_2 = 3 $$

これらを用いて順次計算する。

$$ b_3 \equiv b_2(b_1 + 1) = 3 \times 3 = 9 \pmod{17} $$

よって $b_3 = 9$ である。

$$ b_4 \equiv b_3(b_2 + 1) = 9 \times 4 = 36 \equiv 2 \pmod{17} $$

よって $b_4 = 2$ である。

$$ b_5 \equiv b_4(b_3 + 1) = 2 \times 10 = 20 \equiv 3 \pmod{17} $$

よって $b_5 = 3$ である。

ここで $b_4 = b_1 = 2$ かつ $b_5 = b_2 = 3$ となった。$b_{n+2}$ の値は直前の2項 $b_{n+1}, b_n$ の値のみによって決定されるため、連続する2項が初期値と一致したことで、これ以降の数列 $\{b_n\}$ は周期 $3$ で同じ値を繰り返すことがわかる。

すなわち、任意の自然数 $k$ に対して以下が成り立つ。

$$ b_{3k-2} = 2 $$

$$ b_{3k-1} = 3 $$

$$ b_{3k} = 9 $$

これを用いて $n=6, 7, 8, 9, 10$ のときの値を求めると、 $b_6 = 9$, $b_7 = 2$, $b_8 = 3$, $b_9 = 9$, $b_{10} = 2$ となる。

(3)

条件より $b_{n+1} = b_{m+1} > 0$ かつ $b_{n+2} = b_{m+2}$ が成り立つとする。 (1) の結果より、法 $p$ において次が成り立つ。

$$ b_{n+2} \equiv b_{n+1}(b_n + 1) \pmod p $$

$$ b_{m+2} \equiv b_{m+1}(b_m + 1) \pmod p $$

条件 $b_{n+2} = b_{m+2}$ より、

$$ b_{n+1}(b_n + 1) \equiv b_{m+1}(b_m + 1) \pmod p $$

ここで $b_{n+1} = b_{m+1}$ であるから、この値を $k$ とおく。条件 $b_{n+1} > 0$ および $b_{n+1}$ が $p$ で割った余りであることから、$0 < k < p$ である。上の合同式に代入すると、

$$ k(b_n + 1) \equiv k(b_m + 1) \pmod p $$

移項して整理すると、

$$ k(b_n - b_m) \equiv 0 \pmod p $$

$p$ は素数であり、$0 < k < p$ であるから、$k$ は $p$ の倍数ではない。すなわち、$k$ と $p$ は互いに素である。したがって、合同式の性質から両辺を $k$ で割ることができ、次が得られる。

$$ b_n - b_m \equiv 0 \pmod p $$

ここで、$b_n, b_m$ はともに $p$ で割った余りであるから、$0 \leqq b_n < p$ かつ $0 \leqq b_m < p$ を満たす。この不等式から、差 $b_n - b_m$ のとりうる範囲は、

$$ -p < b_n - b_m < p $$

となる。この範囲にある $p$ の倍数は $0$ のみであるから、

$$ b_n - b_m = 0 $$

よって、$b_n = b_m$ が成り立つ。（証明終）

解説

合同式を用いた整数問題の典型的な構成である。(1) で合同式の基本的な演算規則（和と積の合同）を確認し、(2) で具体的に書き出すことで周期性を発見させる。(3) は「素数 $p$ を法とする合同式において、$p$ と互いに素な数での除法が許される」という重要な性質を問うている。$b_{n+1} > 0$ という条件が、割る数 $b_{n+1}$ と素数 $p$ が互いに素であることを保証するために決定的に働いている点に注意したい。