今回は、東京大学理系数学(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}$ の倍数である。
$$\boldsymbol{n \ \mathbf{が} \ k \ \mathbf{の倍数}}$$
⑶
$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}$ である。
$$\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, \ b, \ q, \ r$ を $0$ でない整数とし、$2$ 整数 $a,b$ の最大公約数を $\mathrm{gcd}(a,b)$ と表す。
$a=bq+r$ ならば $\mathrm{gcd}(a,b)=\mathrm{gcd}(b,r)$
求める値が「 $a_{2022}$ と $25$ の最大公約数」だと分かれば、今度は $\mod{25}$ で考えるのがカギです。$a_4=26$ を $25$ で割った余りが $1$ となって $a_1$ と同じ値になる(つまり余りが循環する)のがこの問題の上手いところです。
まとめ
今回は、東京大学理系数学(2022年 第2問)の解説をしました。
ほかの問題にもチャレンジしよう!
東京大学 理系数学 2022年 第1問 解説
東京大学 理系数学 2022年 第2問 解説
東京大学 理系数学 2022年 第3問 解説
東京大学 理系数学 2022年 第4問 解説
東京大学 理系数学 2022年 第5問 解説
東京大学 理系数学 2022年 第6問 解説