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

今回、整数問題（2022・東京大学・文科）の解説をします。

この記事を読むと

整数問題（2022・東京大学・文科）の解法
合同式を利用した解法
整数問題の「数学的帰納法」の利用方法
最大公約数の利用方法

について理解できます。

この記事は「わか」が執筆しています。

私「わか」（https://twitter.com/wakkachan2019）は、国立大学数学科を卒業後、数学教育に10年以上関わっています。

問題：整数問題（2022・東京大学・文科）
解説：整数問題（2022・東京大学・文科）
補足
まとめ：整数問題（2022・東京大学・文科）

問題：整数問題（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}$ の最大公約数を求めよ。

解説：整数問題（2022・東京大学・文科）

実験（とりあえず$a_1,a_2,a_3$を求める）

実験

$$a_1=4$$

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

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

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

実験（$a_n\pmod3$を具体的に求める）

実験

「３で割ったあまり（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の倍数以外の積）」で同じことに気づくと

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

つまり

３で割ったあまりは　１、０、０、０、２、１　の繰り返し

と予想します。

（１）解答：数学的帰納法利用

（１）解答

$k=0,1,2,3\cdots$ として

\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}

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

（i）$k=0$ のとき

$$a_1\equiv4\equiv1\pmod3$$

$$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$$

よって成立する

（ii）$k=s$ のとき成立すると仮定する

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

$k=s+1$ のとき

\begin{array}{ccc} a_{6(s+1)+1}&\equiv& a_{6s+7}&\equiv& a_{6s+6}^2+(6s+7)(6s+9)&\equiv&1^2+1\cdot0&\equiv&1\pmod3 \\a_{6(s+1)+2}&\equiv& a_{6s+8}&\equiv& a_{6s+7}^2+(6s+8)(6s+10)&\equiv&1^2+2\cdot1&\equiv&0\pmod3 \\a_{6(s+1)+3}&\equiv& a_{6s+9}&\equiv& a_{6s+8}^2+(6s+9)(6s+11)&\equiv&0^2+0\cdot2&\equiv&0\pmod3 \\a_{6(s+1)+4}&\equiv& a_{6s+10}&\equiv& a_{6s+9}^2+(6s+10)(6s+12)&\equiv&0^2+1\cdot0&\equiv&0\pmod3 \\a_{6(s+1)+5}&\equiv& a_{6s+11}&\equiv& a_{6s+10}^2+(6s+11)(6s+13)&\equiv&0^2+2\cdot1&\equiv&2\pmod3 \\a_{6(s+1)+6}&\equiv& a_{6s+12}&\equiv& a_{6s+11}^2+(6s+12)(6s+14)&\equiv&2^2+0\cdot2&\equiv&1\pmod3 \end{array}

よって成立する

（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$$