上頁 123 次頁

完全數與莫仙尼質數 (第 2 頁)

張鎮華

 

首頁 | 搜尋

.原載於科學月刊第二卷第三期
.作者當時任教於中央數學系

註釋
對外搜尋關鍵字
 
莫仙尼 (Mersenne) 質數

尋找偶完全數的工作,到此變成,決定 2n -1 是否為質數的工作。尋求具有特別型式 Mp = 2p -1 的質數,最早以法國數學家(Marin Mersenne, 1588∼1648)算出最多,故我們用他名字稱呼此等質數,叫莫仙尼質數。

前面我們曾經說過 23 (24 -1) 並不是完全數。

現在可以運用第二定理說明,因為 24 -1 = 15 不是莫仙尼質數,所以 23(24 -1) 不是偶完全數。

\begin{displaymath}
\begin{array}{l}
M_2 = 2^2 -1 = 3 \mbox{ {\fontfamily{cwM1}\...
...ontfamily{cwM1}\fontseries{m}\selectfont \char 98}}
\end{array}\end{displaymath}

觀察上面的例子,可以看出一個可能的通性,或許「p 為合成數時 Mp 為合成數,p 為質數時 Mp 為質數。」但是當我們試圖去證明這個敘述時,發現只有上半部才對。

定理 1
p 為合成數,則 Mp 為合成數。 (若 Mp 為質數,則 p 為質數。)

證: p 為合成數,所以存在二個整數 a,b, 使得 p = ab , 1 < a , b < p ,

\begin{eqnarray*}
M_p &=& 2^p -1 = 2^{ab} -1 \\
&=& (2^a -1 )[(2^a)^{b-1} + (2^a)^{b-2} + \cdots + (2^a) +1 ]
\end{eqnarray*}


因為 $2^a -1 \geq 2^2 -1 =3 $,又

\begin{eqnarray*}
\lefteqn{ (2^a)^{b-1} + (2^a)^{b-2} + \cdots + (2^a) + 1 } \\
&\geq& (2^a)^{2-1}+1 = 2^a +1 >1
\end{eqnarray*}


所以 Mp 可以分解為兩個大於 1 的整數的積,必定為合成數。

如果 Mp 是質數,而 p 不是質數。

p=1 時,Mp =1 不是質數。

p 為合成數時,Mp 亦為合成數。

兩者均和已知 Mp 為質數矛盾,所以 p 為質數。

利用這個定理,當我們要尋找莫仙尼質數時,可以不必計算 p 為合成數時的情形。 但是很不幸的是,這個定理的逆命題不成立,任你如何也證不出來,事實上,

\begin{displaymath}
\begin{array}{l}
M_2 =3, \; M_3 = 7, \; M_5 = 31, \; M_7 = 127,  [3]
M_{11} = 2047 = 23 \times 89
\end{array}\end{displaymath}

M11 是第一個和我們搗蛋的傢伙,於是我們的實驗工作, 不得不繼續做下去,

\begin{displaymath}
M_{13} = 8191, \; M_{17} = 13,1071, \; M_{19} = 52,4287
\end{displaymath}

奇怪的是,得到的三個又全是質數。這些數目的位數越來越多, 驗證工作也就顯得不容易。 在初等數論埵釣潃茤w理可以幫助我們檢查一個數是不是質數。

定理2
大於 1 的整數必定有質因數。

定理3
如果整數 A 有合成數,必定有小於或等於 $ \sqrt{A}$ 的質因數。

定理 2 提供我們檢查一個數是否質數的方法: 用小於 A 的一切質數去試驗,如果這些數都不是 A 的因數,那麼 A 就是質數了。 定理 3 更方便,我們只要用小於 $ \sqrt{A}$ 的一切質數去試驗,就能決定 A 是不是質數。但是,即使使用這種方法,要算出 M19 是質數,已經十分不容易,於是又有下面的定理。

定理4
p 為質數,則 Mp 的質因數必呈 ap+1 的型式,其中 a 為正整數。

證: 設 2p -1 有一質因數 x=ap+b,其中 0<b<pb 不可能 =0
$2^p \equiv 1 \pmod{x}$

\begin{eqnarray*}
2^{x-1} & \equiv & 2^{ap+b-1} \equiv (2^p)^a \cdot 2^{b-1} \\
& \equiv & 2^{b-1} \pmod{x}
\end{eqnarray*}


根據費瑪定理 2 $2^{x-1} \equiv 1 \pmod{x}$,所以 $2^{b-1} \equiv 1 \pmod{x}$
假設 b-1>0,因質數 p>b>b-1>0,所以 pb-1 互質。
存在兩個正整數 α 和 β 使得,

\begin{displaymath}
\alpha p = \beta (b-1) +1 \quad \mbox{{\fontfamily{cwM1}\fontseries{m}\selectfont \char 67}} \quad a(b-1) = \beta p+1
\end{displaymath}

$\alpha p = \beta(b-1) +1$ 時,

\begin{displaymath}
2^{\alpha p} \equiv 2^{\beta(b-1)+1} \equiv (2^{b-1})^\beta \cdot 2 \equiv 2 \pmod{x}
\end{displaymath}


\begin{displaymath}
2^{\alpha p} \equiv (2^p)^\alpha \equiv 1 \pmod{x} \;
\Longr...
...us0.1pt{\fontfamily{cwM7}\fontseries{m}\selectfont \char 101}}
\end{displaymath}

同樣地,當 $a(b-1) = \beta p + 1$ 時也矛盾。 因此 b-1=0,即 b=1 本定理得證。

利用這個定理,檢驗工作又減輕不少。但是莫仙尼質數是呈幾何級數增大,當 p 越大, Mp 就越難檢驗。尤拉在1750年算出 M19 的次一莫仙尼質數 M31, 早期的尋找工作就算告一段落。1876年法國數學家洛克司 (Lucas) 用筆算出一個最大紀錄 M127, 這個數大達39位數,是人類用紙筆算出的12個莫仙尼數中之最大者。 現在將這十二個質數列如下: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127。

再下去的數越來越大,不是人類有限的精力所能擔當得了的。尤其莫仙尼質數的密度(density) 越來越小,要找到確實不容易。晚近電子計算機創造,計算能力逐日改良,使得這項工作得以繼續下去。 最新的資料顯示,到目前為止,我們找到23個莫仙尼數,最大的一個是 M11213,居然高達3375位。

   

上頁 123 次頁

回頁首
 
(若有指正、疑問……,可以在此 留言寫信 給我們。)
EpisteMath

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有


編輯:康明軒 最後修改日期:2/17/2002