東京大学 2014 文系第4問 (総合問題)

問題

$r$ を0以上の整数とし、数列 $\{a_n\}$ を次のように定める。

$a_1=r$
$a_2=r+1$
$a_{n+2}=a_{n+1}(a_n+1)$ $(n=1, 2, 3, ...)$

また、素数 $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$ が成り立つことを示せ。

解答(1)

$a_n$ を $p$ で割った商を $c_n$ とおくと、
$a_n=pc_n+b_n$ 　(ただし $0≦{b_n}<{p}$ )
$\begin{eqnarray}a_{n+2}&=&a_{n+1}(a_n+1)\\&=&(pc_{n+1}+b_{n+1})(pc_n+b_n+1)\\&=&p\{pc_{n+1}c_n+b_{n+1}c_n+(b_n+1)c_{n+1}\}+b_{n+1}(b_n+1)\end{eqnarray}$

ここで、 $b_{n+1}(b_n+1)$ を $p$ で割ったときの余りを $x_n$ , 商を $y_n$ とすると ( $0≦{x_n}<{p}$ )、

$b_{n+1}(b_n+1)=py_n+x_n$

この式を使うと、
$a_{n+2}=p\{pc_{n+1}c_n+b_{n+1}c_n+(b_n+1)c_{n+1}+y_n\}+x_n$

また、 $a_{n+2}=pc_{n+2}+b_{n+2}$ で,
$0≦{b_{n+2}}<{p}$ , $0≦{x_n}<{p}$ であるから、
$b_{n+2}=x_n$

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

解答(2)

(問題再掲)(2) $r=2$ , $p=17$ の場合に、10以下のすべての自然数 $n$ に対して、 $b_n$ を求めよ。

問題(1)の結果を利用して解く

$b_1$ は、 $a_1=2$ を17で割った余りだから、 $b_1=2$
$b_2$ は、 $a_2=3$ を17で割った余りだから、 $b_2=3$
問題(1)の結果より、 $b_3$ は $b_2(b_1+1)=9$ を17で割った余りになるから、 $b_3=9$
同様にして、 $b_4$ は $b_3(b_2+1)=36$ を17で割った余りになるから、 $b_4=2$
$b_5$ は $b_4(b_3+1)=20$ を17で割った余りになるから、 $b_5=3$
以下、同じ計算となり、
$b_6=9$ , $b_7=2$
$b_8=3$ , $b_9=9$
$b_10=2$

解答(3)

(問題再掲)(3)ある2つの相異なる自然数 $n, m$ に対して、
$b_{n+1}=b_{m+1}>0$
$b_{n+2}=b_{m+2}$
が成り立ったとする。このとき、 $b_n=b_m$ が成り立つことを示せ。

問題(1)が誘導になっている

問題(1)の結果より、
$b_{n+2}$ は、 $b_{n+1}(b_n+1)$ を $p$ で割った余りに等しく、
$b_{m+2}$ は、 $b_{m+1}(b_m+1)$ を $p$ で割った余りに等しい。

また、題より、 $b_{n+2}=b_{m+2}$ なので、
$b_{n+1}(b_n+1)$ を $p$ で割った余りと、 $b_{m+1}(b_m+1)$ を $p$ で割った余りは等しい。
言い換えると、 $b_{n+1}(b_n+1)$ と $b_{m+1}(b_m+1)$ の差は $p$ の倍数になるとわかります。

題より、 $b_{n+1}=b_{m+1}$ なので、
$b_{n+1}(b_n+1)$ と $b_{n+1}(b_m+1)$ の差は $p$ の倍数になります。
後は式にするだけです。