2次漸化式に関する整数問題（2022年東京大学理系数学第2問）

解答例

 

（１）

以下、合同式の法を$\bmod 5$ とする。$$a_1 \equiv \underline{1}$$ $$a_2 \equiv 1^2+1=2$$ $$a_3 \equiv 2^2+1 \equiv 0$$ $$a_4 \equiv 0^2+1 \equiv \underline{1}$$ $$\quad \vdots$$以上より、数列$\{a_n\}$を$5$で割った余りは周期$3$で循環する。これより、$a_n \equiv 0\pmod 5$ となるのは$n$が$3$の倍数のときであり、またそのときに限る。よって示された。

□

 

 

（２）

正の整数$N$について $a_{N} \equiv 0 \pmod{a_{k}}$ が成り立つとすると、
$$\begin{aligned} a_{N+1} & \equiv 0+1 \pmod{a_{k}} \\ &=1\left(=a_{1}\right) \\ a_{N+2} & \equiv 1^{2}+1 \pmod{a_{k}} \\ &=2\left(=a_{2}\right) \\ a_{N+3} & \equiv 2^{2}+1 \pmod{a_{k}} \\ &=5\left(=a_{3}\right) \\ & \quad \vdots \end{aligned}$$となる。よって与漸化式を逐次用いることにより、$j\ (\leqq k)$ を正の整数として$$a_{N+j} \equiv a_j \pmod{a_{k}} \quad \cdots ①$$が導かれる。

 

ここで、$a_{j} \equiv 0 \pmod{a_{k}}$ となるのは $j=k$ の場合であること、および、$n$を$1$から増加させていったときに$a_n$が初めて$a_k$で割り切れるのが $n=k$ の時点であることに注意すると、$①$式より$n$が$k$の倍数であるとき常に$$a_{n} \equiv 0 \pmod{a_{k}}$$が成り立つ。

 

逆に、$a_{n} \equiv 0 \pmod{a_{k}}$ が成り立つ（$a_{n}$が$a_{k}$の倍数となる）とき、$n=qk+r$（$q,r \in \mathbb Z$, $0 < r \leqq k$）と置けば、$①$式において $N \to qk$、$j \to r$ と置き換えることにより$$(a_{n}=)\ a_{qk+r} \equiv a_{r} \equiv 0 \pmod{a_{k}} \quad \cdots ②$$を得る。$②$式を満たすような$r$は $0 < r \leqq k$ の範囲で $r=k$ のみであるが、これは$n$が$k$の倍数となることを意味する。

 

以上より、$a_{n}$が$a_{k}$の倍数となるための必要十分条件は、「$n$が$k$の倍数であること」である。

□

 

 

（３）

まず（２）の結論から、$a_{8088}$が$a_{2022}$で割り切れることが従う。これより、$$\begin{aligned} a_{8089} &=a_{8088}^{2}+1 \\ &\equiv 1 \pmod{a_{2022}} \\ a_{8090} &\equiv 1^{2}+1 \pmod{a_{2022}} \\ &= 2 \\ a_{8091} & \equiv 2^{2}+1 \pmod{a_{2022}} \\ &=5 \end{aligned}$$となるので、$$\left(a_{8091}\right)^{2} \equiv 25 \pmod{a_{2022}}$$を得る。これより、$a_{2022}$と$\left(a_{8091}\right)^{2}$の最大公約数は $25$、$5$、$1$ のいずれかに限られる。

 

ここで$2022$と$8091$がともに$3$の倍数であることに注目すると、（１）より $a_{2022}$と$a_{8091}$はともに$5$の倍数でなる。

 

また、$$\begin{aligned} a_{1} & \equiv \underline{1} \pmod{25} \\ a_{2} & \equiv 2 \pmod{25} \\ a_{3} & \equiv 5 \pmod{25} \\ a_{4} & \equiv 5^2+1 \equiv \underline{1} \pmod{25} \\ & \quad \vdots \end{aligned}$$となるから、数列$\{a_n\}$を$25$で割った余りは周期$3$で循環し、どの項も$25$で割り切れることはない。よって$a_{2022}$は$5$の倍数ではあるが$25$の倍数でないので、求める$a_{2022}$と$\left(a_{8091}\right)^{2}$の最大公約数は$$\color{red}{5}$$である。