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

合同式で数列の剰余周期と添字の剰余関係を示し、整除判定とユークリッドの互除法による最大公約数計算を行う。

(1) $\pmod 5$ で、$x$ を $x^2+1$ に対応させると
$$1\to2\to0\to1$$
と巡回する。$a_1\equiv1\pmod5$ だから、$a_{3m+1},a_{3m+2},a_{3m+3}$ の剰余はそれぞれ $1,2,0$ となる（$m\geqq0$）。従って $n$ は $3$ で割り切れる なら $a_n$ は $5$ で割り切れる。

(2) 補助的に $a_0=0$ とおくと、漸化式は $a_1=a_0^2+1$ でも成り立つ。任意の正整数 $k$ について
$$a_{k+r}\equiv a_r\pmod{a_k}\qquad(r\geqq0) \qquad\text{（}1\text{）}$$
が成り立つ。実際、$r=0$ では $a_k\equiv a_0=0\pmod{a_k}$ であり、$a_{k+r}\equiv a_r\pmod{a_k}$ なら漸化式から
$$a_{k+r+1}=a_{k+r}^2+1\equiv a_r^2+1=a_{r+1}\pmod{a_k}$$
となるので、数学的帰納法で示される。

$n=qk+r\ (0\leqq r<k)$ とする。$n\geqq k$ なら (1) を繰り返して $a_n\equiv a_r\pmod{a_k}$ となる。数列は $a_{j+1}-a_j=a_j^2-a_j+1>0$ より増加するので、$1\leqq r<k$ なら $0<a_r<a_k$ であり、この場合 $a_n$ は $a_k$ で割り切れない。一方、$r=0$ なら $a_n\equiv a_0=0\pmod{a_k}$。また $n<k$ の場合も $0<a_n<a_k$ で割り切れない。従って
$$a_k\text{ は }a_n\text{ の約数}\quad\text{すなわち}\quad r=0 \quad\text{すなわち}\quad k\text{ は }n\text{ の約数}.$$

(3) (1) より、$m\leqq n$ のとき
$$\text{（}a_m\text{ と }a_n\text{ の最大公約数）}=\text{（}a_m\text{ と }a_{n-m}\text{ の最大公約数）}$$
である。添字にユークリッドの互除法を繰り返し適用すると
$$\text{（}a_m\text{ と }a_n\text{ の最大公約数）}=a_{\text{（}m\text{ と }n\text{ の最大公約数）}}$$
を得る。ここで $8091=4\cdot2022+3$、$2022=674\cdot3$ だから
$$\text{（}a_{2022}\text{ と }a_{8091}\text{ の最大公約数）}=a_3=5.$$
また $a_1,a_2,a_3\equiv1,2,5\pmod{25}$ であり、$5^2+1\equiv1\pmod{25}$ だから、剰余は $1,2,5$ と3項周期で繰り返す。$2022$ は $3$ で割り切れることから $a_{2022}\equiv5\pmod{25}$、従って $a_{2022}$ は $25$ で割り切れない。さらに $8091$ は $3$ で割り切れるので (1) より $a_{8091}$ は $5$ の倍数であり、したがって $(a_{8091})^2$ は $25$ の倍数である。

$\text{（}a_{2022}\text{ と }(a_{8091})^2\text{ の最大公約数）}$ の任意の素因数は $a_{2022}$ と $a_{8091}$ の双方を割るため、$\text{（}a_{2022}\text{ と }a_{8091}\text{ の最大公約数）}=5$ から素因数は $5$ に限られる。$a_{2022}$ は $25$ で割り切れない であり、両数は5で割り切れるから
$$\text{（}a_{2022}\text{ と }(a_{8091})^2\text{ の最大公約数）}=5.$$