■素数生成多項式(その39)

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は素数でない。最も小さい素因数をpとすると

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

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

===================================

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

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と仮定すれば因数分解のどこかに素数pが顔を出すことになる。

それをatとすると

0≦t≦s-1

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

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

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

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

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

===================================

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

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

したがって、2s+1≦p・・・これが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>kとなるから

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

===================================

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

===================================