トップ› 東京大学› 2022年› 理系第2問

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

方針・初手

数列の漸化式 $a_{n+1} = a_n^2 + 1$ によって定まる数列 $\{a_n\}$ の性質を調べる問題である。（1）では法 $5$ での合同式を用いて数列の周期性を見つける。（2）では $a_k$ を法とする合同式に着目し、添え字 $n$ と $k$ の関係を割り出す。（3）ではその性質とユークリッドの互除法の原理を利用して最大公約数を求める。

解法1

(1) 法 $5$ における $a_n$ の剰余を考える。

$$ a_1 = 1 \equiv 1 \pmod 5 $$

$$ a_2 = 1^2 + 1 = 2 \equiv 2 \pmod 5 $$

$$ a_3 = 2^2 + 1 = 5 \equiv 0 \pmod 5 $$

$$ a_4 = 5^2 + 1 = 26 \equiv 1 \pmod 5 $$

漸化式 $a_{n+1} = a_n^2 + 1$ より、$a_{n+1}$ の法 $5$ での余りは $a_n$ の法 $5$ での余りだけで決まる。したがって、数列 $\{a_n\}$ を $5$ で割った余りは $1, 2, 0$ の周期 $3$ で繰り返される。すなわち、任意の非負整数 $m$ に対して以下が成り立つ。

$$ a_{3m+1} \equiv 1 \pmod 5 $$

$$ a_{3m+2} \equiv 2 \pmod 5 $$

$$ a_{3m+3} \equiv 0 \pmod 5 $$

よって、$n$ が $3$ の倍数のとき（$n = 3m+3$ のとき）、$a_n \equiv 0 \pmod 5$ となり、$a_n$ は $5$ の倍数となる。

(2) 任意の正の整数 $k$ を固定し、法 $a_k$ における $a_n$ の剰余を考える。すべての正の整数 $m$ について

$$ a_{k+m} \equiv a_m \pmod{a_k} $$

が成り立つことを $m$ についての数学的帰納法で示す。

(i)

$m = 1$ のとき $a_k \equiv 0 \pmod{a_k}$ であるから、

$$ a_{k+1} = a_k^2 + 1 \equiv 0^2 + 1 = 1 = a_1 \pmod{a_k} $$

となり成り立つ。

(ii)

$m = l$ のとき成立すると仮定する。すなわち $a_{k+l} \equiv a_l \pmod{a_k}$ とする。 $m = l+1$ のとき、

$$ a_{k+l+1} = a_{k+l}^2 + 1 \equiv a_l^2 + 1 = a_{l+1} \pmod{a_k} $$

となり、$m = l+1$ のときも成り立つ。

（i）、（ii）より、任意の正の整数 $m$ に対して $a_{k+m} \equiv a_m \pmod{a_k}$ が成り立つ。これを用いて、任意の正の整数 $n$ について $a_n$ の法 $a_k$ での余りを考える。 $n$ を $k$ で割った商を $q$、余りを $r$ とおくと、$n = qk + r$ （$q \ge 0, 0 \le r < k$）と表せる。

(ア)

$r = 0$ のとき $n = qk$ であり、$q=1$ ならば $a_k \equiv 0 \pmod{a_k}$ である。 $q \ge 2$ ならば、$a_{qk} = a_{k+(q-1)k} \equiv a_{(q-1)k} \pmod{a_k}$ を繰り返し適用することで、

$$ a_n = a_{qk} \equiv a_k \equiv 0 \pmod{a_k} $$

となり、$a_n$ は $a_k$ の倍数となる。

(イ)

$1 \le r < k$ のとき $q=0$ ならば $n=r$ である。 $q \ge 1$ ならば、$a_{k+m} \equiv a_m \pmod{a_k}$ を繰り返し適用することで、

$$ a_n = a_{qk+r} \equiv a_{(q-1)k+r} \equiv \cdots \equiv a_r \pmod{a_k} $$

となる。ここで、数列 $\{a_n\}$ は $a_1 = 1 > 0$ であり、

$$ a_{n+1} - a_n = a_n^2 - a_n + 1 = \left(a_n - \frac{1}{2}\right)^2 + \frac{3}{4} > 0 $$

より狭義単調増加する正の整数の列である。したがって $1 \le r < k$ のとき $0 < a_r < a_k$ が成り立つ。ゆえに $a_r \equiv 0 \pmod{a_k}$ とはならず、$a_n$ は $a_k$ の倍数ではない。

以上（ア）、（イ）より、$a_n$ が $a_k$ の倍数となるための必要十分条件は $n$ が $k$ の倍数となることである。

(3) 漸化式 $a_{n+1} = a_n^2 + 1$ より、$a_n^2 = a_{n+1} - 1$ である。これを用いると、

$$ (a_{8091})^2 = a_{8092} - 1 $$

となる。したがって、求める最大公約数は $\gcd(a_{2022}, a_{8092} - 1)$ である。 (2)で示した性質 $a_{k+m} \equiv a_m \pmod{a_k}$ より、法 $a_{2022}$ において $a_{m+2022} \equiv a_m \pmod{a_{2022}}$ が成り立つ。 $8092$ を $2022$ で割ると $8092 = 2022 \times 4 + 4$ であるから、

$$ a_{8092} \equiv a_4 \pmod{a_{2022}} $$

となる。ここで $a_4 = 26$ であるから、ある整数 $Q$ を用いて

$$ a_{8092} = Q a_{2022} + 26 $$

と表せる。ゆえに

$$ a_{8092} - 1 = Q a_{2022} + 25 $$

ユークリッドの互除法の原理より、

$$ \gcd(a_{2022}, a_{8092} - 1) = \gcd(a_{2022}, Q a_{2022} + 25) = \gcd(a_{2022}, 25) $$

が成り立つ。 $25 = 5^2$ であるから、$a_{2022}$ が $25$ を法としてどのような値と合同になるかを調べる。

$$ a_1 = 1 \equiv 1 \pmod{25} $$

$$ a_2 = 2 \equiv 2 \pmod{25} $$

$$ a_3 = 5 \equiv 5 \pmod{25} $$

$$ a_4 = 26 \equiv 1 \pmod{25} $$