鉴别质数的方法

质数的存在是一回事，鉴别质数又是另外一回事。鉴别质数是十分令人头痛的问题。一个人人皆知的办法，是把所有可能的质因子，一一拿去试除。不过，这里也有窍门：假定 N 是一个合数，数 A 是它的最小质因子。令 N＝A·B，则

∵N＝A·B≥A ²

∴ N≥A

这表明我们只要对不大于 N的质因子逐一试除就行了！

即使这样，试除工作也是繁重而费事的。举例说，要鉴定以下的数是否质数：

需要试除

N＝10000000000000001

N≈10⁸ 以内的质数，这样的质数共有5761455个，倘若一一

试过，则不知要试到何年何月？更不用说要判定位数更大的数了！因此，如何快速鉴别质数，便成为向人类智慧挑战的最简单同时又最困难的一个数学问题！

数世纪以来，许多数学家为寻求快速鉴定质数的方法绞尽了脑汁。

公元 1640 年，法国著名数学家费尔马（Fermat，1601～1665）在给他朋友的一封信中，声称发现了一个定理：即若 P 为质数，则对任何正整数 a，

（ap－a）一定能被 p 整除。不过当时费尔马没有给出证明，这一命题的证明， 是由一个世纪之后瑞士数学家欧拉作出的。

下面是这个定理的一些简单例子：

213-2＝8190＝13×630

311-3＝177144=11×16104

57-5＝78120＝7×11160

⋯⋯ ⋯⋯

这里似乎需要提到一段历史上的公案。本世纪 20 年代欧洲的一些学者， 例如迪克森等人，在论述数的历史的时候，曾经说道：早在孔丘时代（春秋时期，距今约 2500 年）中国人就知道“若 P 为质数，则 2P-2 能为 P 整除” 的规律，众所周知，这是上述费尔马定理的特例。后来，人们查证了这种说法的出处，原来均来源于公元 1897 年，一位名叫琼斯的大学生的一篇短文。在这篇短文的末尾，有一则奇怪的附注。附注说：“威妥玛爵士的一篇论文认为，早在孔丘时代就已有过这个定理，并且（错误地）说，如果 P 不是质数，则此定理不成立。

那么，威妥玛爵士的文章又是依据什么呢？原来是依据中国古代数学名著《九章算术》中的一段论述：

“可半者半之，不可半者副置分母分子之数，以少减多，更加减损，求其等也！”

这一段令人迷惑难懂的文言文，实际上说的是辗转相除。这一方法曾以古希腊数学家欧几里得名字命名，然而由于西方的汉学家，对于中国古文理解的艰难，致使出现了理解上的差错！不过，中国的数学史家，对此始终抱着实事求是的态度。他们在论述《九章算术》时，从来没有提到如同威妥玛

爵士所讲的那种“辉煌成就”！

可是，近来有些非数学史的书上，以讹传讹，又从国外一些文献中，把迪克森等人的观点捡了回来，并作为我们国家的“世界之最”加以宣扬。作为炎黄子孙，我们自然希望，早在 2500 年前，我们的某位祖先，已经显示出

如伺 17 世纪的费尔马那样的数学才华。但是，对史实的牵强附会，无疑是与科学相违背的！

现在回到前面讨论的课题上来。我们讲过，若 P 为质数，则（aP－a）必能整除 P。那么，反过来，若 aP－a 能被 P 整除，P 是质数吗？对这个费尔马定理的逆命题，在做了许多尝试，并没有发现它是不成立的之后，人们倾向于认为这是一条真理！

不料，到了公元 1830 年，一位不愿意公开自己姓名的德国作者，撰文对此命题予以否定！他举出了一个反例：

当 n＝341 时2341－2＝2×（2340－1）

＝2×（210－1）（2330＋2320＋2310＋⋯＋1）

＝2×3×341×（2330+2320+2310+⋯＋1）

而 341＝11×31，它不是质数！

不过，应当指出，能整除 2n－2 的 n，几乎都是质数。像 341 那样混迹其中的合数是极少的。

公元 1909 年，巴拉切维兹证明了在 2000 之内，诸如 341 那样鱼目混珠的合数（通称假质数）只有 5 个，占 0.25％，它们是：

341=11×31； 561＝3×11×17

1387=19×73； 1729＝7×13×19

1905＝3×5×127

随后，人们又陆续找到了一些超过 2000 的假质数，例如：

2407＝23×89； 2701=37×73

4369＝17×257； 4681＝31×151

10261＝31×331；⋯⋯

假质数比起真质数来，真是凤毛麟角，少得可怜！在一百亿之内的质数有 455052512 个，而假质数只有 14884 年。这表明，在百亿之内，且（2n-2） 能被 n 整除的那数中，质数占 99.9967％，只有不足 0.004％的数是合数。一般地，假质数与质数的比约为三万分之一。

这样一来，2n－2 能否被 n 整除，便可作为鉴定数 n 是否是质数的相当可靠的办法。如果 2n－2 不能被 n 整除，那么 n 一定是合数；否则 n 要么是质数，要么是假质数。剔除为数极少的假质数，所剩的便是真质数了！

公元 1980 年，两位欧洲数学家，根据上面的思路，终于找到了一种最新的质数鉴定法。应用这种方法，一个一百位质数的鉴定，过去需要几万年， 现在只需几秒种！

有趣的是，在假质数中还有这样的一类，它们不仅能够整除 2n－2，而且还能整除

3n-3；4n-4；5n-5； ⋯⋯

这样的假质数，我们称为“绝对假质数”，其中最小的一个是

561＝3×11×17

目前已知最大的一个是：

443656337893445593609056001

它在绝对假质数中排行第 685，是 1978 年发现的！