2022年東大理科第2問 - 数式で独楽する

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

小問(1)の解答例
小問(2)の解答例
小問(3)の解答例
解説

小問(1)の解答例

\begin{eqnarray}
a_2 &=& 2 \\
a_3 &=& 5
\end{eqnarray}です。
漸化式により、 $a_n$ を5で割った余りは1, 2, 0です。
$a_n, \ a_{n +1}$ の余りを分類すると、次のようになります。
\begin{array}{c|ccc}
\hline
a_n & 1 & 2 & 0 \\ \hline
a_{n +1} & 2 & 0 & 1 \\ \hline
\end{array}
つまり、 $a_n$ が5の倍数のとき、 $a_{n +3}$ も5の倍数となります。
また、 $a_3$ は5の倍数です。

したがって、 $n$ が3の倍数のとき、 $a_n$ は5の倍数となります。(証明終わり)

小問(2)の解答例

$a_n$ を $a_k$ で割った余りで分類します。表の第1行が余りです。
\begin{array}{ccccc}
\hline
a_1 & a_2 & \cdots & a_{k -1} & 0 \\ \hline
a_1 & a_2 & \cdots & a_{k -1} & a_k \\
a_{k +1} & a_{k +2} & \cdots & a_{2k -1} & a_{2k} \\
\vdots & \vdots && \vdots & \vdots \\
a_{(m -1)k +1} & a_{(m -1)k +2} & \cdots & a_{mk -1} & a_{mk} \\
a_{mk +1} & a_{mk +2} & \cdots & a_{(m +1)k -1} & a_{(m +1)k} \\
\vdots & \vdots && \vdots & \vdots \\ \hline
\end{array}
これより、 $a_n$ が $a_k$ の倍数となる必要十分条件は、

$n$ が $k$ の倍数

となります。

小問(3)の解答例

素因数分解は
\begin{eqnarray}
2022 &=& 2 \times 3 \times 337 \\
8091 &=& 3^2 \times 29 \times 31
\end{eqnarray}です。
両者は1, 3以外の公約数を持ちません。
したがって、小問(2)の結果から、 $a_{2022}, \ a_{8091}$ は
\begin{eqnarray}
a_1 &=& 1 \\
a_3 &=& 5
\end{eqnarray}以外の公約数を持ちません。
次に、 $a_{2022}$ が $5^2 = 25$ を約数に持つか否かを評価します。
$a_1, \ a_2, \ a_3, \ a_4, \ a_5, \ a_6, \ \cdots$ を25で割った余りは次のようになります。
\begin{array}{c|c}
\hline
a_1 & 1 \\
a_2 & 2 \\
a_3 & 5 \\
a_4 & 1 \\
a_5 & 2 \\
a_6 & 5 \\
\vdots & \vdots \\ \hline
\end{array}余りは1, 2, 5を繰り返すことになります。
したがって $a_{2022}$ は25を約数に持たないことが分かります。