神奇的“質(zhì)數(shù)篩”

林革

翻閱日歷，品玩數(shù)字。靈感，有時(shí)就誕生于這無聊，卻成就于認(rèn)真。

眾所周知，一個(gè)大于1的整數(shù)，如果除了它本身和1以外，不能被其他正整數(shù)所整除，這個(gè)整數(shù)就是質(zhì)數(shù)（也稱素?cái)?shù)），如2，3，5，7，11等都是質(zhì)數(shù)。在自然數(shù)列中，因?yàn)橄薅ㄇ疤岷吞卣鞯木壒剩|(zhì)數(shù)顯得稀少且特別。古往今來，許多數(shù)學(xué)家都致力于尋找質(zhì)數(shù)，其方法可謂多種多樣。

“埃拉托斯特尼篩”

公元前3世紀(jì)，古希臘學(xué)者埃拉托斯特尼提出的著名“篩法”就非常具有代表性。他在一塊涂蠟的板上依次寫上自然數(shù)列的數(shù)字，將蠟板固定在一個(gè)框上，把其中的1及合數(shù)一個(gè)個(gè)挖去，就得到一個(gè)像篩子一樣有許多小孔的東西，其中留下的數(shù)就是質(zhì)數(shù)，這張數(shù)表被稱為“埃拉托斯特尼篩”。埃拉托斯特尼是怎樣“篩”質(zhì)數(shù)的呢？他的具體做法如下：

把n個(gè)自然數(shù)按次序排列起來;

1不是質(zhì)數(shù)，也不是合數(shù)，要?jiǎng)澣?

2是質(zhì)數(shù)，留下來，而把2后面所有2的倍數(shù)都劃去;

2后面第一個(gè)沒劃去的數(shù)是3，把3留下，再把3后面所有3的倍數(shù)都劃去;

3后面第一個(gè)沒劃去的數(shù)是5，把5留下，再把5后面所有5的倍數(shù)都劃去;

……

這樣一直做下去，就會(huì)把不超過n的全部合數(shù)都篩掉，留下的就是不超過n的全部質(zhì)數(shù)。

例如：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

用“埃拉托斯特尼篩”可以找出不超過30的質(zhì)數(shù)有：2，3，5，7，11，13，17，19，23，29，共10個(gè)。

有人統(tǒng)計(jì)過：在1到1000之間，有168個(gè)質(zhì)數(shù);在1000到2000之間，有135個(gè)質(zhì)數(shù);在2000到3000之間，有127個(gè)質(zhì)數(shù);而在3000到4000之間，就只有120個(gè)質(zhì)數(shù)了?？傊?，越往后質(zhì)數(shù)就越稀少。這種方法是世界上最古老的求質(zhì)數(shù)的方法。它原理簡單，運(yùn)用起來很方便。現(xiàn)在，憑借經(jīng)過改進(jìn)后的“埃拉托斯特尼篩”，數(shù)學(xué)家們已經(jīng)把10億以內(nèi)的質(zhì)數(shù)都篩出來了。

“辛答拉姆篩法”

4 7 10 13 16 19 …

7 12 17 22 27 32 …

10 17 24 31 38 45 …

13 22 31 40 49 58 …

16 27 38 49 60 71 …

……

1934年，也就是“埃拉托斯特尼篩”問世兩千多年后，一位年輕的印度學(xué)生辛答拉姆創(chuàng)造了上表，表中數(shù)的排列規(guī)律是：第一行（最上層橫著數(shù)）和第一列（最左邊豎著數(shù)）的數(shù)是相同的，在這一行（列）中，從第二個(gè)數(shù)起，每一個(gè)數(shù)與前一個(gè)數(shù)相差3，例如7-4 = 10-7 = 13-10 = 16-13 = … = 3;在第二行（列）中，從第二個(gè)數(shù)起，每一個(gè)數(shù)與前一個(gè)數(shù)相差5;在第三行（列）中，從第二個(gè)數(shù)起，每一個(gè)數(shù)與前一個(gè)數(shù)相差7;在第四行（列）中，從第二個(gè)數(shù)起，每一個(gè)數(shù)與前一個(gè)數(shù)相差9;在第五行（列）中，從第二個(gè)數(shù)起，每一個(gè)數(shù)與前一個(gè)數(shù)相差11。3，5，7，9，11，13……相信你根據(jù)這樣的規(guī)律也能接著寫出第六行、第七行……

不過，辛答拉姆的發(fā)現(xiàn)遠(yuǎn)比此深刻，并且其數(shù)學(xué)意義重大。他從中發(fā)現(xiàn)并證實(shí)了一個(gè)極為奇特有趣的現(xiàn)象：在這個(gè)表中，隨便找一個(gè)自然數(shù)M，那么2M+1一定不是質(zhì)數(shù)。

例如：M = 4，2M+1 = 2 × 4+1 = 9，9不是質(zhì)數(shù);M = 31，2M+1 = 2 × 31+1 = 63，63也不是質(zhì)數(shù);如此等等。反過來，隨便找一個(gè)表中沒有的自然數(shù)M，則2M+1一定是質(zhì)數(shù)。

例如：M = 11，11不在表中，2M+1 = 2 × 11+1 = 23，23的確是質(zhì)數(shù); M = 23，23不在表中，2M+1 = 2 × 23+1 = 47，47也是質(zhì)數(shù);如此等等。

辛答拉姆猜想：若自然數(shù)M出現(xiàn)在這個(gè)表中，則2M+1不是質(zhì)數(shù);若自然數(shù)M不出現(xiàn)在這個(gè)表中，則2M+1是質(zhì)數(shù)。辛答拉姆極為精彩地證明了這個(gè)猜想。

他寫出第n行的第一個(gè)數(shù)是4+（n-1） × 3 = 3n+1，此行是公差為2n+1的等差數(shù)列，所以此行第m列的數(shù)是（3n+1）+（m-1）（2n+1） = 2（m+1）n+m;設(shè)N是第n行第m列的數(shù)，則N = （2m+1）n+m，于是2N+1 = 2[（2m+1）n+m]+1 = 4mn + 2n + 2m + 1 = 2m（2n + 1） + （2n + 1） = （2m+1）（2n+1），顯然它是個(gè)合數(shù)。再設(shè)N不在上表中，現(xiàn)在必須2N+1是質(zhì)數(shù)。辛答立姆采用反證法，即證明“若2N+1不是質(zhì)數(shù)，則N必在表中”，這與原命題等價(jià)，并且最重要的是證明起來相對要容易得多。事實(shí)上，若2N+1不是質(zhì)數(shù)，則有2N + 1 = x·y（x，y為整數(shù)），因?yàn)?N+1為奇數(shù)，則可推知x，y也必為奇數(shù)。不妨設(shè)x = 2p+1，y =? 2q + 1，從而有2N+l = （2p+1）（2q+1），對照上面“N是表中的第n行第m列的數(shù)，則2N+1 = （2m+1）（2n+1）”的結(jié)論，可確定這里的N表示的是表中第p行第q列的數(shù)。由此，人們確信這是尋找質(zhì)數(shù)的又一個(gè)獨(dú)特而有效的方法，它被稱為“辛答拉姆篩法”。

這兩種“質(zhì)數(shù)篩”都從一個(gè)側(cè)面反映出：研究質(zhì)數(shù)在自然數(shù)列中的分布一直是數(shù)論最重要和最有吸引力的中心問題之一。