オイラーの素数生成式に関する雑談記事です。
という式は の範囲で異なる40個の素数の値を与えることが知られています。これは「オイラーの素数生成(多項)式」と呼ばれる有名な二次式です。
この多項式によって得られる最初の40個の素数を列挙してみます。
|
|
1 |
41 |
2 |
43 |
3 |
47 |
4 |
53 |
5 |
61 |
6 |
71 |
7 |
83 |
8 |
97 |
9 |
113 |
10 |
131 |
11 |
151 |
12 |
173 |
13 |
197 |
14 |
223 |
15 |
251 |
16 |
281 |
17 |
313 |
18 |
347 |
19 |
383 |
20 |
421 |
21 |
461 |
22 |
503 |
23 |
547 |
24 |
593 |
25 |
641 |
26 |
691 |
27 |
743 |
28 |
797 |
29 |
853 |
30 |
911 |
31 |
971 |
32 |
1033 |
33 |
1097 |
34 |
1163 |
35 |
1231 |
36 |
1301 |
37 |
1373 |
38 |
1447 |
39 |
1523 |
40 |
1601 |
このようにオイラーの素数生成式は連続して個もの素数を与えます。 のときは となって初めて素数でなくなります。
なお、この二次式はゼロ以下の場合でも素数値を与えますが なのでが正のときを考えれば十分です( を考えることに相当するので重複しています)。
は の範囲ではその半数以上の86個のについて素数を与えます。範囲を広げて調べてみると以下の結果を得ます。
範囲 |
素数を与えるの個数 |
|
86 |
|
581 |
|
4149 |
|
31985 |
|
261081 |
|
2208197 |
|
19132652 |
この結果から、 の範囲で素数を与えるの個数をと置くと、という関係式が得られます。これは下図に示したとの間に成り立つ直線関係から求めたものです(青色折れ線はのプロット、橙色破線は原点を通る近似直線)。
図.との直線関係
ここまで多くの素数値を与えるのは定数項がの場合に特有の性質と言えます。例えば の場合、 の範囲で素数を与える整数は68個しかありません。
と置くとき、が素数になるの個数を調べると以下のようになり、に比べて明らかに少ない結果を得ます。
範囲 |
が素数になるの個数 |
|
11 |
|
68 |
|
470 |
|
3634 |
|
29525 |
|
249551 |
|
2162730 |
を素数としてを調べても、 の場合ほどは多くありません。
範囲 |
が素数になるの個数 |
|
19 |
|
126 |
|
885 |
|
6850 |
|
55791 |
|
472233 |
|
4092968 |
試しに多項式 について の値を~までで色々変え、 の範囲で素数を与えるの個数を調べてみると、上位10位は下の表のようになります。
|
素数を与えるの個数 |
41 |
31985 |
941 |
25445 |
671 |
25290 |
107 |
25162 |
227 |
24658 |
101 |
24549 |
221 |
24305 |
881 |
24270 |
857 |
23911 |
587 |
23786 |
のときに飛び抜けて多いという結果になりました。
多項式について、が、、、、、のとき、 の自然数を代入すると素数になることが知られており、これらの素数をまとめて “Lucky numbers of Euler”「オイラーの幸運数」と呼びます。しかし、 の場合について、より大きなについてもが多数の素数値を与えることはあまり知られていないように思います。
きいねく氏によれば、ウラムの螺旋に類するのプロットを描くと以下のようになるそうです。 の場合は特に黒く塗り潰されており、より広範囲のについても素数になっていることが視覚的に理解できます。これはなかなか興味深い性質です。
定数項が特定の数の場合に多項式が多数の素数を与える現象は「ヘーグナー(Heegner)数」との関係が深いことが背景にありますが、難解なのでここでは詳しく立ち入りません。興味のある方はtsujimotter氏の「オイラーの素数生成多項式の秘密」のページを参考にして下さい。2次体、類数、ラビノヴィッチの定理などについても併せて調べてみると良いでしょう。
2020年の奈良教育大学の入試に次のような問題が出題されています。
以下の問に答えよ。
(1)を自然数とするとき、 はの倍数であることを証明せよ。
(2)次の命題が真または偽であることを示せ。
「を自然数とするとき、は素数である。」
2020年奈良教育大学 前期(数学教育専修) 第1問
(2)の式はまさにオイラーの素数生成式そのもので、 を代入すれば命題が偽であることが示されます。
昔、慶応大学の数学に多項式がすべての整数について素数ならは定数関数であることを証明させる問題が出題されていたと記憶しています。この事実を何となく知っているだけでも二次式が常に素数になることは無さそうだと判断できます。一方でを自然数としてという形で表せる素数(オイラー素数)が無数に存在するかどうかは知られていない(恐らく無数に存在するでしょうが証明されていない)ように思います。
また、過去には国際数学オリンピック(IMO)にもオイラーの素数生成式が登場したことがあります。
Let be an integer. Prove that if is prime for all integers such that , then is prime for all integers such that .
IMO 1987, Day 2, Problem 6(キューバ大会)
本問は「を自然数として と置くとき、がすべて素数であれば、はすべて素数であることを示せ。」と読み替えられます。
が合成数になるような以上 以下の整数が存在するとして、を割り切るような最小の素数を仮定して矛盾を導く、という方法で証明されます。
これを定理として使えば、例えば について、、、、が素数になるので残りの~も素数になることが従います。また、 の場合は となり素数でないので素数生成式に該当しないことが直ちに分かります。
ところで、 となりますが、これらの素因数はいずれもの素数値として得られるものであり、ここから何らかの規則性が見出せそうにも思われます。
しかし、となりの値として登場しない素因数が現れるので、これは単なる思い違いのようです。
そもそもから得られる整数を素因数分解したときに未満の素因数が現れることはないので、小さめのに対してが与える素数値との素因数分解に現れる素数が少し似ているように見える、というだけのことです。
なお、下線部の事実は各素数を法とする剰余類を調べることで示されます。素数についてとなるので の範囲で調べれば十分です。いま、 の範囲のすべての整数に対しては以上の素数となるので、が以下の素数で割り切れることはありません。したがって、任意の整数に対しては未満の素因数を含むことはありません。当然ですが、素数だけでなく~までの整数についても同様にを割り切らないことが言えます。
(参考:素数一覧表)
「f[41](n)=n^2-n+41の値に41未満の素因数が現れることはない」
ことを示すには,
「各素数を法とする剰余類を調べる」わけですが,
その手続きは,(個別に1つずつ行うとすればかなり大変ですが,そうでなければ)
さほど煩雑な計算はしないで完結しますし,
明記しておく方がよさそうな気がします.
言わずもがなですが,以下のようになりますね.
[1]
f[41](n) (n=0,1,2,…,40)はすべて素数であり,41未満のものはないので,
どれも,41未満の素数pで割った余りは0ではない.
[2]
f[41](n+p)とf[41](n)は,pで割った余りは等しい.
よって,nをpで割った余りが定まれば,f[41](n)をpで割った余りは定まる.
[3]
p<41だから,任意の自然数は,
0,1,2,…,40の少なくとも1つとpで割った余りが等しい.
以上[1],[2],[3]より,f[41](n)は,41未満の素数pで割り切れることはない.
たけちゃん さん
コメントありがとうございます。
仰る通り、各素数について個別に論じる必要はありませんね。
簡単にですが加筆しました。ご指摘ありがとうございます。