独自の解答・詳解
問題文は非掲載
小問3問・無料

東京大学　2022年度　前期日程　理科

第2問整数・数列の解答・解説

漸化式と整除・合同式・最大公約数・ユークリッドの互除法当サイトの体感難易度：やや難最終更新 2026/10/11

問題文について

大学の公式解答ではなく、当サイト独自の解答・解説です。問題文は掲載していません。理科の問題文は、この年度については大学が公開していません（2026/10/11時点）。お手元の過去問集・赤本などでご確認ください。

問題を転載している非公式サイトへのリンクは、当サイトでは行っていません。

(1) $n$ が $3$ の倍数のとき $a_{n}$ が $5$ の倍数であることを示す

答 $5$ で割った余りが $1, 2, 0$ の繰り返しになる

$a_{n + 1}$ は $a_{n}$ だけから決まるので、 $5$ で割った余りも「余り $\to$ 余り」で決まる。最初の数項の余りを書き出すと周期3で繰り返すことが見え、あとはそれを数学的帰納法で固めるだけでよい。

$a_{1} = 1$ 、 $a_{2} = 2$ 、 $a_{3} = 5$ 、 $a_{4} = 26$ 、 $a_{5} = 677$ 、… である。 $5$ で割った余りを順に書くと

1, 2, 0, 1, 2, 0, \dots

となる。これを証明する。 $m$ を $0$ 以上の整数として、次の主張を $m$ についての数学的帰納法で示す。

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

$m = 0$ のときは $a_{1} = 1$ 、 $a_{2} = 2$ 、 $a_{3} = 5$ で成り立つ。 $m$ で成り立つとすると、 $a_{3 m + 3} \equiv 0$ だから

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

となり $m + 1$ でも成り立つ。よってすべての $m$ で成り立ち、とくに $n$ が $3$ の倍数のとき $a_{n}$ は $5$ の倍数である。

同じ計算を $25$ を法として行うと、余りは $1, 2, 5$ の繰り返しになる（ $a_{4} = 26 \equiv 1 (mod 25)$ がきっかけ）。つまり $3$ の倍数番目の項は $5$ では割り切れるが $25$ では割り切れない。これは (3) で効く。

$a_{6} = 458330 = 5 \times 91666$ で、 $91666$ は $5$ の倍数でない。 $a_{9}$ まで多倍長整数で計算しても、 $3$ の倍数番目はすべて $5$ でちょうど1回だけ割り切れる。

(2) $a_{n}$ が $a_{k}$ の倍数となるための必要十分条件を $k, n$ で表す

答 $n$ が $k$ の倍数であること

$a_{k + 1} = a_{k}^{2} + 1$ は $a_{k}$ で割ると $1$ 余る。つまり $a_{k}$ を法として見ると、数列は $k$ 項目からまた $a_{1}, a_{2}, \dots$ をなぞり直す。この「周期 $k$ 」が分かれば、 $a_{n}$ の余りは $n$ を $k$ で割った余りだけで決まる。あとは $a_{1} < a_{2} < \dots$ であることから、余りが $0$ になるのは割り切れるときだけだと分かる。

まず ${a_{n}}$ は $a_{1} = 1$ で $a_{n + 1} - a_{n} = a_{n}^{2} - a_{n} + 1 = (a_{n} - \frac{1}{2})^{2} + \frac{3}{4} > 0$ だから狭義の増加列で、すべて正の整数である。

$a_{k}$ を法とした周期。 次を $j$ についての数学的帰納法で示す。

a_{k + j} \equiv a_{j} (mod a_{k}) (j = 1, 2, 3, \dots)

$j = 1$ のときは $a_{k + 1} = a_{k}^{2} + 1 \equiv 1 = a_{1}$ で成り立つ。 $j$ で成り立つとすると

a_{k + j + 1} = a_{k + j}^{2} + 1 \equiv a_{j}^{2} + 1 = a_{j + 1} (mod a_{k})

となり $j + 1$ でも成り立つ。これを繰り返し使えば、 $q$ を正の整数として $a_{q k + j} \equiv a_{j} (mod a_{k})$ が言える。

余りが $0$ になるとき。 $n$ を $k$ で割って $n = q k + r$ （ $1 \leq r \leq k$ 、 $q \geq 0$ ）と書く。上より $a_{n} \equiv a_{r} (mod a_{k})$ である。

$r = k$ （つまり $n$ が $k$ の倍数）のとき： $a_{n} \equiv a_{k} \equiv 0$ なので $a_{n}$ は $a_{k}$ の倍数。
$1 \leq r < k$ のとき： $k \geq 2$ であり、増加列だから $0 < a_{r} < a_{k}$ 。よって $a_{r}$ は $a_{k}$ の倍数ではなく、 $a_{n}$ も $a_{k}$ の倍数ではない。

$k = 1$ のときは $a_{1} = 1$ ですべての $a_{n}$ が $a_{1}$ の倍数であり、「 $n$ が $1$ の倍数」も常に正しいので、この場合も合っている。よって求める必要十分条件は

n が k の倍数であること

である。

$a_{6} = 458330$ は $a_{3} = 5$ の倍数で、 $a_{2} = 2$ の倍数でもある（ $6$ は $3$ と $2$ の倍数）。 $a_{4} = 26$ は $a_{2} = 2$ の倍数だが $a_{3} = 5$ の倍数ではない（ $4$ は $2$ の倍数だが $3$ の倍数でない）。多倍長整数で $1 \leq k, n \leq 12$ を全部調べても例外はなかった。

$n = q k + r$ の余りを $0 \leq r < k$ ではなく $1 \leq r \leq k$ ととると、「ちょうど割り切れる」場合が $r = k$ としてきれいに扱える。 $a_{0}$ を定義せずに済む。

「 $a_{r}$ が $a_{k}$ の倍数でない」の根拠は $0 < a_{r} < a_{k}$ である。増加列であることを先に言っておく。

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

答 $5$

(2) で得た「 $a_{k}$ を法とすると周期 $k$ 」をそのまま使う。 $8091$ を $2022$ で割った余りは $3$ なので、 $a_{8091}$ は $a_{2022}$ で割ると $a_{3} = 5$ 余る。すると $(a_{8091})^{2}$ は $25$ 余るので、互除法で「 $a_{2022}$ と $25$ の最大公約数」に化ける。あとは $a_{2022}$ が $5$ で割り切れて $25$ で割り切れないことを言えばよい。

$8091 = 4 \cdot 2022 + 3$ である。(2) の証明で示した $a_{k + j} \equiv a_{j} (mod a_{k})$ を $k = 2022$ として4回使うと

a_{8091} \equiv a_{6069} \equiv a_{4047} \equiv a_{2025} \equiv a_{3} = 5 (mod a_{2022})

となる。したがって

(a_{8091})^{2} \equiv 5^{2} = 25 (mod a_{2022})

である。ユークリッドの互除法より、 $a_{2022}$ と $(a_{8091})^{2}$ の最大公約数は、 $a_{2022}$ と $25$ の最大公約数に等しい（ $a_{2022} > 25$ なので、 $(a_{8091})^{2}$ を $a_{2022}$ で割った余りはちょうど $25$ である）。

$a_{2022}$ を $25$ で割った余り。 (1) と同じ要領で、 $25$ を法として

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

を数学的帰納法で示す。 $m = 0$ では $a_{1} = 1$ 、 $a_{2} = 2$ 、 $a_{3} = 5$ で正しい。 $m$ で正しいとすると $a_{3 m + 3} \equiv 5$ より

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

となるので $m + 1$ でも正しい。 $2022 = 3 \cdot 674$ は $3$ の倍数だから $a_{2022} \equiv 5 (mod 25)$ 、つまり $a_{2022}$ は $5$ で割り切れるが $25$ では割り切れない。

よって $a_{2022}$ と $25$ の最大公約数は $5$ であり、求める最大公約数は $5$ である。

小さい番号で同じ状況を作って確かめられる。 $m = 6$ 、 $n = 9$ は最大公約数が $3$ で、多倍長整数で計算すると $a_{6}$ と $(a_{9})^{2}$ の最大公約数は $5$ になる。 $m = 6$ 、 $n = 15$ でも、 $m = 9$ 、 $n = 6$ でも $5$ である。

$(a_{8091})^{2}$ を $a_{8091}$ と同じに扱わない。 $a_{2022}$ と $a_{8091}$ の最大公約数は $5$ だが、2乗したぶん $5$ の指数が増える可能性があるので、 $a_{2022}$ が $25$ で割り切れないことまで確かめて初めて答えが $5$ と決まる。

$8091$ と $2022$ の最大公約数が $3$ であること（ $8091 = 3^{2} \cdot 29 \cdot 31$ 、 $2022 = 2 \cdot 3 \cdot 337$ ）と、 $a_{3} = 5$ が対応しているのは偶然ではない。一般に $a_{m}$ と $a_{n}$ の最大公約数は $a_{(m, n)}$ になる。

2022年度の全6問をまとめて読む

大学の公式解答ではなく、当サイト独自の解答・解説です。問題文は掲載していません。解答は当サイトで検算していますが、誤りが残っている可能性はあります。掲載方針

当サイト運営者が制作した教材

同じ形式の問題を、5回分

合格答案をつくる東大理系数学 2027

東大理系数学の出題を分析して書き下ろした予想問題集です。過去問そのものは入っていません。本番と同じ試験時間・大問構成で5回分、解答・詳解・別解に加えて、小問ごとの加点・減点つきの採点表を収録しています。

Amazonで見る全3巻を見る¥2,695・168ページ・2026年8月2日発売

中身を試し読みする

扉・問題・解答などを、それぞれ抜粋して掲載しています。連続したページではありません。画像を押すと拡大できます。

抜粋をPDFでまとめて見る

問題文について

(1)n が 3 の倍数のとき an​ が 5 の倍数であることを示す

(2)an​ が ak​ の倍数となるための必要十分条件を k,n で表す

(3)a2022​ と (a8091​)2 の最大公約数を求める

同じ形式の問題を、5回分

中身を試し読みする

関連するページ

(1) $n$ が $3$ の倍数のとき $a_{n}$ が $5$ の倍数であることを示す

(2) $a_{n}$ が $a_{k}$ の倍数となるための必要十分条件を $k, n$ で表す

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