トップ› 東京大学› 2022年› 文系第3問

東京大学 2022年文系第3問解説

方針・初手

（1）は合同式を用いて、数列 $\{a_n\}$ を $3$ で割った余りの周期性を調べる。（2）はユークリッドの互除法の考え方を応用し、隣接する項の関係式から最大公約数の候補を絞り込む。

解法1

(1) すべての自然数 $n$ について、$a_n$ を $3$ で割った余りを合同式を用いて調べる。与えられた漸化式は以下の通りである。

$$ a_{n+1} = a_n^2 + n(n+2) $$

法を $3$ として各項の余りを順に計算する。

$$ \begin{aligned} a_1 &= 4 \equiv 1 \pmod 3 \\ a_2 &= a_1^2 + 1 \cdot 3 \equiv 1^2 + 0 \equiv 1 \pmod 3 \\ a_3 &= a_2^2 + 2 \cdot 4 \equiv 1^2 + 8 \equiv 0 \pmod 3 \\ a_4 &= a_3^2 + 3 \cdot 5 \equiv 0^2 + 0 \equiv 0 \pmod 3 \\ a_5 &= a_4^2 + 4 \cdot 6 \equiv 0^2 + 0 \equiv 0 \pmod 3 \\ a_6 &= a_5^2 + 5 \cdot 7 \equiv 0^2 + 35 \equiv 2 \pmod 3 \\ a_7 &= a_6^2 + 6 \cdot 8 \equiv 2^2 + 0 \equiv 1 \pmod 3 \end{aligned} $$

この結果から、$a_n$ を $3$ で割った余りは $1, 1, 0, 0, 0, 2$ の周期 $6$ で繰り返されると推測できる。これを数学的帰納法で証明する。すべての非負整数 $k$ について、以下の合同式が成り立つことを示す。

$$ \begin{aligned} a_{6k+1} &\equiv 1 \pmod 3 \\ a_{6k+2} &\equiv 1 \pmod 3 \\ a_{6k+3} &\equiv 0 \pmod 3 \\ a_{6k+4} &\equiv 0 \pmod 3 \\ a_{6k+5} &\equiv 0 \pmod 3 \\ a_{6k+6} &\equiv 2 \pmod 3 \end{aligned} $$

(i)

$k=0$ のとき

上記の計算結果より成り立つ。

(ii)

$k=m$ のとき成り立つと仮定する。

$k=m+1$ のとき、

$$ \begin{aligned} a_{6m+7} &= a_{6m+6}^2 + (6m+6)(6m+8) \equiv 2^2 + 0 \equiv 1 \pmod 3 \\ a_{6m+8} &= a_{6m+7}^2 + (6m+7)(6m+9) \equiv 1^2 + 0 \equiv 1 \pmod 3 \\ a_{6m+9} &= a_{6m+8}^2 + (6m+8)(6m+10) \equiv 1^2 + 2 \cdot 1 \equiv 0 \pmod 3 \\ a_{6m+10} &= a_{6m+9}^2 + (6m+9)(6m+11) \equiv 0^2 + 0 \equiv 0 \pmod 3 \\ a_{6m+11} &= a_{6m+10}^2 + (6m+10)(6m+12) \equiv 0^2 + 0 \equiv 0 \pmod 3 \\ a_{6m+12} &= a_{6m+11}^2 + (6m+11)(6m+13) \equiv 0^2 + 2 \cdot 1 \equiv 2 \pmod 3 \end{aligned} $$

したがって、$k=m+1$ のときも成り立つ。

(i), (ii) より、すべての非負整数 $k$ で周期性が示された。ここで、$2022 = 6 \times 337$ であるから、$k=336$ のときの $a_{6k+6}$ に該当する。よって、$a_{2022} \equiv 2 \pmod 3$ となり、$a_{2022}$ を $3$ で割った余りは $2$ である。

(2) $n=2022$ とおき、$a_{n}, a_{n+1}, a_{n+2}$ の最大公約数を $g$ とする。漸化式より、以下の関係が成り立つ。

$$ \begin{aligned} a_{n+1} - a_n^2 &= n(n+2) \\ a_{n+2} - a_{n+1}^2 &= (n+1)(n+3) \end{aligned} $$

$g$ は $a_n$ と $a_{n+1}$ の公約数であるから、上式の左辺 $a_{n+1} - a_n^2$ を割り切る。したがって、$g$ は $n(n+2)$ の約数である。同様に、$g$ は $a_{n+1}$ と $a_{n+2}$ の公約数であるから、下式の左辺 $a_{n+2} - a_{n+1}^2$ を割り切る。したがって、$g$ は $(n+1)(n+3)$ の約数でもある。ゆえに、$g$ は $n(n+2)$ と $(n+1)(n+3)$ の公約数である。

これら2つの式の差をとると、

$$ (n+1)(n+3) - n(n+2) = (n^2 + 4n + 3) - (n^2 + 2n) = 2n + 3 $$

となるため、$g$ は $2n + 3$ の約数でもある。さらに、$g$ は $n(n+2)$ と $2n+3$ をともに割り切ることから、以下の式を考える。

$$ 4n(n+2) = 4n^2 + 8n = (2n+3)(2n+1) - 3 $$

この式を変形すると、

$$ 3 = (2n+3)(2n+1) - 4n(n+2) $$

$g$ は $2n+3$ と $n(n+2)$ を割り切るため、右辺全体を割り切る。したがって、$g$ は $3$ の約数でなければならない。すなわち、$g = 1$ または $g = 3$ である。

ここで (1) の結果より、$a_{2022}$ を $3$ で割った余りは $2$ であるため、$a_{2022}$ は $3$ の倍数ではない。よって、$g$ が $3$ になることはあり得ない。以上より、$g = 1$ と決定される。