2次の素数生成公式について考えます。

　n^2+n+kがn=0〜k-2のとき素数になるには、0≦n≦√(k/3)のとき素数になることが必要十分だとわかっているようです．

この性質により効率的な判定が可能となります。

n^2+n+11についてはn=0,1について素数であることを確かめればn=0から9まで素数であることがわかります。

n^2+n+41についてはn=0,1,2,3について素数であることを確かめればn=0から39まで素数であることがわかります。

　これが正しいことを確認するのは簡単ですが，ラビノヴィッチの定理を用いずに証明することが可能なのでしょうか？

ともあれ、数学オリンピック(1987)の中でも難問の属する問題なのだそうですが、実は初等的に証明できるのだそうです。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　an=n^2+n+k

　a0,a1,a2,・・・,ak-2に一つでも素数でなければ矛盾が生ずることを示します。

最初に現れる素数でない数をasとすると、　

a0,a1,a2,・・・,as-1は素数、asは素数でない。最も小さい素因数をｐとすると

as=s^2+s+k=p・q・r・・・

as=s^2+s+k≧p^2

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

a0,a1,a2,・・・,as-1は素数であるが、このなかにｐが出てくるかどうかを分析する

as-a0,as-a1,・・・,as-as-1

as-an=s^2+s-n^2-n=(s-n)(s+n+1)より

as-a0=s(s+1)

as-a1=(s-1)(s+2)

as-a2=(s-2)(s+3)

as-as-1=1x2s

ここでp≦2sと仮定すれば因数分解のどこかに素数ｐが顔を出すことになる。

それをatとすると

0≦ｔ≦ｓ-1

as-at=(s-t)(s+t+1)

s-t=pまたはs+t+1=p

as-atはｐの倍数となり、もともとasはｐの倍数ですから、atもｐの倍数。

atは素数ですから、atはｐそのもの。

したがって、at=t^2+t+k=p

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

-1＜t^2,ｓ≦ｋ-2なので、s+t+1＜t^2+t+k=p

s-t＜s+t+1＜ｐとなって、矛盾。仮定p≦2sがまずかったことになる。

したがって、2ｓ+1≦ｐ・・・これが0≦n≦√(k/3)、n^2+n+kは素数に引っかかることになる。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

s^2+s+k≧p^2≧(2s+1)^2=4s^2+4s+1

k≧3s^2+3s+1

s=√(k/3)とおくと3s^2+3s+1＞ｋとなるから

s≦√(k/3)であるが、asは素数になってしまい、仮定に反する。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

[参]小島寛之「数学オリンピック問題にみる現代数学」講談社ブルーバックス

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝