最近解いたEGMOの良問（2017年のEGMO日本代表一次選抜試験の問題2）

最近解いた問題で、結構良問だったので紹介します。
2017年のEGMO日本代表一次選抜試験の問題2です。

問題

数列 ${a_1,a_2,\cdots}$ を ${a_1=1,a_{k+1}=a_{k}^2+1(k=1,2,\cdots)}$ と定める。
このとき、次の条件を満たす素数 ${p}$ が無数に存在することを示せ。

条件： ${a_1,a_2,\cdots}$ の中に ${p}$ の倍数が存在する。

問題解説

問題をわかりやすく解説してみます。

数列の各項を具体的に計算してみると、
${a_1=1}$
${a_2=2}$
${a_3=5}$
${a_4=26=2\times 13}$
${a_5=677}$
${a_6=458330=2\times 5\times 45833}$
${a_7=210066388901=41\times 1277\times 4012193}$

と続いていきます。

そして、条件を満たす素数 ${p}$ というのは、
${p=2,5,13,677,45833,41,1277,4012193,\cdots}$
です。

そのような素数が無数に存在することを示せばいいのです。
条件が弱そう。

というか、無数に存在しない、つまり有限個しかないとしたら
逆にびっくりです…。

方針

（解いているときの自分の心の声的な感じで）

数列の一般項をもとめる（ ${a_n}$ を ${n}$ の式で表す）のは難しそう。

一般項を求めなくともわかるこの数列 ${a_1,a_2,\cdots}$ の性質を探してみよう。
何か進展がみられそう。やってみよう。

うーん。全然性質が見つからない。
ただ一つ見つかったことといえば、
${a_m \equiv a_n \pmod p \Rightarrow a_{m+1} \equiv a_{n+1} \pmod p}$
（ただし、 ${m,n}$ は自然数、 ${p}$ は素数）
ということぐらい。

この見つかった性質からいろいろ進展させてみよう。
${a_m \equiv a_n \pmod p \Rightarrow a_{m+t} \equiv a_{n+t} \pmod p}$
（ただしtは正の整数）
がいえる。

ってことは、 ${n=m+t}$ のとき、
${a_m \equiv a_{m+t} \pmod p \Rightarrow a_{m+t} \equiv a_{m+2t} \pmod p}$
がいえる。
これを繰り返すと、
${a_m \equiv a_{m+t}\equiv a_{m+2t}\equiv a_{m+3t}\equiv \cdots \pmod p}$
ということがわかる。
なんか使えそうになってきた。

あ、ひらめいたぞ。
${a_0=0}$ と拡張すると、 ${a_0^2+1=a_1}$ となって自然だ。
${a_0}$ はどんな数でも割り切れるから、
上の式に ${m=0}$ を代入して
${a_0 \equiv a_{0+t}\equiv a_{0+2t}\equiv a_{0+3t}\equiv \cdots \pmod p}$
より
${0 \equiv a_t\equiv a_{2t}\equiv a_{3t}\equiv \cdots \pmod p}$
いい感じ。

しかし、条件を満たす素数 ${p}$ が無数に存在することをどう証明すればいいのだろう…？

とりあえず、素数が無数に存在することの証明みたいに、背理法を使おう。
条件を満たす素数 ${p}$ が無数に存在しないと仮定して、矛盾を導いてみよう。

とりあえず、条件を満たすような素数をそれぞれ ${p_1,p_2,\cdots,p_n}$ とおいてみて…
${p_1,p_2,\cdots,p_n}$ のどれでも割り切れないような ${a_x}$ はないかなあ。

あ、 ${a_{x-1}}$ が ${p_1,p_2,\cdots,p_n}$ の全てで割り切れればいいのか。
おっ、これはさっき示したアレが使える…！

よっしゃ、できた。

解答

すいません、長くなりました。解答です。

解答

条件を満たす素数 ${p}$ が無数に存在しないと仮定して、矛盾を導く。

ここで数列を ${a_0=0,a_{k+1}=a_{k}^2+1(k=0,1,\cdots)}$ と拡張する。
${a_0^2+1=a_1}$ より、 ${a_1}$ 以降の項の値は変わらない。

条件を満たすような素数をそれぞれ ${p_1,p_2,\cdots,p_n}$ とおく。
また、1以上n以下の正の整数 ${i}$ に対し、 ${a_j}$ が ${p_i}$ で割り切れるような最小の正の整数 ${j}$ を ${f(i)}$ とおく。

このとき、
${a_m \equiv a_n \pmod p}$ のとき
${a_m^2+1 \equiv a_n^2+1 \pmod p}$
${a_{m+1} \equiv a_{n+1} \pmod p}$
が成り立つ。
これを繰り返すことにより、
${a_m \equiv a_{m+t}\equiv a_{m+2t}\equiv a_{m+3t}\equiv \cdots \pmod p}$
が示される。

よって、 ${m}$ に0を代入して、
${0 \equiv a_t\equiv a_{2t}\equiv a_{3t}\equiv \cdots \pmod p}$
である。

したがって、
${a_{f(1)f(2)\cdots f(n)}}$ は ${a_{f(1)},a_{f(2)},\cdots,a_{f(n)}}$ で割り切れる。
${f}$ の定義より、 ${a_{f(1)f(2)\cdots f(n)}}$ は ${p_1,p_2,\cdots,p_n}$ で割り切れる。