東京大学 理系 2022年度 第2問 解説
問題編
問題
数列 $\{a_n\}$ を次のように定める。\[ a_1=1,\ a_{n+1}=a_n^2+1 \quad (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$ の最大公約数を求めよ。
考え方
余りに着目すると循環することがわかるので、それを利用していきます。
(3)は2乗がついていなければすぐに答えはわかります。2乗がついているので少し考えないといけないところが出てきますが、(2)までにやったことをよく見返せば思いつくでしょう。
解答編
問題
数列 $\{a_n\}$ を次のように定める。\[ a_1=1,\ a_{n+1}=a_n^2+1 \quad (n=1,2,3,\cdots) \]
(1) 正の整数 $n$ が $3$ の倍数のとき、 $a_n$ は $5$ の倍数となることを示せ。
解答
2つの整数 $a,b$ の差が正の整数 $p$ で割り切れることを\[ a \equiv b \pmod p \]と表すことにする。
(1)
正の整数 $m$ に対し、 $a_{3m}$ が $5$ の倍数であることを示す。
(i) $m=1$ のとき
$a_2 \equiv 1^2+1 \equiv 2 \pmod 5$
$a_3 \equiv 2^2+1 \equiv 0 \pmod 5$
より成り立つ。
(ii) $m=k$ のとき（$k$ は正の整数）、 $a_{3k}$ が $5$ の倍数とすると
$a_{3k+1} \equiv 0^2+1 \equiv 1 \pmod 5$
$a_{3k+2} \equiv 1^2+1 \equiv 2 \pmod 5$
$a_{3k+3} \equiv 2^2+1 \equiv 0 \pmod 5$
より、 $m=k+1$ のときも成り立つ。
(i)(ii)より、正の整数 $n$ が $3$ の倍数のときに $a_n$ が $5$ の倍数になることが示せた。（終）
解答編 つづき
問題
(2) $k,n$ を正の整数とする。 $a_n$ が $a_k$ の倍数となるための必要十分条件を $k,n$ を用いて表せ。
解答
(2)
漸化式より $a_n$ は正だとわかる。よって、漸化式より、 $a_n\lt a_{n+1}$ となることがわかるため、 $n\lt k$ ならば $a_n\lt a_k$ となる。そのため、このときは $a_n$ が $a_k$ の倍数になることはない。
次に、正の整数 $m$ に対し、 $a_{k+m} \equiv a_m \pmod {a_k}$ が成り立つことを示す。
(i) $m=1$ のとき
$a_{k+1} \equiv a_k^2+1 \equiv 1 \equiv a_1 \pmod {a_k}$
より成り立つ。
(ii) $m=\ell$ のとき（$\ell$ は正の整数）、 $a_{k+\ell} \equiv a_{\ell} \pmod {a_k}$ が成り立つとすると
$a_{k+\ell+1} \equiv a_{k+\ell}^2+1 \equiv a_{\ell}^2+1 \pmod {a_k}$
$a_{\ell+1} \equiv a_{\ell}^2+1 \pmod {a_k}$
より、 $m=\ell+1$ のときも成り立つ。
(i)(ii)より、正の整数 $m$ に対し、 $a_{k+m} \equiv a_m \pmod {a_k}$ が成り立つことが示せた。
$n\lt k$ のときは $a_n$ は $a_k$ の倍数にはならないので、上で示したことから、 $n$ が $k$ の倍数でないときは、 $a_n$ は $a_k$ の倍数にはならない。一方、上で示したことから、\[ a_{k\ell} \equiv a_k \equiv 0 \pmod {a_k} \]なので、 $n$ が $k$ の倍数であるときは、 $a_n$ は $a_k$ の倍数である。
以上より、 $a_n$ が $a_k$ の倍数となるための必要十分条件は、「 $n$ が $k$ の倍数であること」である。（答）
解答編 つづき
問題
(3) $a_{2022}$ と $(a_{8091})^2$ の最大公約数を求めよ。
解答
(3)
$\mod {a_{2022} }$ で考えると、(2)より $a_{8088}\equiv 0$ だから
\begin{eqnarray}
a_{8089} &\equiv& 0^2+1 \equiv 1 \\[5pt]
a_{8090} &\equiv& 1^2+1 \equiv 2 \\[5pt]
a_{8091} &\equiv& 2^2+1 \equiv 5 \\[5pt]
(a_{8091})^2 &\equiv& 5^2 \equiv 25 \\[5pt]
\end{eqnarray}なので、 $a_{2022}$ と $(a_{8091})^2$ の最大公約数は $a_{2022}$ と $25$ の最大公約数に等しい。
(1)より $a_{2022}$ は $5$ の倍数であることがわかる。一方、 $\mod {25}$ で考えると
\begin{eqnarray}
a_1 & \equiv & 1 \\[5pt]
a_2 & \equiv & 1^2+1 \equiv 2 \\[5pt]
a_3 & \equiv & 2^2+1 \equiv 5 \\[5pt]
a_4 & \equiv & 5^2+1 \equiv 1 \\[5pt]
\end{eqnarray}となることから、 $a_n$ を $25$ で割った余りは $1,2,5,1,2,5,\cdots$ と循環するため、 $25$ で割り切れることはない。よって、 $a_{2022}$ は $25$ で割り切れない。
以上から、 $a_{2022}$ と $(a_{8091})^2$ の最大公約数は $5$ （答）
