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

(1) $x\mapsto x^2+1\pmod 5$ では $$1\longmapsto2\longmapsto0\longmapsto1$$ と巡回する。$a_1\equiv1\pmod5$ だから、$a_{3m+1},a_{3m+2},a_{3m+3}$ の剰余はそれぞれ $1,2,0$ となる（$m\geq0$）。従って $3\mid n$ なら $5\mid a_n$ である。

(2) 補助的に $a_0=0$ とおくと、漸化式は $a_1=a_0^2+1$ でも成り立つ。任意の正整数 $k$ について $$a_{k+r}\equiv a_r\pmod{a_k}\qquad(r\geq0) \tag{1}$$ が成り立つ。実際、$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\leq r<k)$ とする。$n\geq k$ なら (1) を繰り返して $a_n\equiv a_r\pmod{a_k}$ となる。数列は $a_{j+1}-a_j=a_j^2-a_j+1>0$ より増加するので、$1\leq r<k$ なら $0<a_r<a_k$ であり、この場合 $a_k\nmid a_n$。一方、$r=0$ なら $a_n\equiv a_0=0\pmod{a_k}$。また $n<k$ の場合も $0<a_n<a_k$ で割り切れない。従って $$a_k\mid a_n\quad\text{すなわち}\quad r=0 \quad\text{すなわち}\quad k\mid n.$$

(3) (1) より、$m\leq n$ のとき $$\gcd(a_m,a_n)=\gcd(a_m,a_{n-m})$$ である。添字にユークリッドの互除法を繰り返し適用すると $$\gcd(a_m,a_n)=a_{\gcd(m,n)}$$ を得る。ここで $8091=4\cdot2022+3$、$2022=674\cdot3$ だから $$\gcd(a_{2022},a_{8091})=a_3=5.$$ また $a_1,a_2,a_3\equiv1,2,5\pmod{25}$ であり、$5^2+1\equiv1\pmod{25}$ だから、剰余は $1,2,5$ と3項周期で繰り返す。$3\mid2022$ より $a_{2022}\equiv5\pmod{25}$、従って $25\nmid a_{2022}$。さらに $3\mid8091$ なので (1) より $5\mid a_{8091}$、すなわち $25\mid(a_{8091})^2$。

$\gcd(a_{2022},(a_{8091})^2)$ の任意の素因数は $a_{2022}$ と $a_{8091}$ の双方を割るため、$\gcd(a_{2022},a_{8091})=5$ から素因数は $5$ に限られる。$25\nmid a_{2022}$ であり、両数は5で割り切れるから $$\gcd\!\left(a_{2022},(a_{8091})^2\right)=5.$$