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

　1│2│3　

完全數與莫仙尼質數（第 2 頁）

張鎮華

首頁 | 搜尋

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

‧註釋
‧對外搜尋關鍵字

莫仙尼 (Mersenne) 質數

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

前面我們曾經說過 2³ (2⁴ -1) 並不是完全數。

現在可以運用第二定理說明，因為 2⁴ -1 = 15 不是莫仙尼質數，所以 2³(2⁴ -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 為合成數時 M_p 為合成數，p 為質數時 M_p 為質數。」但是當我們試圖去證明這個敘述時，發現只有上半部才對。

定理 1
若 p 為合成數，則 M_p 為合成數。（若 M_p 為質數，則 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*}$

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

如果 M_p 是質數，而 p 不是質數。

當 p=1 時，M_p =1 不是質數。

當 p 為合成數時，M_p 亦為合成數。

兩者均和已知 M_p 為質數矛盾，所以 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}$

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

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

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

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

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

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

證：設 2^p -1 有一質因數 x=ap+b，其中 0<b<p（b 不可能 =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^{x-1} \equiv 1 \pmod{x}$ ，所以 $2^{b-1} \equiv 1 \pmod{x}$
假設 b-1>0，因質數 p>b>b-1>0，所以 p 和 b-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 越大， M_p 就越難檢驗。尤拉在1750年算出 M₁₉ 的次一莫仙尼質數 M₃₁，早期的尋找工作就算告一段落。1876年法國數學家洛克司 (Lucas) 用筆算出一個最大紀錄 M₁₂₇，這個數大達39位數，是人類用紙筆算出的12個莫仙尼數中之最大者。現在將這十二個質數列如下： 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127。

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

　1│2│3　


	（若有指正、疑問……，可以在此留言或寫信給我們。）

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

編輯：康明軒

最後修改日期：2/17/2002