【整数問題】a_1=1 , a_n+1=a_n^2+1のとき a_2022と(a_8091)^2の最大公約数を求めよ（2022・東京大学・理科）

$$a_1=1$$

$$a_2=1^2+1=2$$

$$a_3=2^2+1=5$$

$$a_4=4^2+1=26$$

$$a_5=26^2+1=677$$

$$a_6=677^2+1=458300$$

5の倍数であることを示すので mod5 を考える

$$a_1\equiv1\pmod5$$

$$a_2\equiv1^2+1\equiv2\pmod5$$

$$a_3\equiv2^2+1\equiv5\equiv0\pmod5$$

$$a_4\equiv0^2+1\equiv1\pmod5$$

$$a_5\equiv1^2+1\equiv2\pmod5$$

$$a_6\equiv2^2+1\equiv5\equiv0\pmod5$$

\begin{array}{|c|c|c|} \hline n & 1 & 2&3&4&5&6&\cdots \\ \hline a_n\pmod5 &1&2&0&1&2&0&\cdots \\ \hline \end{array}

\(a_n\) は、５で割ったあまりが 1,2,0 と繰り返すので

nが３の倍数のとき、\(a_n\) は５の倍数

数列\({a_n}\) は単調増加であり \(a_1=1\) より

最初に\(a_n\) が \(a_k\) の倍数となるのは \(n=k\) のとき

次に \(a_n\) が \(a_k\) の倍数となるときを考える

\(mod{a_k}\) を考えて

$$a_{k+1}\equiv a_{k}^2+1\equiv0^2+1\equiv1\pmod{a_k}$$

$$a_{k+2}\equiv a_{k+1}^2+1\equiv1^2+1\equiv2\pmod{a_k}$$

$$a_{k+3}\equiv a_{k+2}^2+1\equiv2^2+1\equiv5\pmod{a_k}$$

\(\cdots\)

\begin{array}{|c|c|c|} \hline n & 1 & 2&3&\cdots&k-1&k&k+1&k+2&k+3&\cdots&k+k=2k&2k+1&2k+2&\cdots \\\hline a_n &1&2&5&\cdots&a_{k-1}&a_k&a_{k+1}&a_{k+2}&a_{k+3}&\cdots&a_{k+k}=a_{2k}&a_{2k+1}&a_{2k+2}&\cdots\\ \hline a_n\pmod{a_k} &1&2&5&\cdots&a_{k-1}&0&1&2&5&\cdots&a_k\equiv0&1&2&\cdots \\ \hline \end{array}

\(a_n\) は \(a_k\) で割ったあまりが

\(\underbrace{1,2,5,\cdots ,a_{k-1},0}_{k個},\underbrace{1,2,5\cdots,0}_{k個},\cdots\) と繰り返す

したがって

「\(a_n\) が \(a_k\) の倍数」となるための必要十分条件は「 n は k の倍数」

（２）より

$$a_{8088}\equiv a_{2022\times4}\equiv 0\pmod {a_{2022}}$$

$$a_{8089}\equiv a_{8088}^2+1\equiv 1\pmod {a_{2022}}$$

$$a_{8090}\equiv a_{8089}^2+1\equiv 2\pmod {a_{2022}}$$

$$a_{8091}\equiv a_{8090}^2+1\equiv 5\pmod {a_{2022}}$$

\((a_{8091})^2\equiv25\pmod{a_{2022}}\)

$$(a_{8091})^2=a_{2022}\times X+25 (X:整数)$$

\((a_{8091})^2\) と \(a_{2022}\) の最大公約数は

\(a_{2022}\) と 25 の最大公約数と一致する

\(a_{2022}\) と 25 の最大公約数は　５

したがって

\((a_{8091})^2\) と \(a_{2022}\) の最大公約数は　５