問題#Ⅰ017 ★★★☆
$r$を$0$以上の整数とし、数列$\{a_n\}$を次のように定める。
$a_1=r$、$a_2=r+1$、$a_{n+2}=a_{n+1}(a_{n}+1) \ (n=1,2,3,\cdots)$
また、素数$p$を$1$つとり、$a_n$を$p$で割った余りを$b_n$とする。ただし、$0$を$p$で割った余りは$0$とする。
（１）自然数$n$に対し、$b_{n+2}$は$b_{n+1}(b_{n}+1)$を$p$で割った余りと一致することを示せ。
（２）$r=2$、$p=17$の場合に、$10$以下のすべての自然数$n$に対して、$b_n$を求めよ。
（３）ある$2$つの相異なる自然数$n$、$m$に対して、
$b_{n+1}=b_{m+1}>0$、$b_{n+2}=b_{m+2}$
が成り立ったとする。このとき、$b_n=b_m$ が成り立つことを示せ。
（４）$a_2$、$a_3$、$a_4$、$\cdots$ に$p$で割り切れる数が現れないとする。このとき、$a_1$も$p$で割り切れないことを示せ。
《ポイント》
抽象的な問題ですが誘導が丁寧なので上手く乗りたいところ。（３）が本問のポイントとなる設問です。（４）では「鳩ノ巣論法」を利用しましょう。なお（４）は対偶を証明しても良いのですが、結局は（３）を利用する方が効率的です。
《解答例》
（１）
$a_n$を$p$で割ったときの商を$c_n$と置くと、$$\begin{cases} a_{n}=p c_{n}+b_{n}\\ a_{n+1}=p c_{n+1}+b_{n+1} \\ a_{n+2}=p c_{n+2}+b_{n+2} \end{cases}$$となるから、$$\begin{align} &\ \ \ \ \ a_{n+2} \\ &= a_{n+1}(a_{n}+1) \\ &=(p c_{n+1}+b_{n+1})(p c_{n}+b_{n}+1) \\ &=p \{c_{n} (p c_{n+1}+b_{n+1})+c_{n+1}(b_{n}+1)\}+b_{n+1}(b_{n}+1) \end{align}$$と表せる。これより$a_{n+2}$を$p$で割った余り$b_{n+2}$は$b_{n+1}(b_{n}+1)$を$p$で割った余りに一致する。
□
（２）
$b_1=2$、$b_2=3$、$b_3=9$、$b_4=2$、$b_5=3$ となるから、（１）より$b_n$は $2,\,3,\,9$ と繰り返すことが分かる。故に$m$を正の整数として$$\begin{cases} b_{3m-2}=2 \\ b_{3m-1}=3 \\ b_{3m}=9 \end{cases}$$と求められる。よって$$\begin{cases} b_{n}=2 (n=1,\,4,\,7,\,10)\\ b_{n}=3 (n=2,\,5,\,8)\\ b_{n}=9 (n=3,\,6,\,9) \end{cases}$$となる。
（３）
（１）より、$b_{n+2}$は$b_{n+1}(b_{n}+1)$を$p$で割った余りに一致するから、商を$d_n$とすると$$b_{n+1}(b_{n}+1)=p d_n + b_{n+2}$$が成り立つ。$b_{m+2}$についても同様に商を$d_m$とすると$$b_{m+1}(b_{m}+1)=p d_m + b_{m+2}$$が成り立つ。ここで $b_{n+1}=b_{m+1}$ かつ $b_{n+2}=b_{m+2}$ より、辺々の差をとると$$b_{n+1}(b_{n}-b_{m})=p(d_n-d_m)$$を得る。右辺は$p$の倍数であるから左辺も$p$の倍数でなければならないが、$0<b_{n+1}<p$ より $b_{n}-b_{m}$ が$p$の倍数であることが必要となる。$-p<b_{n}-b_{m}<p$ より、$$b_{n}-b_{m}=0$$ $$\therefore b_{n}=b_{m}$$が成り立つ。
□
（４）
仮定より、$a_2$、$a_3$、$a_4$、$\cdots$ には$p$で割り切れる数が現れないから、余り$b_2$、$b_3$、$b_4$、$\cdots$ はいずれも$0$でない。
よって$(b_{n},\,b_{n+1})$の組み合わせとしてあり得るのは $0<b_{n}<p$、$0<b_{n+1}<p$ より、高々$(p-1)^2$通り以下であるから、数列$\{b_n\}$を十分先まで考えれば$$(b_{i+1},\,b_{i+2})=(b_{j+1},\,b_{j+2})$$となるような整数$i$、$j$が存在する（ただし $0<i<j$ を満たす）。したがって（３）より、$$b_{i}=b_{j}$$が成り立つ。これより帰納的に$$b_{1}=b_{j-i+1}$$が成り立つが、$j-i+1$ は$2$以上の整数であるから仮定より $b_{j-i+1}>0$ である。故に $b_{1} \ne 0$ となるから$a_1$は$p$で割り切れない。
□
《コメント》
前問に続き抽象的な問題でしたね。（４）ではいわゆる「鳩ノ巣論法」が必要になるので、発想できたかどうかが点数の大きな分かれ目になったことと思います。「数列$\{b_n\}$を十分先まで考え」るというのは、例えば $k>p^2$ とすると$k$個の組$(b_{n},\,b_{n+1})$のうちどれか2組は一致するものが存在する、ということを言うためです。これが「鳩ノ巣論法」や「引き出し論法」などと呼ばれる考え方です。
（出典：東京大学 2014年）