[math]2022年東京大学理系前期数学問題2

Table of Contents

問題

数列$a_n$を次のように定める。$$a_1 = 1, a_{n+1}={a_n}^2+1\ \ \ (n=1, 2, 3, \cdots)$$
$(1)$ 正の整数$n$が$3$の倍数のとき、$a_n$は$5$の倍数となることを示せ。
$(2)$ $k, n$を正の整数とする。$a_n$が$a_k$の倍数となるための必要十分条件を$k, n$を用いて表わせ。
$(3)$ $a_{2022}$と$(a_{8091})^2$の最大公約数を求めよ。

方針

合同式を用いるのが記述が簡単でよいだろう。

解答

$(1)$ 以下$\pmod{5}$で考える。$$\begin{eqnarray}a_1 & \equiv & 1\\ a_2 & = & {a_1}^2+1& \\& \equiv & 2 \\ a_3 & = & {a_2}^2+1 \\ & \equiv & 0 \\ a_4 & = & {a_3}^2+1 \\& \equiv & 1 \\ a_5 & = & {a_4}^2+1\\& \equiv & 2 \\ \cdots\end{eqnarray}$$となり以下繰り返すから、$n$が$3$の倍数のとき$a_n$は$5$で割り切れる。

$(2)$ 以下$\pmod{a_k}$で考える。$$\begin{eqnarray}a_{k+1} & = & {a_k}^2+1\\& \equiv & 1\\ a_{k+2} & = & {a_{k+1}}^2+1 \\& \equiv & 2 \\ a_{k+3} & = & {a_{k+2}}^2+1\\ & \equiv & 5 \\ a_{k+4} & = & {a_{k+3}}^2+1 \\& \equiv & 26 \\ \cdots\end{eqnarray}$$であるから、$1\leq l \leq k$とすると、$a_{k+l} \equiv a_{l} \ \pmod{a_k}$である（厳密には数学的帰納法で示すが簡単である）。$a_n$は増加数列であるから、$a_1< a_2 < \cdots a_l< \cdots < a_k$である。したがって、$a_{k+l}$が$a_k$で割り切れるのは、$a_l = a_k$のときに限る。この議論から、$n$が$k$の倍数のとき、$a_n$は$a_k$の倍数となる。逆に、$n = kl+r\ \ (0<r<k)$とすると、$a_{n}$を$a_k$で割った余りは$a_r$となり、$0$にならない。よって求める必要十分条件は$\underline{n \equiv 0\pmod{k}}$である。

$(3)$ $8091 = 2022\times 4 + 3$であるから、$(2)$の議論から${a_{8091}}$を$a_{2022}$で割った余りは$a_3 = 5$となる。したがって、${a_{8091}}^2$を$a_{2022}$で割った余りは$5^2 = 25$である。Euclidの互除法から、${a_{8091}}^2$と$a_{2022}$の最大公約数は、$a_{2022}$と$25$の最大公約数と等しい。$2022 \equiv 0\pmod{3}$だから、$(1)$より$a_{2022}$は$5$で割り切れる。以後$\pmod{25}$で考えると、$$\begin{eqnarray}a_1 & = & 1\\ a_2 & = & {a_1}^2+1\\ & \equiv & 2\\ a_3 & = & {a_2}^2+1\\ & \equiv & 5 \\ a_4 & = & {a_3}^2+1\\ & \equiv & 1\\ \cdots\end{eqnarray}$$となり、$1, 2, 5$を繰り返す。つまり、$a_n$が$25$で割り切れることはない。以上から、$a_{2022}$と${a_{8091}}^2$の最大公約数は$\underline{5}$である。

解説

$(1)$で様子を掴む。

$(2)$ 苦戦した受験生も多かったかもしれない。手を動かして実験すると、$a_k$で割った余りを考えたとき、$a_{k+1}$の余りは$a_1$、$a_{k+2}$の余りは$a_2$、$\cdots$となることがわかる。実験、といっても$a_n$は急速に大きくなるのでなかなか難しいが。ちなみに、コンピュータで計算すると$a_{10} =3791862310265926082868235028027893277370233152247388584761734150717768254410341175325352026$となる。

$(3)$ $a_{8091}$でなく、$a_{8091}$の二乗なので、$5^2 = 25$が$a_{2022}$の約数でないことに言及する必要がある。その事自体は難しくないが、抜け落ちてしまったものも多かったことだろう。

題材はありふれているが、ピリッとくる良問題である