恆給素數的多項式
以往數學家希望可得到恆出素數 (Prime Number) 的公式，而在眾多算式中，最為人所認識的必定是 n2 - n + 41 ，這是瑞士數學家歐拉 (Leonhard Euler 1707-1783) 於 1772 年提出的，這多項式 (Polynomial) 在 n = 0 至 39 中一連給出 40 個素數。數學家努力的從多項式中找尋一條素數的通式：即給定所有整數，輸出的值全是素數的公式，可惜結果是失敗的。但這反過來使人們認識了不同種類的素數，現在讓我們看看部份產生素數的多項式吧！
多項式 |
可連續給出素數的範圍 |
斯洛恩數列 |
素數值 |
36n2 - 810n + 2753 |
[0,44] |
2753, 1979, 1277, ..... , 52253 |
|
47n2 - 1701n + 10181 |
[0,42] |
8527, 6967, 5501, ..... , 19447 |
|
n2 - n + 41 |
[0,39] |
41, 43, 47, ...... , 2797 |
|
2n2 + 29 |
[0,28] |
29, 31, 37, ...... , 1597 |
|
n2 + n + 17 |
[0,15] |
17, 19, 23, ...... , 257 |
|
4n2 + 4n + 59 |
[0,13] |
59, 67, 83, ...... , 787 |
|
2n2 + 11 |
[0,10] |
13, 19, 29, ...... , 211 |
|
n3 + n2 + 17 |
[0,10] |
19, 29, 53, ...... , 1117 |
上表的數式只列取連續給出素數的部份 n 值，在該範圍以外的也存有素數。
數學家黑格納 (K. Heegner) 對 n2 - n + p (其中 p 為素數) ，這個名為歐拉多項式 (Euler's Polynomial) 的型式作深究，找出一些素數 p 可使該歐拉多項式中 n= 0 至 p-2 給出素數值，這些素數被稱為歐拉的幸運數 (Lucky Numbers of Euler)，包括 2, 3, 5, 11, 17, 41 六個數，所以歐拉多項式是同類多項式中的最佳的。
是否有多項式可使代入任何的 x 值都會給出素數呢？
答案是沒有，其實早在 1752年，普魯士數學家哥德巴赫 (Christian Goldbach 1690-1764) 證明了沒有一條以整數為系數的多項式，即 整多項式 (Integral Polynomials) 可給出所有的值皆為素數。其後法國數學家勒讓德 (Adrien-Marie Legendre 1752-1833) 更證明沒有 有理多項式 (Rational Polynomials) 可常給素數。讓我們看看為什麼吧。
我們可以用反證法 (Proof by Contradiction) 來證明這一點：
倘若能找到一條恒給出素數的多項式。那麼，當 x = m 時便得一素數 P，而且，
P = a + bm + cm2 + dm3 + ......
同時，取 x = m + nP 時，又可得另一素數 Q，而且，
Q = a + b ( m + nP ) + c ( m + nP )2 + d ( m + nP )3 + ......
但是，若把上式展開，我們得：
b ( m + nP ) = bm + (含有 P 的項)
c ( m + nP )2 = cm2 + (含有 P 的項)
d ( m + nP )3 = dm3 + (含有 P 的項)
......
因此，Q = a + bm + cm2 + dm3 + .... + (含有 P 的項) = P + (含有 P 的項)，
但所謂「含有 P 的項」亦即是「P 的倍數」。因此 Q 是 P 的倍數，即不是素數。因而與「恒給素數」相矛盾，推翻「恒給素數」的假設。證畢。
看一個實例吧：
以歐拉多項式 n2 - n + 41 為例，代 n = 1，得素數 41。若代 1 + 41m，如 42、83、124 等，答案便是合數了：
取 n = 42，多項式值為 1763 = 41 * 43 ； 取 n = 83，得值 6847 = 41 * 167；取 n = 124，得值 15293 = 41 * 373 等。
沒有恆給素數的多項式，但有沒有部分給出素數的多項式呢？哪樣的輸入會得出素數的輸出呢？似乎成了數學家的新一目標來。
參考文獻及網址：
Weisstein, E. W. "Prime-Generating Polynomial." From MathWorld http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html.
