恆給素數的多項式

以往數學家希望可得到恆出素數 (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素數的多項式。那麼,當 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 的倍數,即不是素數。因而與「痤僖擘ヾv相矛盾,推翻「痤僖擘ヾv的假設。證畢。

 

看一個實例吧:

以歐拉多項式  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.

 

 

Free Web Hosting