https://spherical-harmonics.hateblo.jp/entry/Todai/2022/Rika

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記

今年の東大理系数学第2問には一応数学的なネタがありまして、「Divisibility sequence」ってのがあります
詳しくはリンク先にて(英語)https://t.co/WaWWKQzNO1 pic.twitter.com/SwCLeb5lOF
— カグラルナ (@QBtdvOepKuXxhg2) 2022年3月2日

Divisibility sequence - Wikipedia
Elliptic divisibility sequence - Wikipedia

だそうだ。

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