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

(1) 定義から $a_n\equiv b_n\pmod p$ である。したがって漸化式より $$a_{n+2}=a_{n+1}(a_n+1)\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_1=2,\quad b_2=3,\quad b_3=3(2+1)=9,\quad b_4\equiv9(3+1)=36\equiv2\pmod{17},$$ $$b_5\equiv2(9+1)=20\equiv3,\quad b_6\equiv3(2+1)=9,\quad b_7\equiv9(3+1)=2,$$ $$b_8\equiv2(9+1)=3,\quad b_9\equiv3(2+1)=9,\quad b_{10}\equiv9(3+1)=2\pmod{17}.$$ よって $(b_1,b_2,\ldots,b_{10})=(2,3,9,2,3,9,2,3,9,2)$ である。

(3) $c=b_{n+1}=b_{m+1}>0$ とおく。小問(1)より $$b_{n+2}\equiv c(b_n+1),\qquad b_{m+2}\equiv c(b_m+1)\pmod p.$$ 仮定 $b_{n+2}=b_{m+2}$ と合わせて $c(b_n-b_m)\equiv0\pmod p$ を得る。$c$ は $1\leq c\leq p-1$ だから，素数 $p$ とは互いに素であり，$b_n\equiv b_m\pmod p$ である。両者は $0$ 以上 $p-1$ 以下の剰余なので $b_n=b_m$ となる。

(4) 仮に $p\mid a_1$ とすると $b_1=0$ である。背理法の仮定より $b_k>0$ はすべての $k\geq2$ で成り立つ。数列 $(b_n,b_{n+1})$（$n\geq2$）の各成分は $1,2,\ldots,p-1$ のいずれかであり，このような組は高々 $(p-1)^2$ 個である。一方，組は無限に続くので，ある $2\leq n<m$ について $$(b_n,b_{n+1})=(b_m,b_{m+1})$$ となる。小問(3)を添字 $n-1,m-1$ に適用すると $b_{n-1}=b_{m-1}$ である。同じように添字を一つずつ下げて適用できる。各適用時に必要な $b_{k+1}>0$ は，その添字 $k+1\geq2$ について背理法の仮定から成り立つ。したがって最終的に $$b_1=b_{m-n+1}$$ を得る。ここで $m-n+1\geq2$ なので右辺は正であるが，左辺は $0$ で矛盾する。よって $p\nmid a_1$ である。