東京大学 2014年度理系数学第5問解答・解説

問題

$r$ を0以上の整数とし，数列 ${a_{n}}$ を次のように定める。

a_{1} = r, a_{2} = r + 1, a_{n + 2} = a_{n + 1} (a_{n} + 1) (n = 1, 2, 3, \dots)

また，素数 $p$ を1つとり， $a_{n}$ を $p$ で割った余りを $b_{n}$ とする。ただし，0を $p$ で割った余りは0とする。

(1) 自然数 $n$ に対し， $b_{n + 2}$ は $b_{n + 1} (b_{n} + 1)$ を $p$ で割った余りと一致することを示せ。

(2) $r = 2$ ， $p = 17$ の場合に，10以下のすべての自然数 $n$ に対して， $b_{n}$ を求めよ。

(3) ある2つの相異なる自然数 $n$ ， $m$ に対して，

b_{n + 1} = b_{m + 1} > 0, b_{n + 2} = b_{m + 2}

が成り立ったとする。このとき， $b_{n} = b_{m}$ が成り立つことを示せ。

(4) $a_{2}, a_{3}, a_{4}, \dots$ に $p$ で割り切れる数が現れないとする。このとき， $a_{1}$ も $p$ で割り切れないことを示せ。

出典：東京大学 2014年度前期日程第2次学力試験理系第5問

方針

(1) から (3) は文科第4問と同じく、余りだけで漸化式を追い、非零の共通余りを素数 $p$ のもとで割り戻す。(4) は背理法を用いる。もし $a_{1}$ が $p$ で割り切れるなら $b_{1} = 0$ 、一方で仮定から $b_{k} > 0$ が $k ≧ 2$ で成り立つ。有限個しかない正の余りの隣接ペア $(b_{k}, b_{k + 1})$ を考えると同じペアが現れるので、(3) を1つずつ過去へ戻して $b_{1}$ が後の正の余りに等しいという矛盾を導く。

解答

(1)

$b_{n}$ は $a_{n}$ を $p$ で割った余りであるから $a_{n} \equiv b_{n} (mod p), a_{n + 1} \equiv b_{n + 1} (mod p)$ である。したがって $a_{n} + 1 \equiv b_{n} + 1 (mod p)$ であり、積をとって $a_{n + 1} (a_{n} + 1) \equiv b_{n + 1} (b_{n} + 1) (mod p)$ を得る。

漸化式より $a_{n + 2} = a_{n + 1} (a_{n} + 1)$ であるから、 $a_{n + 2}$ を $p$ で割った余り $b_{n + 2}$ は、 $b_{n + 1} (b_{n} + 1)$ を $p$ で割った余りと一致する。

(2)

$r = 2$ より $b_{1} = 2, b_{2} = 3$ である。(1) を用いて順に計算する。 $b_{3} \equiv 3 (2 + 1) = 9 (mod 17)$ より $b_{3} = 9$ である。 $b_{4} \equiv 9 (3 + 1) = 36 \equiv 2 (mod 17)$ より $b_{4} = 2$ である。 $b_{5} \equiv 2 (9 + 1) = 20 \equiv 3 (mod 17)$ より $b_{5} = 3$ である。

ここで $(b_{4}, b_{5}) = (2, 3) = (b_{1}, b_{2})$ となったので、以後は同じ計算が繰り返される。したがって

n b_{n} 122339425369728399102

である。

(3)

$b_{n + 1} = b_{m + 1} > 0, b_{n + 2} = b_{m + 2}$ とする。 $c = b_{n + 1} = b_{m + 1}$ とおくと、 $c$ は $p$ で割った余りであり、 $0 < c < p$ である。

(1) より $b_{n + 2} \equiv c (b_{n} + 1) (mod p)$ であり、同様に $b_{m + 2} \equiv c (b_{m} + 1) (mod p)$ である。 $b_{n + 2} = b_{m + 2}$ だから $c (b_{n} + 1) \equiv c (b_{m} + 1) (mod p)$ すなわち $c (b_{n} - b_{m}) \equiv 0 (mod p)$ である。 $p$ は素数で、 $0 < c < p$ だから $c$ は $p$ で割り切れない。よって $b_{n} - b_{m} \equiv 0 (mod p)$ である。 $b_{n}, b_{m}$ はどちらも $0$ 以上 $p - 1$ 以下なので $b_{n} = b_{m}$ である。

(4)

背理法で示す。 $a_{1}$ が $p$ で割り切れると仮定する。このとき $b_{1} = 0$ である。一方、問題の仮定より $a_{2}, a_{3}, a_{4}, \dots$ には $p$ で割り切れる数が現れないので $b_{k} > 0 (k ≧ 2)$ である。 $k ≧ 2$ について、隣接する2つの余りの組 $(b_{k}, b_{k + 1})$ を考える。各成分は $1, 2, \dots, p - 1$ のいずれかであるから、このような組は高々 $(p - 1)^{2}$ 通りしかない。したがって無限に続く組 $(b_{2}, b_{3}), (b_{3}, b_{4}), (b_{4}, b_{5}), \dots$ の中には、同じ組が2回現れる。すなわち、ある $2 ≦ n < m$ が存在して $b_{n} = b_{m}, b_{n + 1} = b_{m + 1}$ となる。

ここで $b_{n} = b_{m} > 0$ かつ $b_{n + 1} = b_{m + 1}$ であるから、(3) を添字 $n - 1, m - 1$ に適用すると $b_{n - 1} = b_{m - 1}$ が従う。さらに $b_{n - 1} > 0$ であれば、同じ議論を1つ前の添字に繰り返せる。 $n ≧ 2$ なので、この操作を順に行うと $b_{1} = b_{m - n + 1}$ を得る。

ところが $m - n + 1 ≧ 2$ であるから、仮定より $b_{m - n + 1} > 0$ である。一方、最初に仮定した通り $b_{1} = 0$ である。これは矛盾である。

したがって $a_{1}$ は $p$ で割り切れない。すなわち $a_{1} も p で割り切れない$ である。

東京大学 2014年度理系数学 第5問

問題

方針

解答

(1)

(2)

(3)

(4)

東京大学 2014年度
理系数学第5問