東京大学 理系数学 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{eqnarray}
a_2 &=& a_1^{\,2}+1=1^2+1=2 \\
a_3 &=& a_2^{\,2}+1=2^2+1=5
\end{eqnarray}$$より、$a_3$ は $5$ の倍数なので成り立つ。

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

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

⑵

$\ell$ を正の整数として、$a_{n+\ell} \equiv a_\ell \pmod {a_n}\quad\cdots\text{①}$ を数学的帰納法により示す。

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

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

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

よって、任意の正の整数 $k,m$ に対して①を繰り返し用いると
$$a_{mk} \equiv a_{(m-1)k} \equiv a_{(m-2)k} \equiv \cdots \equiv a_k \equiv 0 \pmod{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} \pmod{a_k}$$となる。ここで、漸化式より数列 $\{a_n\}$ は明らかに増加数列であるから、$1\leqq r \lt k$ ならば $a_1(=1) \leqq a_r \lt a_k$ となり、$a_r$ が $a_k$ の倍数になることはない。よって、$n$ が $k$ の倍数でないとき、$a_n$ は $a_k$ の倍数でない。

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

⑶

$8088$ は $2022$ の倍数（ $8088=2022\times 4$ ）なので、⑵より
$$a_{8088} \equiv 0 \pmod{a_{2022}}$$

よって
$$\begin{eqnarray}
a_{8089} &=& (a_{8088})^2+1 \equiv 0^2+1 = 1 \pmod{a_{2022}} \\
a_{8090} &=& (a_{8089})^2+1 \equiv 1^2+1 = 2 \pmod{a_{2022}} \\
a_{8091} &=& (a_{8090})^2+1 \equiv 2^2+1 = 5 \pmod{a_{2022}} \\
\end{eqnarray}$$

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

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

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

以上から、$a_{2022}$ は $5$ の倍数であるが $25$ の倍数でないので、$a_{2022}$ と $(a_{8091})^2$ の最大公約数は $\boldsymbol{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$ の最大公約数」だと分かれば、今度は $\mod{25}$ で考えるのがカギです。$a_4=26$ を $25$ で割った余りが $1$ となって $a_1$ と同じ値になる（つまり余りが循環する）のがこの問題の上手いところです。

まとめ

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