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

問題

数列 ${a_{n}}$ を次のように定める。

a_{1} = 1, a_{n + 1} = a_{n}^{2} + 1 (n = 1, 2, 3, \dots\dots)

(1) 正の整数 $n$ が3の倍数のとき， $a_{n}$ は5の倍数となることを示せ。

(2) $k, n$ を正の整数とする。 $a_{n}$ が $a_{k}$ の倍数となるための必要十分条件を $k, n$ を用いて表せ。

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

出典：東京大学 2022年度前期日程第2次学力試験理系第2問

方針

解法1

漸化式 $a_{n + 1} = a_{n}^{2} + 1$ は、任意の法で余りだけを追える形である。 $a_{0} = 0$ と拡張すると、 $a_{k + j} \equiv a_{j} (mod a_{k})$ が帰納法で示せるので、添字に対して割り算の余りを取る操作がそのまま項の最大公約数に反映される。(2)はこの合同式と単調増加性から $a_{k} ∣ a_{n} ⟺ k ∣ n$ を示す。(3)は同じ合同式で $g cd (a_{m}, a_{n}) = a_{g c d (m, n)}$ を証明してから、25を法とする周期で5の指数を確認する。

解法2

まず強い整除性 $g cd (a_{m}, a_{n}) = a_{g c d (m, n)}$ を合同式とユークリッド互除法で示す。(2)はこの公式と単調増加性から直ちに判定し、(3)は $a_{8091}$ の $a_{2022}$ による余りを直接5まで落として平方の最大公約数を25との最大公約数に帰着する。

解答

解法1

(1)

5を法として $a_{n}$ の余りを調べる。 $a_{1} = 1$ から

a_{1} \equiv 1, a_{2} \equiv 1^{2} + 1 \equiv 2, a_{3} \equiv 2^{2} + 1 \equiv 0 (mod 5)

である。さらに $a_{4} \equiv 0^{2} + 1 \equiv 1 (mod 5)$ となり、 $a_{1}$ と同じ余りに戻る。漸化式は直前の余りだけで次の余りを決めるので、以後 $1, 2, 0$ が周期3で繰り返される。したがって $n$ が3の倍数のとき $a_{n} \equiv 0 (mod 5)$ であり、 $a_{n}$ は5の倍数である。

(2)

$a_{0} = 0$ と定める。このとき $a_{1} = a_{0}^{2} + 1$ なので、漸化式は $n = 0$ から成り立つ。

固定した正の整数 $k$ に対して $a_{k + j} \equiv a_{j} (mod a_{k}) (j = 0, 1, 2, \dots)$ を示す。 $j = 0$ では $a_{k} \equiv a_{0} = 0 (mod a_{k})$ である。 $a_{k + j} \equiv a_{j} (mod a_{k})$ が成り立つと仮定すると、漸化式より $a_{k + j + 1} = a_{k + j}^{2} + 1 \equiv a_{j}^{2} + 1 = a_{j + 1} (mod a_{k})$ である。よって帰納法により上の合同式が成り立つ。

いま $n = q k + r$ 、 $0 ≦ r < k$ とおく。この合同式を $q$ 回繰り返すと $a_{n} \equiv a_{r} (mod a_{k})$ である。

数列 $a_{n}$ は正で、 $a_{n + 1} = a_{n}^{2} + 1 > a_{n}$ より単調増加する。したがって $0 < r < k$ なら $0 < a_{r} < a_{k}$ であり、 $a_{n}$ を $a_{k}$ で割った余りは0ではない。一方、 $r = 0$ なら $a_{n} \equiv a_{0} = 0 (mod a_{k})$ である。

したがって

a_{n} が a_{k} の倍数 ⟺ r = 0 ⟺ k ∣ n

である。

(3)

まず、任意の正整数 $m, n$ について $g cd (a_{m}, a_{n}) = a_{g c d (m, n)}$ が成り立つことを確認する。たとえば $m = q n + r$ 、 $0 ≦ r < n$ とすると、(2)で用いた合同式より $a_{m} \equiv a_{r} (mod a_{n})$ である。したがって $g cd (a_{m}, a_{n}) = g cd (a_{n}, a_{r})$ である。これは添字に対するユークリッドの互除法と同じ操作であり、最後に余りが0になったとき $g cd (a_{d}, a_{0}) = a_{d}$ となる。ゆえに上の式が成り立つ。

ここで $g cd (2022, 8091) = 3$ であるから $g cd (a_{2022}, a_{8091}) = a_{3}$ である。実際 $a_{1} = 1, a_{2} = 2, a_{3} = 5$ なので $g cd (a_{2022}, a_{8091}) = 5$ である。

次に、 $a_{2022}$ が25で割り切れるかを調べる。25を法として

a_{1} \equiv 1, a_{2} \equiv 2, a_{3} \equiv 5, a_{4} \equiv 5^{2} + 1 \equiv 1 (mod 25)

であるから、余りは周期3で $1, 2, 5$ を繰り返す。 $2022$ は3の倍数なので $a_{2022} \equiv 5 (mod 25)$ である。したがって $a_{2022}$ は5で割り切れるが、25では割り切れない。 $a_{2022}$ と $(a_{8091})^{2}$ の共通素因数 $p$ をとると、 $p ∣ (a_{8091})^{2}$ から $p ∣ a_{8091}$ である。したがって $p$ は $g cd (a_{2022}, a_{8091}) = 5$ の素因数であり、可能性は $p = 5$ だけである。さらに $a_{2022}$ は25で割り切れないので、共通因子として現れる5の指数は1で止まる。

よって求める最大公約数は $5$ である。

解法2

(1)

5を法として

a_{1} \equiv 1, a_{2} \equiv 2, a_{3} \equiv 0, a_{4} \equiv 1

だから余り $1, 2, 0$ が周期3で繰り返す。よって $3 ∣ n$ なら $5 ∣ a_{n}$ である。

(2)

$a_{0} = 0$ とおく。帰納法により

a_{k + j} \equiv a_{j} (mod a_{k}) (j ≧ 0)

が成り立つ。したがって添字にユークリッド互除法を行うたびに項の最大公約数も保たれ、

g cd (a_{m}, a_{n}) = a_{g c d (m, n)}

を得る。数列は狭義単調増加だから

a_{k} ∣ a_{n} ⟺ g cd (a_{k}, a_{n}) = a_{k} ⟺ a_{g c d (k, n)} = a_{k} ⟺ g cd (k, n) = k ⟺ k ∣ n .

(3)

$8091 = 4 \cdot 2022 + 3$ なので合同式より

a_{8091} \equiv a_{3} = 5 (mod a_{2022}) .

ゆえに

g cd (a_{2022}, a_{8091}^{2}) = g cd (a_{2022}, 25) .

25を法とすると余りは $1, 2, 5$ の周期3であり、 $2022 \equiv 0 (mod 3)$ だから

a_{2022} \equiv 5 (mod 25) .

したがって求める最大公約数は $5$ である。

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

問題

方針

解法1

解法2

解答

解法1

(1)

(2)

(3)

解法2

(1)

(2)

(3)

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