[別館]球面倶楽部零八式markIISR

東大入試数学中心。解説なので解答としては不十分。出題年度で並ぶようにしている。大人の解法やうまい解法は極めて主観的に決めている。

2022年(令和4年)東京大学-数学(理科)[2]

2022.02.25記

[2] 数列 \{a_n\} を次のように定める。
a_1=1，a_{n+1}=a_n^2+1（n=1,2,3,\cdots\cdots）

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

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

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


2022.02.25記

[解答]

(1) \mbox{mod} \,5 で考える。a_m\equiv 1 のとき a_{m+1} \equiv 2，a_{m+2} \equiv 5 \equiv 0，a_{m+3} \equiv 1 となるので，a_1=1 とから，一般に
a_{3u+1}\equiv 1，a_{3u+2}\equiv 2，a_{3u+3}\equiv 0
が成立する．よって正の整数 n が3の倍数のとき，a_n は 5 の倍数となる。

(2) \mbox{mod}\, a_k で考える。正の整数 m が a_m\equiv 1 をみたすとき，
a_m\equiv a_1 から帰納的に任意の正の整数 l に対して a_{m+l}\equiv a_{1+l} が成立する．
よって，a_{m+k-1}\equiv a_{k} \equiv 0 となり，a_{m+k}\equiv 1 が成立する．ここで a_m が単調増加であることに注意すると，a_{m+l}\equiv 0 となる最小の l は l=k-1 であるから，数列 a_n の \mbox{mod}\, a_k での基本周期は k となる．

よって，a_n\equiv a_k であるための必要十分条件は「n は k の倍数であること」である．

(3) ユークリッドの互除法を用いる。
a_{2022} と (a_{8901})^2 の最大公約数は
a_{2022} と a_{8902}-1 の最大公約数に等しく，
8902=4\times 2022+4 から
a_{2022} と a_{4}-1=(a_3)^2=5^2=25 の最大公約数に等しい。
ここで 2022 が 3 の倍数であることから
a_{2022} は a_3=5 の倍数であるが，a_n は \mbox{mod}\,25 で 1,2,5 を繰り返すので、a_{2022} が 25 の倍数になることはない．

よって，求める最大公約数は 5 である．

2022.03.03記


Divisibility sequence - Wikipedia
Elliptic divisibility sequence - Wikipedia

だそうだ。

2023.01.02記
end-of-paiotu.hatenablog.com
end-of-paiotu.hatenablog.com