東京大学 理系数学 2022年 第2問 解説

今回は、東京大学理系数学（2022年 第2問）の解説をしたいと思います。

問題

　数列 $\{a_n\}$ を次のように定める。
$$a_1=1,a_{n+1}=a_n^2+1\text{（}n=1,2,3,\cdots \cdots \text{）}$$

⑴　正の整数 $n$ が $3$ の倍数のとき，$a_n$ は $5$ の倍数となることを示せ。

⑵　$k,n$ を正の整数とする。$a_n$ が $a_k$ の倍数となるための必要十分条件を $k,n$ を用いて表せ。

⑶　$a_{2022}$ と $(a_{8091}{)}^2$ の最大公約数を求めよ。

（東京大学）

解答

⑴

$n=3m$（ $m$ は正の整数）のとき、$a_n$ が $5$ の倍数となることを数学的帰納法により示す。

(ⅰ)　$m=1$（ $n=3$ のとき）
$$\begin{array}{rcl}{a}_2& =& a_1^2+1=1^2+1=2\\ a_3& =& a_2^2+1=2^2+1=5\end{array}$$より、$a_3$ は $5$ の倍数なので成り立つ。

(ⅱ)　$m=i$（ $i$ は正の整数）のとき成り立つ、すなわち
$$a_{3i}\equiv 0(\mathrm{mod}5)$$であると仮定すると、
$$\begin{array}{rcl}{a}_{3i+1}& =& a_{3i}^2+1\equiv 0^2+1=1(\mathrm{mod}5)\\ a_{3i+2}& =& a_{3i+1}^2+1\equiv 1^2+1=2(\mathrm{mod}5)\\ a_{3i+3}& =& a_{3i+2}^2+1\equiv 2^2+1\equiv 0(\mathrm{mod}5)\end{array}$$より、$m=i+1$ のときも成り立つ。

(ⅰ),(ⅱ)より、すべての正の整数 $m$ について成り立つので、$n$ が $3$ の倍数のとき、$a_n$ は $5$ の倍数となる。$$\begin{array}{}\text{(証明終)}& \end{array}$$

⑵

$\ell$ を正の整数として、$a_{n+\ell }\equiv a_{\ell }(\mathrm{mod}{a}_n)\cdots \text{①}$ を数学的帰納法により示す。

(ⅰ)　$\ell =1$ のとき
$$a_{n+1}=a_n^2+1\equiv 1=a_1(\mathrm{mod}{a}_n)$$より成り立つ。

(ⅱ)　$\ell =i$（ $i$ は正の整数）のとき成り立つ、すなわち
$$a_{n+i}\equiv a_i(\mathrm{mod}{a}_n)$$であると仮定すると、$\ell =i+1$ のとき
$$a_{n+i+1}=a_{n+i}^2+1\equiv a_i^2+1=a_{i+1}(\mathrm{mod}{a}_n)$$より成り立つ。

(ⅰ),(ⅱ)より、すべての正の整数 $\ell$ について①が成り立つ。

よって、任意の正の整数 $k,m$ に対して①を繰り返し用いると
$$a_{mk}\equiv a_{(m-1)k}\equiv a_{(m-2)k}\equiv \cdots \equiv a_k\equiv 0(\mathrm{mod}{a}_k)$$となるから、$n$ が $k$ の倍数のとき、$a_n$ は $a_k$ の倍数となる。

一方、$n$ が $k$ の倍数でないとき、$n$ を $k$ で割った余りを $r$（ $r=1,2,\cdots ,k-1$ ）とおくと、①を繰り返し用いることで
$$a_n\equiv a_{n-k}\equiv a_{n-2k}\equiv \cdots \equiv a_r(\mathrm{mod}{a}_k)$$となる。ここで、漸化式より数列 $\{a_n\}$ は明らかに増加数列であるから、$1\leqq r<k$ ならば $a_1(=1)\leqq a_r<a_k$ となり、$a_r$ が $a_k$ の倍数になることはない。よって、$n$ が $k$ の倍数でないとき、$a_n$ は $a_k$ の倍数でない。

したがって、$a_n$ が $a_k$ の倍数となるための必要十分条件は、$\mathit{n}$ が $\mathit{k}$ の倍数である。

⑶

$8088$ は $2022$ の倍数（ $8088=2022\times 4$ ）なので、⑵より
$$a_{8088}\equiv 0(\mathrm{mod}{a}_{2022})$$

よって
$$\begin{array}{rcl}{a}_{8089}& =& (a_{8088}{)}^2+1\equiv 0^2+1=1(\mathrm{mod}{a}_{2022})\\ a_{8090}& =& (a_{8089}{)}^2+1\equiv 1^2+1=2(\mathrm{mod}{a}_{2022})\\ a_{8091}& =& (a_{8090}{)}^2+1\equiv 2^2+1=5(\mathrm{mod}{a}_{2022})\end{array}$$

したがって
$$(a_{8091}{)}^2\equiv 5^2=25(\mathrm{mod}{a}_{2022})$$より、$a_{2022}$ と $(a_{8091}{)}^2$ の最大公約数は $a_{2022}$ と $25$ の最大公約数である。

ここで、$2022$ は $3$ の倍数なので、⑴より $a_{2022}$ は $5$ の倍数である。

一方、
$$\begin{array}{rcl}{a}_1& =& 1\equiv 1(\mathrm{mod}25)\\ a_2& =& 2\equiv 2(\mathrm{mod}25)\\ a_3& =& 5\equiv 5(\mathrm{mod}25)\\ a_4& =& 5^2+1=26\equiv 1(\mathrm{mod}25)\end{array}$$より、$a_n$ を $25$ で割った余りは $1,2,5,1,2,5,\cdots$ と循環するので、$a_n$ が $25$ で割り切れることはない。

以上から、$a_{2022}$ は $5$ の倍数であるが $25$ の倍数でないので、$a_{2022}$ と $(a_{8091}{)}^2$ の最大公約数は $\mathbf{5}$ である。

解説

この問題は、「 $a_n$ を特定の値で割ると余りが循環する」という性質に気づくことが重要です。

イメージが湧きづらいという人は、具体的な例で考えてみましょう。
$a_4=26$ なので、$a_n$ を $26$ で割った余りは $1,2,5,0,1,2,5,0,\cdots$ と循環します。これは $\mathrm{mod}$ の計算の性質から直ちに分かります。

つまり、数列 $\{a_n\}$ の項の中で $26$ の倍数（＝ $26$ で割った余りが $0$ ）であるものは第 $4m$ 項（ $m$ は正の整数）に現れることが分かります。そしてそれ以外の項を $26$ で割った余りは $1$ 以上 $26$ 未満（この例では $1,2,5$ ）なので、$26$ の倍数にはなりえないのです。これを厳密に書くと⑵の解答のようになります。

文字を使った抽象的な議論が苦手な人は、具体的な数字を代入してみて、その式が何を表現しようとしているのかイメージをつかむ練習を重ねてみましょう。

⑶は最大公約数に関する問題なので、「ユークリッドの互除法の原理」を使いましょう。

求める値が「 $a_{2022}$ と $25$ の最大公約数」だと分かれば、今度は $\mathrm{mod}25$ で考えるのがカギです。$a_4=26$ を $25$ で割った余りが $1$ となって $a_1$ と同じ値になる（つまり余りが循環する）のがこの問題の上手いところです。

まとめ

今回は、東京大学理系数学（2022年 第2問）の解説をしました。