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

問題編

問題

 r を $0$ 以上の整数とし、数列 $\{ a_n \}$ を次のように定める。\[ a_1=r, \quad a_2=r+1, \quad a_{n+2}=a_{n+1}(a_n+1) \quad (n=1,2,3,\cdots) \]また、素数 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} \gt 0, \quad b_{n+2}=b_{m+2} \]が成り立ったとする。このとき、 $b_n=b_m$ が成り立つことを示せ。
(4) $a_2, a_3, a_4, \cdots$ に p で割り切れる数が現れないとする。このとき、 $a_1$ も p で割り切れないことを示せ。

【広告】

考え方

見かけはごつい感じがしますが、整数問題にしては易しいです。

(1)は与えられた式をそのまま変形するか、差が p の倍数になることを示します。(2)は計算するだけです。(3)も、差が p の倍数になることを示します。

(4)は(3)を使うことは予想できますが、(3)の前提を満たすものをどうやって見つけるかが言いにくいです。余りの組を考え、数は無限個なのに種類は有限個であることに注目しましょう。