質數 (第 2 頁)

　1│2│3│4　

質數（第 2 頁）

唐文標

首頁 | 搜尋

．原載於數學傳播第四卷第四期
．作者當時任教於英國劍橋大學
‧對外搜尋關鍵字

(二)找質數

怎樣找質數呢？這個問題據說自希臘及中國周朝已有人在問這個難題了。下面是一些初步查詢。

質數是無窮。這很早就證明了。因若 p₁=2, p₂=3, $\cdots\cdots$ p_n 是最初 n 個質數，則新數目 $p_1\times p_2\times \cdots\cdots \times p_n+1$ 必由一個不等於 p₁, p₂, $\cdots\cdots$ , p_n 中任一個質數的新質數所除盡，故而 p_n+1 存在了；且

$\begin{displaymath}p_n<p_{n+1}\leq p_1\times p_2 \times \cdots\cdots \times p_{n+1} \end{displaymath}$

舉例說，

$\begin{eqnarray*} 2+1&=&3,\\ 2\times 3+1&=&7\\ 2\times 3\times 5+1&=&31\\ 2\t... ...&=&2311\\ 2\times 3\times 5\times 7\times 11\times 13+1&=&30031 \end{eqnarray*}$

但

30031=59 x 509

證明了 $p_1\cdots\cdots p_n+1$ ，不必是質數。

考慮

$\begin{displaymath}f(n)=p_1\times\cdots\cdots\times p_n+1 \end{displaymath}$

f(n) 形式中是否有無限個質數存在或 f(p) 中是否有無限合成數存在呢？

怎樣證明 n 是一個質數呢？

傳統的「篩法」是將任一個數n的可能因子查證，簡化後；只要過濾所有小於 $\sqrt{n}$ 的質數即可以了。就是n若是合成數，必有一個小於 $\sqrt{n}$ 的質因數。如 3，5，7，11，13， $\cdots\cdots$ 等等。目前零碎地查質數的方法固然有，但仍無一萬全之方。Fermat曾有一平方法，如下：因 $N=u\cdot v=(x-y)(x+y)=x^2-y^2$ ，可取 x=t+k, $y=\sqrt{(t+k)^2-N}$ , t²，大過 N 的平方。例：N=931，則 t²=31,32,33,34, $\cdots\cdots$ , (34)²=1156 是最小而令 $y=\sqrt{1156-931}=15$ 可開平方成整數。因而 x=34, y=15，即 u=19,v=49，即 N=931=19 x 49，即是一個合成數。

　1│2│3│4　


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

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

編輯：朱安強

最後修改日期：4/26/2002