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

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

方針・初手

数列をある数で割った余りに関する問題である。(1) は合同式の性質をそのまま用いる。(2) は(1)の漸化式に従って具体的に計算し、周期性を見つける。(3) は余りの性質と素数 $p$ であることを利用して、1つ前の項が等しいことを示す。(4) はとり得る余りの組が有限であることから生じる周期性（または繰り返し）と、(3)の「前へ戻れる」性質（逆推移性）を組み合わせた背理法による典型的な証明である。

解法1

(1)

整数 $x, y$ に対し、$x \equiv y \pmod p$ で $x$ と $y$ を $p$ で割った余りが等しいことを表す。

$b_n$ は $a_n$ を $p$ で割った余りであるから、すべての自然数 $n$ について

$$ a_n \equiv b_n \pmod p $$

が成り立つ。

与えられた漸化式 $a_{n+2} = a_{n+1}(a_n + 1)$ において、両辺を $p$ を法とする合同式で考えると、

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

となる。

$b_{n+2}$ は $a_{n+2}$ を $p$ で割った余りであるため、$b_{n+2}$ と $b_{n+1}(b_n + 1)$ を $p$ で割った余りは一致する。

(2)

$r=2, p=17$ とする。

(1) の結果より、$b_{n+2} \equiv b_{n+1}(b_n + 1) \pmod{17}$ であり、$0 \leqq b_n \leqq 16$ である。

$a_1 = 2, a_2 = 3$ であるから、

$$ b_1 = 2, \quad b_2 = 3 $$

である。順次 $b_n$ を計算すると、

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

より $b_3 = 9$。

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

より $b_4 = 2$。

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

より $b_5 = 3$。

ここで $(b_4, b_5) = (2, 3) = (b_1, b_2)$ となる。

漸化式 $b_{n+2} \equiv b_{n+1}(b_n + 1) \pmod{17}$ より、隣り合う2項が決定すれば次の項も一意に定まるため、数列 $\{b_n\}$ は周期 $3$ で同じ値を繰り返す。

すなわち、$b_n = 2, 3, 9, 2, 3, 9, \cdots$ となる。

よって、$10$ 以下の自然数 $n$ に対する $b_n$ は、

$n=1, 4, 7, 10$ のとき $b_n = 2$

$n=2, 5, 8$ のとき $b_n = 3$

$n=3, 6, 9$ のとき $b_n = 9$

(3)

条件より $b_{n+1} = b_{m+1} > 0$ かつ $b_{n+2} = b_{m+2}$ である。

(1) の結果より、$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+1}(b_n + 1) \equiv b_{m+1}(b_m + 1) \pmod p $$

が成り立つ。

ここで $b_{n+1} = b_{m+1}$ であり、これを $C$ とおく。条件より $C > 0$ であり、$C$ は $p$ で割った余りであるから $C < p$ である。

したがって、$p$ は素数であるから、$C$ と $p$ は互いに素である。

先の合同式は

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

と書け、式を変形すると

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

となる。

$C$ と $p$ は互いに素であるから、$b_n - b_m$ は $p$ の倍数である。

すなわち

$$ b_n \equiv b_m \pmod p $$

が成り立つ。

$b_n, b_m$ はいずれも $p$ で割った余りであるため、$0 \leqq b_n < p$ かつ $0 \leqq b_m < p$ を満たす。

この範囲で差が $p$ の倍数となるのは $b_n - b_m = 0$ の場合に限られる。

よって、$b_n = b_m$ が成り立つ。

(4)

背理法を用いて証明する。

$a_2, a_3, a_4, \cdots$ に $p$ で割り切れる数が現れない、すなわち $n \geqq 2$ において $b_n > 0$ であると仮定する。

このもとで、$a_1$ が $p$ で割り切れる、すなわち $b_1 = 0$ と仮定して矛盾を導く。

数列 $\{b_n\}$ の各項は $0$ 以上 $p-1$ 以下の整数であるから、隣り合う2項の組 $(b_n, b_{n+1})$ は高々 $p^2$ 通りしか存在しない。

数列は無限に続くため、部屋割り論法（鳩の巣原理）により、ある相異なる自然数 $n, m$ ($n < m$) が存在して、

$$ (b_n, b_{n+1}) = (b_m, b_{m+1}) $$

が成り立つ。

このような等しい組が存在するような最小の自然数 $n$ を $N$ とする。

もし $N \geqq 2$ であるとすると、$n \geqq 2$ において $b_n > 0$ であるという前提から $b_N > 0$ である。

ここで、

$$ b_N = b_m > 0, \quad b_{N+1} = b_{m+1} $$

が成り立っている。これは (3) の条件において $n, m$ をそれぞれ $N-1, m-1$ と置き換えた

$$ b_{(N-1)+1} = b_{(m-1)+1} > 0, \quad b_{(N-1)+2} = b_{(m-1)+2} $$

に他ならない。

(3) の結果より、$b_{N-1} = b_{m-1}$ が導かれる。

すると、$(b_{N-1}, b_N) = (b_{m-1}, b_m)$ となり、$N$ よりも小さなインデックスで等しい組が存在することになり、$N$ の最小性に矛盾する。

したがって、$N = 1$ でなければならない。

$N = 1$ のとき、ある $m > 1$ (すなわち $m \geqq 2$) に対して

$$ (b_1, b_2) = (b_m, b_{m+1}) $$

が成り立つ。

これより $b_1 = b_m$ となるが、仮定より $b_1 = 0$ であるため、$b_m = 0$ となる。

しかし、$m \geqq 2$ のとき $b_m > 0$ であるという前提に矛盾する。

ゆえに、最初の仮定が誤りであり、$a_1$ も $p$ で割り切れないことが示された。

解説

整数を法とした余りの数列（剰余列）の周期性をテーマにした典型的な問題である。(1)(2)で剰余の漸化式とその周期性を具体的に確認させ、(3)で「一つ前の項が一致する」という逆向きの推移性を証明させる。そして(4)で「取りうる値の組が有限」であることから必ず周期を持つこと（部屋割り論法）と、(3)の逆推移性を組み合わせて背理法に持ち込む、非常に美しい構成となっている。(3)で $C$ と $p$ が互いに素であるという条件が効いてくるため、$p$ が素数であることの確認を忘れないようにしたい。