最近解いた問題で、結構良問だったので紹介します。
2017年のEGMO日本代表一次選抜試験の問題2です。
問題解説
問題をわかりやすく解説してみます。
数列の各項を具体的に計算してみると、
と続いていきます。
そして、条件を満たす素数というのは、
です。
そのような素数が無数に存在することを示せばいいのです。
条件が弱そう。
というか、無数に存在しない、つまり有限個しかないとしたら
逆にびっくりです…。
方針
(解いているときの自分の心の声的な感じで)
数列の一般項をもとめる(をの式で表す)のは難しそう。
一般項を求めなくともわかるこの数列の性質を探してみよう。
何か進展がみられそう。やってみよう。
うーん。全然性質が見つからない。
ただ一つ見つかったことといえば、
(ただし、は自然数、は素数)
ということぐらい。
この見つかった性質からいろいろ進展させてみよう。
(ただしtは正の整数)
がいえる。
ってことは、のとき、
がいえる。
これを繰り返すと、
ということがわかる。
なんか使えそうになってきた。
あ、ひらめいたぞ。
と拡張すると、となって自然だ。
はどんな数でも割り切れるから、
上の式にを代入して
より
いい感じ。
しかし、条件を満たす素数が無数に存在することをどう証明すればいいのだろう…?
とりあえず、素数が無数に存在することの証明みたいに、背理法を使おう。
条件を満たす素数が無数に存在しないと仮定して、矛盾を導いてみよう。
とりあえず、条件を満たすような素数をそれぞれとおいてみて…
のどれでも割り切れないようなはないかなあ。
あ、がの全てで割り切れればいいのか。
おっ、これはさっき示したアレが使える…!
よっしゃ、できた。
解答
すいません、長くなりました。解答です。
解答
条件を満たす素数が無数に存在しないと仮定して、矛盾を導く。
ここで数列をと拡張する。
より、以降の項の値は変わらない。
条件を満たすような素数をそれぞれとおく。
また、1以上n以下の正の整数に対し、がで割り切れるような最小の正の整数をとおく。
このとき、
のとき
が成り立つ。
これを繰り返すことにより、
が示される。
よって、に0を代入して、
である。
したがって、
はで割り切れる。
の定義より、はで割り切れる。
しかし、はと互いに素であるから、これはのどれでも割り切れない。
明らかにより、は以外に素因数を持つことになり、矛盾。
あとがき
整数論の問題にしては、面倒くさくなく、また程よい難易度で、かなりの良問だったと思います。こんな問題たくさん解きたい。