主题：【文摘】鉴别质数的方法 -- 别离歌

　　质数的存在是一回事，鉴别质数又是另外一回事。鉴别质数是十分令人头痛的问题。一个人人皆知的办法，是把所有可能的质因子，一一拿去试除。不过，这里也有窍门：假定N是一个合数，数A是它的最小质因子。我们只要对不大于N的平凡根的质因子逐一试除就行了。

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

　　　　　　　　N＝10000000000000001

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

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

　　公元1640年，法国著名数学家费尔马（Fermat，1601～1665）在给他朋友的一封信中，声称发现了一个定理：即若P为质数，则对任何正整数a，（a^p－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为质数，则（a^P－a）必能整除P。那么，反过来，若a^P－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，它不是质数！

　　不过，应当指出，能整除2^n－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年。这表明，在百亿之内，且（2^n-2）能被n整除的那数中，质数占99.9967％，只有不足0.004％的数是合数。一般地，假质数与质数的比约为三万分之一。

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

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

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

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

　　　　　　　　561＝3×11×17

　　目前已知最大的一个是：

　　　　　　　　443656337893445593609056001

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

它最好的地方就是不需要什么工业基础，不过我国现在的基础学科好像不强。

老一辈的故去了，年轻的急功近利，耐不住寂寞，出去后都转行做计算机挣钱去了，所以现在国内数学界能拿得出手的人才真没几个。

不要看现在论文啊、SCI啊搞得挺热闹，论水平来说还真不如文化大革命前的那段时期。

我一直觉得，中国的传统文化对基础科学、自然科学的是一种抑制，是不是因为这个造成了中国基础科学的薄弱呢？