読者です 読者をやめる 読者になる 読者になる

数学徘徊記

自由な数学ブログ。

最近解いた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}で割り切れる。

しかし、{a_{f(1)f(2)\cdots f(n)+1}}{a_{f(1)f(2)\cdots f(n)}}と互いに素であるから、これは{p_1,p_2,\cdots,p_n}のどれでも割り切れない。

明らかに{a_{f(1)f(2)\cdots f(n)+1}>1}より、{a_{f(1)f(2)\cdots f(n)+1}}{p_1,p_2,\cdots,p_n}以外に素因数を持つことになり、矛盾。

よって、背理法より、条件を満たす素数{p}が無数に存在することが証明された。
Q.E.D.

あとがき

整数論の問題にしては、面倒くさくなく、また程よい難易度で、かなりの良問だったと思います。こんな問題たくさん解きたい。