【整数問題】a_1=4 , a_(n+1)=a_n^2+n(n+2)のとき、a_2022 , a_2023 , a_2024 の最大公約数を求めよ。（2022・東京大学・文科）

数列${a_n}$を次のように定める。

$$a_1=4 , a_{n+1}=a_n^2+n(n+2)　(n=1,2,3,\cdots)$$

（１）　$a_{2022}$ を３で割った余りを求めよ。

（２）　$a_{2022} , a_{2023} , a_{2024}$ の最大公約数を求めよ。

$$a_1=4$$

$$a_2=4^2+2\cdot4=24$$

$$a_3=24^2+3\cdot5=584$$

これ以上は大きくなってしまって、計算が大変そうです。

「３で割ったあまり（mod3）」に注目して考えます。

$$a_1\equiv4\equiv1\pmod3$$

$$\color{blue}{a_2\equiv1^2+2\cdot4\equiv9\equiv0\pmod3}$$

$$a_3\equiv0^2+3\cdot5\equiv15\equiv0\pmod3$$

$$a_4\equiv0^2+4\cdot6\equiv24\equiv0\pmod3$$

$$a_5\equiv0^2+5\cdot7\equiv35\equiv2\pmod3$$

$$a_6\equiv2^2+6\cdot8\equiv52\equiv1\pmod3$$

$$a_7\equiv1^2+7\cdot9\equiv64\equiv1\pmod3$$

$$\color{blue}{a_8\equiv1^2+8\cdot10\equiv81\equiv0\pmod3}$$

$$\cdot$$

$a_2$と$a_8$の仕組みが「$1^2$+（3の倍数以外の積） 」で同じことに気づくと

この後同様に繰り返すと予想できます。

つまり

と予想します。

を数学的帰納法を使って示す

（i）（ii）より　

$$\begin{eqnarray} \begin{cases} a_{6k+1}\equiv 1\pmod3 \\ a_{6k+2}\equiv 0\pmod3 \\a_{6k+3}\equiv0\pmod3\\a_{6k+4}\equiv0\pmod3\\a_{6k+5}\equiv2\pmod3\\a_{6k+6}\equiv1\pmod3 \end{cases} \end{eqnarray}$$

したがって

$$a_{2022}\equiv a_{6\cdot337}\equiv1\pmod3$$

$a_{2022} , a_{2023} , a_{2024}$ の最大公約数をdとする

$$a_{n+1}=a_n^2+n(n+2)$$

を変形して

$$a_{n+1}-a_n^2=n(n+2)$$

$n=2023 , 2022$ を代入して

$$a_{2024}-a_{2023}^2=2023\cdot2025・・・①$$

$$a_{2023}-a_{2022}^2=2022\cdot2024・・・②$$

①②ともに左辺は、dを因数にもつ（dで割り切れる）

また、①②の右辺を考えて

$$\begin{array}{ccc} ①・・・2023\cdot2025&=&(7\cdot17^2)(3^4\cdot5^2)&=&\color{red}{3}^4\cdot5^2\cdot7\cdot17^2 \\ ②・・・2022\cdot2024&=&(2\cdot3\cdot337)(2^3\cdot11\cdot23)&=&2^4\cdot\color{red}{3}\cdot11\cdot23\cdot337 \end{array}$$

①②の共通の素因数は「３」のみである。

したがって、dの候補は「１」か「３」となる

（１）より $a_{2022}$ は「３」で割り切れないことから

$$d=1$$