https://spherical-harmonics.hateblo.jp/entry/Todai/2014/Rika

問題：2014年(平成26年)東京大学前期-数学(理科) - [別館]球面倶楽部零八式markIISR

2022.03.08記
漸化式で定まる整数に値をとる数列の余りは途中から周期をもつが，特に漸化式をうまく逆に辿ることができるなら，その周期は初項から始まる。

$\mbox{mod}\,p$ で
$b_{n+2}\equiv a_{n+2}=a_{n+1}(a_n+1)\equiv b_{n+1}(b_n+1)$ となることは普通に使う訳だが，それを示せという問題．

[解答]

(1) 漸化式から $a_n$ は正の整数をとる数列であることが帰納的に言えるので，任意の正の整数 $n$ に対して
$a_n=p\cdot q_n + b_n$ （ $0\leqq b_n\lt p$ ）をみたす正または0の整数をとる数列 $q_n$ が一意に定まる．

このとき，漸化式より
$p\cdot q_{n+2} + b_{n+2}=(p\cdot q_{n+1} + b_{n+1})(p\cdot q_n + b_n+1)$
つまり
$b_{n+2}-b_{n+1}(b_n+1)$ $=p\cdot (p q_nq_{n+1}+b_n q_{n+1}+b_{n+1}q_n+q_{n+1}-q_{n+2})$
が成立するので，登場する文字が全て整数であることに注意すると
$b_{n+2}-b_{n+1}(b_n+1)$
は $p$ の倍数となり，よって $b_{n+2}$ と $b_{n+1}(b_n+1)$ を $p$ で割った余りは等しい．

(2) $(b_n,b_{n+1})=(b_m,b_{m+1})$ なる最小の自然数の組 $n,m$ （ $n\lt m$ ）が存在すると，(1) により $b_{n+2}=b_{m+2}$ が成立するので帰納的に，任意の自然数 $k$ について $b_{n+k}=b_{m+k}$ が成立することになるので，数列 $b_n$ は第 $n$ 項以降は周期 $m-n$ で繰り返す数列になる．

$r=2,p=17$ のとき， $b_1=2$ ， $b_2=3$ ， $b_3=9$ ， $b_4=36-2\cdot 17=2=b_1$ であるから，数列 $b_n$ は第 $1$ 項以降は周期 $3$ で繰り返す数列になる．

よって， $b_1=b_4=b_7=b_{10}=2$ ， $b_2=b_5=b_8=3$ ， $b_3=b_6=b_9=9$ となる．

(3) $p$ で割った余りが等しいことを「 $\equiv$ 」で結ぶこととする．

$(b_{n+2},b_{n+1})=(b_{m+2},b_{m+1})$ （ $b_{n+1}=b_{m+1}\gt 0$ ）なる自然数の組 $n,m$ （ $n\lt m$ ）が存在するとき，
$0=b_{n+2}-b_{m+2}$ $\equiv b_{n+1}(b_n+1)-b_{m+1}(b_m+1)$ $=b_{n+1}(b_n-b_m)$
となるが， $b_{n+1}\neq 0$ ， $0\leqq b_n,b_m\lt p-1$ より $b_n=b_m$ となる．

(4) $(b_{n+2},b_{n+1})$ の組み合わせは高々 $p^2$ 通りであるから，ディリクレの部屋割り論法により
$(b_3,b_2)$ から $(b_{p^2+3},b_{p^2+2})$ までの $p^2+1$ 組の中には
$(b_{n+2},b_{n+1})=(b_{m+2},b_{m+1})$ （ $1\lt n\lt m$ ）
なる自然数の組 $n,m$ が存在する．そして題意から $2$ 以上の全ての自然数 $k$ に対して $b_k\neq 0$ だから，
$(b_{n+2},b_{n+1})=(b_{m+2},b_{m+1})$ （ $1\lt n\lt m$ ）
において(3)を $n$ 回繰り返すと
$(b_{2},b_{1})=(b_{m-n+2},b_{m-n+1})$ （ $1\lt n\lt m$ ）
が成立する．ここで $m-n+1\geqq 2$ により $b_{m-n+1}\neq 0$ であるから， $b_1\neq 0$ が言え，よって $a_1$ も $p$ では割り切れない．