問題はこちら（画像をクリックするとPDFファイルで開きます。）
本問にまつわる話としては、オイラーの見つけた
\(f(x)=x^{2}+x+41\)
という式が有名です。
- \(f(0)=41\)
- \(f(1)=43\)
- \(f(2)=47\)
- \(f(3)=53\)
というように、素数を生成し続けます。
ただ、これは永遠に素数を生み出し続けるわけではなく、
\(f(40)=40^{2}+40+41=40 (40+1)+41=41^{2}\)
となり、合成数も生まれてしまいます。
ただ、結構な長さで素数を生み出し続けてくれました。
オイラーの見つけたこの関数は失敗してしまいましたが、永遠に素数を生み出し続ける「素数生成多項式」を発見できたとしたら、どんなに喜ばしいことかは言うまでもありません。
ただ、これは残念なことに否定的な結果として証明されます。
ルジャンドルにより、
- 有理数係数でそのような素数生成多項式は定数関数以外ありえない
ということが証明されてしまったのです。
それはそれで一歩前進ですけど。
本問においては整数係数でやってごらんという問題です。
（以下ネタバレ注意）
+ クリック（タップ）して続きを読む
(1) について
ひとまず、\(f(x)\) を \(N\) 次多項式として、
\(f(x)=a_{N}x^{N}+a_{N-1}x^{N-1}+\cdots+a_{1}x+a_{0}\)
と設定します。
ここでカギとなってくるのは
\(f(x)-f(y)=(x-y)( \ \ \ \ )\) という形で因数分解できる
ということです。
根拠としては
- \(x^{u}-y^{u}=(x-y)(x^{u-1}+x^{u-2}y+\cdots+xy^{u-2}+y^{u-1})\)
という因数分解です。
したがって、
\(f(n+m)-f(n)\) は \((n+m)-m\), すなわち \(m\) の倍数ということになります。
(2) について
(1) において \(m=f(n)k\) とすると、ただちに証明が完了してしまいます。
(3) について
直接定数関数であるということを示すのは大変です。
そこで、大まかな路線としてまずは「背理法」を睨みたいところです。
\(f(x)\) が定数関数ではない \(N\) 次式であると仮定します。
形が複雑ですが、
\(f(整数)\) の形をしていたら、それは素数となっている
という認識が大切です。
そういう目をもって、(2) の結果である
- \(f(n+f(n)k)=f(n) \cdot M\)(\(M\) は整数)
という結果を観察してみると
\((素数)=(素数)\cdot M\)
と、素数が積の形となっていることに気が付くと思います。
つまり、このことから \(M=1\) となるしか逃げ道がないわけです。
よって
が任意の整数 \(k\) について成立することになります。
ここで、「ん？」となるでしょうか。
\(p\) を素数として、\(f(n)=p\) とおくと
\(f(n+kp)=p\)
が任意の整数 \(k\) について成立することになるわけです。
これが意味するところは
\(N\) 次方程式 \(f(x)=p\) が
\(n+p\) , \(n+2p\) , \(\cdots\)
という無数の解をもつ
ということであり、不合理です。
余談
冒頭、素数生成多項式の存在が否定されてしまったという話をしましたが、
- じゃあ、どのぐらいの割合で素数を生み出してくれるのか
といういわば素数を生み出す「確率」に注目し、出来る限りその確率を高めるためにどうすればよいかという研究も行われているようです。
解答はコチラ
