5 で割った余りは 3 つでめぐる

a_1 = 1, a_2 = 2, a_3 = 5, a_4 = 26, a_5 = 677 と、数はすぐ手に負えなくなります。そのまま追うのはあきらめて、余りだけを見ます。

a_{n+1} = a_n^2+1 は、a_n の余りだけで次の余りが決まる形です。だから余りは必ずどこかでめぐり始めます。

5 で割った余りを並べると 1, 2, 0, 1, 2, 0, \ldots です。0 の次は 0^2+1 = 1 で先頭へ戻り、3 つでひと回りします。

余りが 0 になるのは 3 番目、6 番目、\ldots ですから、a_n が 5 の倍数になるのは n が 3 の倍数のときです。これで (1) が示せました。

a_k で割ると数列が頭から出直す

こんどは a_k で割った余りを見ます。a_k \equiv 0 ですから a_{k+1} = a_k^2+1 \equiv 1 = a_1 です。先頭に戻りました。

先へも続きます。a_{k+j} \equiv a_j なら a_{k+j+1} = a_{k+j}^2+1 \equiv a_j^2+1 = a_{j+1} ですから、a_{k+j} \equiv a_j \pmod{a_k} が j について次々に出ます。

つまり a_k で割った余りは k 個ごとに同じ並びをくり返し、0 が出るのは添字が k の倍数のところだけです。

途中で 0 が出ないことも要ります。1 \leqq j \leqq k-1 では 0 < a_j < a_k ですから、余りは a_j そのもので 0 になりません。(2) の答えは「n が k の倍数であること」です。

(3) では 2 つの添字がどちらも大きく、片方は 2 乗されています。まず 2 乗を外して考えます。

m を n で割った余りを r とすると、いまの性質から a_m \equiv a_r \pmod{a_n} です。だから \gcd(a_m,\,a_n) = \gcd(a_r,\,a_n) となります。

これは添字のほうでユークリッドの互除法を回すのと同じことです。行き着く先は \gcd(a_m,\,a_n) = a_{\gcd(m,\,n)} です。

8091 = 4 \times 2022+3、2022 = 674 \times 3 ですから \gcd(2022,\,8091) = 3 で、\gcd(a_{2022},\,a_{8091}) = a_3 = 5 です。

a_{2022} と (a_{8091})^2 が共通に持てる素数は、a_{2022} と a_{8091} の両方を割る素数だけです。それは 5 に限られます。

残るのは 5 を何個まで共通に持てるかです。(a_{8091})^2 の側は 2 乗したぶん増えているかもしれません。

25 で割った余りを追います。1, 2, 5, 1, 2, 5, \ldots と、こちらも 3 つでめぐります。3 の倍数のところは余りが 5 で、0 ではありません。

つまり a_{2022} は 5 で割れますが 25 では割れず、5 を 1 個しか持ちません。少ないほうに合わせるので、最大公約数は 5 です。