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

(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(\mathrm{m}\mathrm{o}\mathrm{d}5)$$である。さらに $a_4\equiv 0^2+1\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}5)$ となり、$a_1$ と同じ余りに戻る。漸化式は直前の余りだけで次の余りを決めるので、以後 $1,2,0$ が周期3で繰り返される。したがって $n$ が3の倍数のとき $a_n\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}5)$ であり、$a_n$ は5の倍数である。

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

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

いま $n=qk+r$、$0\leqq r<k$ とおく。この合同式を $q$ 回繰り返すと $a_n\equiv a_r(\mathrm{m}\mathrm{o}\mathrm{d}{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(\mathrm{m}\mathrm{o}\mathrm{d}{a}_k)$$ である。

したがって$$a_n\text{ が }{a}_k\text{ の倍数}⟺r=0⟺k\mid n$$である。

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

ここで $\gcd (2022,8091)=3$ であるから $$\gcd (a_{2022},a_{8091})=a_3$$ である。実際 $$a_1=1,a_2=2,a_3=5$$ なので $$\gcd (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(\mathrm{m}\mathrm{o}\mathrm{d}25)$$であるから、余りは周期3で $1,2,5$ を繰り返す。$2022$ は3の倍数なので $a_{2022}\equiv 5(\mathrm{m}\mathrm{o}\mathrm{d}25)$ である。したがって $a_{2022}$ は5で割り切れるが、25では割り切れない。 $a_{2022}$ と $(a_{8091}{)}^2$ の共通素因数 $p$ をとると、$p\mid (a_{8091}{)}^2$ から $p\mid a_{8091}$ である。したがって $p$ は $$\gcd (a_{2022},a_{8091})=5$$ の素因数であり、可能性は $p=5$ だけである。さらに $a_{2022}$ は25で割り切れないので、共通因子として現れる5の指数は1で止まる。

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

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

(1)
5を法として$$a_1\equiv 1,a_2\equiv 2,a_3\equiv 0,a_4\equiv 1$$だから余り $1,2,0$ が周期3で繰り返す。よって $3\mid n$ なら $5\mid a_n$ である。

(2)
$a_0=0$ とおく。帰納法により$$a_{k+j}\equiv a_j(\mathrm{m}\mathrm{o}\mathrm{d}{a}_k)(j\geqq 0)$$が成り立つ。したがって添字にユークリッド互除法を行うたびに項の最大公約数も保たれ、$$\gcd (a_m,a_n)=a_{\gcd (m,n)}$$を得る。数列は狭義単調増加だから$$a_k\mid a_n⟺\gcd (a_k,a_n)=a_k⟺a_{\gcd (k,n)}=a_k⟺\gcd (k,n)=k⟺k\mid n\mathrm{.}$$(3)
$8091=4\cdot 2022+3$ なので合同式より$$a_{8091}\equiv a_3=5(\mathrm{m}\mathrm{o}\mathrm{d}{a}_{2022})\mathrm{.}$$ゆえに$$\gcd (a_{2022},a_{8091}^2)=\gcd (a_{2022},25)\mathrm{.}$$25を法とすると余りは $1,2,5$ の周期3であり、$2022\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}3)$ だから$$a_{2022}\equiv 5(\mathrm{m}\mathrm{o}\mathrm{d}25)\mathrm{.}$$したがって求める最大公約数は $5$ である。