什么是质数

什么是质数 让任何人在任何地方任何时候享受最好的教育服务 什么是质数? 所谓质数或称 素数，就是一个正整数，除了本身和 1 以外并没有任何其它因子。例如 2，3，5，7 是质数，而 4，6，8，9 则不是，后者称为合成数。从这个观点可将整数分为两种，一种叫质数，一种叫合成数。(有人认为数目字 1 不该称为质数)著名的高斯「唯一分解定理」说，任何一个整数。可以写成一串质数相乘的积。 (例1) ，， ， ， ， ，这就是说，任何数都由质数构成的。 (例2) 2,(,×,)，3、5、7、11…均为质数。而,、,、,不为质数。(因为最少还有因子2) 由于质数本身的奇异性使人无法一把抓住它出现的规律，抓住它出现的特性甚至不知道它实际分布的情形。简单来说，给你一个正整数，你竟不可知道它是否是一个质数，即使你用尽了方法，证明它不可能是一个质数，但竟无法分解它，举例来说:211-1=2047 可以分解成 。267-1 呢,据说美国代数学家 Frank Neloon Cole花了三年多才发现的。自然那时「计算机时代」还未来临，只能靠无限的耐心与毅力，再加上一副长于计算数目的训练才弄得出来。但有了计算机似乎好不了多少，数目字加大了，困难依旧。1931年 D.H. Lehmar 证明了 2257-1 是一个大合成数。大～不错。它等于 231,584,178,474,632,390,847,141,970,017,375,815,706, 539,969,331,281,128,078,915,168,015,826,259,279,871 一个78位数字的大数，到目前仍未有人或计算机能分解它～ 因此，虽然知道一个数目是否质数也许没有多大用处，但仍是很有趣味，最少在找它的过程中会引起很多方法论的问。 质数的特性? ,质数除了,之外，必为奇数。(换句话说，,是最小的质数，也是唯一的偶数) ,「,」不算是质数。 ,「算术基本定理」:比,大的任何整数，必可分解为质因子的乘积，且表示的方法是唯一的。 质数的个数与求法 ,欧几里德证明了「质数必有无限个」 ,「Eratosthenes」滤套 若要求从,到n的质数，只要检查n是否可被不大于的质数整除即可。要判断,,,是否为质数，则只要检查,,,是不是可以被小于或等于,,的质数整除即可。 ,质数有没有一种特殊的型式呢, Mersenne质数:型如，若为质数时称之(但质数不一定型如， 例如就非质数。)目前已知有3, 7, 31, 127,等38个，还在寻找中… 费玛质数:型如，当n,,到,时。(但质数不一定型如，例 第 1 页 共 7 页 让任何人在任何地方任何时候享受最好的教育服务 如n=5时，非质数。) 【注】型如称为「费玛数」，而费玛质数只有3 , 5, 17 , 257 , 65537等五个。 ,可不可以用一个公式，表示出所有的质数呢, (1)欧拉::在x=0、1、2…40时，可得41个质数 (1)勒真德::在x=0、1、2…28时，可得29个质数 :在x=0、1、2…79时，可得80个质数 :在x=1、2…11000时，可得11000个质数 ?但是，没有一个多项式可表示出所有的质数 为什么要找质数 「既然质数有无限多个，那么为什么数学家要投入那么多的心力一直寻找更大的质数呢,」 简单的说，数学家就和一般人一样，「你有收藏东西的兴趣习惯吗,」「喜欢在比赛中得到名次吗,」这个都是理由之一。回答这个问题，可以用几个方向来说明， 一、这是传统～ 在公元前300年的欧几里德已经开始这个追求!他在「几何原本」中提及完全数的概念，其中和麦司尼质数产生了关联，开启了研究之门，之后大数学家如费玛、欧拉、麦司尼、笛卡尔…相继投入这个追寻的工作中。也就在寻找大的质数的过程中，对基本数论有很大的助益，因此这个寻找的传统值得被继续, 二、它的附加价值～ 因为美国的政治上的目的，才有把人送上月球的创举，但是追寻大的质数例如像麦司尼质数，对社会影响的却是持续不断的，它的副加价值在于不断促进科技的进步与人们的日常生活有用的东西材质的研发，也改进教育建设让生活更有生产力。在寻找并纪录麦司尼质数的过程中，让老师可以带领学生投入研究，这让学生将研究的精神用于工作上，让工程或科学的得以进步，当然这只是副加价的一部份而已。 三、人们喜欢美丽且稀少的物品～ 如前文提及欧几里德已经开始这个追求后，它是如此稀少(目前已知有30多个，还在寻找中)，不仅如此它也是美丽的;数学上什么叫作「美丽」,例如人们希望证明是简短、明了，而且可以绐合旧知识让你了解新的东西～而麦司尼质数的型式与证明都合符合上述的要求。 四、无上荣耀～ 运动选手为什么不断追不更高、更快、更远呢,难道是希望他们在工作上可以使用这些技巧吗,不是吧，它们都是渴望竞争，为了荣耀(to win)～险峻的峭壁和高山峻岭对于喜欢攀岩、登山的人，有无法抗拒的魅力，数学的探索也是如此，看着无法想象巨大的数字竟是质数时那种心情是相同的，因此继续寻找下一个的渴望，岂是语言可以形容, 人们当然需要务实，但是也需要好奇心和不断尝试的精神，才能而不断进步。 五、对计算机的考验～ 当计算机的发明之后，人们可以藉由计算机的计算去找麦司尼质数，因为检验一个已知的质数都要经过十亿次以上的计算才会计算出来(以计算机来算当然很快)，这时候就是测验计算机稳不稳定的好时机，Intel的Pentium处理器，就被Thomas Nicely在计算twin prime constant 第 2 页 共 7 页 让任何人在任何地方任何时候享受最好的教育服务 时，找到有bug存在。 六、了解质数分布的情形～ 虽然数学不是实验的科学，但是在我们会用例子去检验我们的猜测，当例子愈来愈多时，我们也会更了解事实，而质数的分布情形这是如此，例如高斯在看过质数表之后猜测了质数定理(prime number theorem)，这个定理在1896由哈达玛(Hadamard)及普辛(Pouusin)分别证得: 质数是自然数的一部份，有趣的是，它却与自然数的个数一样多，也有无穷多个。两千多年前，古希腊数学家就从理论上证明了这一点。不过，质数看上去要比自然数少的多。有人统计过，在1到1000之间，有168个质数;在1000到2000之间，有135个质数;在2000到3000之间，有127个质数;而在3000到4000之间，就只有120个质数了，越往后，质数就会越稀少。那么，怎样从自然数里把质数给找出来呢,公元前三世纪，古希腊数学家埃拉托塞尼(Eratosthenes)发明了一种很有趣的方法。埃拉托塞尼常把数表写在涂了白腊的木板上，遇到需要划去的数，就在那个数的位置刺一个孔;随着合数逐一被划掉，木板上变得千疮百孔，像是一个神奇的筛子，筛掉了合数，留下了质数。所以，人们将这种求质数的方法叫做“埃拉托塞尼筛法“。 1. 我们把1~100的自然数，按照顺序列成一张百数表。(如下表) 2. 首先把1划掉，因为1既不是质数，也不是合数。 3. 接下来一个数是2，它是最小的质数，应予保留。但2的倍数一定不是质数，应该全部划掉;也就是从2起，每隔1个数就划掉1个数。 4. 在剩下的数中，3是第一个未被划掉的数，它是个质数，应予保留。但3的倍数一定不是质数，应该全部划掉;也就是从3起，每隔2个数就划掉1个数。 5. 在剩下的数中，4已被划掉了，其余的数，5成为第一个未被划掉的数，它是质数，也应予以保留。但5的倍数一定不是质数，应该全部划掉;也就是从5起，每隔4个数就划掉1个数。 6.仿照步骤1,5，继续划下去，数表上最后剩下的就是1~100之间的质数了。 1 4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32 33 34 35 36 38 39 40 42 44 45 46 48 49 50 第 3 页 共 7 页 51 52 54 55 56 57 58 60 让任何人在任何地方任何时候享受最好的教育服务 埃拉托塞尼筛法 这种方法是世界上最古老的一种求质数的方法，它的原理很简单，运用起来也很方便。现在，凭着经过改进后的埃拉托塞尼筛法，数学家们已把10亿以内的质数全都筛出来了。怎样找质数呢,这个问题据说自希腊及中国周朝已有人在问这个难题了。下面是一些初步查询。 质数是无穷。这很早就证明了。因若 p1=2, p2=3, pn 是最初 n 个质数，则新数目 必由一个不等于 p1, p2, , pn 中任一个质数的新质数所除尽，故而 pn+1 存在了;且 举例说， 但 30031=59 x 509 证明了 ，不必是质数。 考虑 f(n) 形式中是否有无限个质数存在或 f(p) 中是否有无限合成数存在呢, 怎样证明 n 是一个质数呢, 传统的「筛法」是将任一个数n的可能因子查证，简化后;只要过滤所有小于的质数即可以了。就是n若是合成数，必有一个小于的质因子。如 3，5，7，11，13，等等。目前零碎地查质数的方法固然有，但仍无一万全之方。 费马的猜测 17世纪时，有个法国律师叫费马(Fermat，1601-1665)，他非常喜欢数学，常常利用业余时间研究高深的数学问题，结果取得了很大的成就，被人称之为“业余数学家之王“。费马研究数学时，不喜欢搞证明，喜欢提问题;他凭借丰富的想象力和深刻的洞察力，提出一系列重要的数学猜想，深刻地影响了数学的发展，他提出的“费马最后定理“，几百年来吸引了无数的数学家，直到1994年才由美国普林斯顿大学的怀尔斯得出证明。 他在公元1640年提出了一个公式:『 2，1』，他验算了n等于1到4的情况，发现都是质数以后(如下表)，就直接猜测只要n是自然数，这个公式求出来的一定是质数。」 n 2，1 第 4 页 共 7 页 让任何人在任何地方任何时候享受最好的教育服务 1 2，1,5(质数) 2 2，1,17(质数) 3 2，1,257(质数) 4 2，1,65537(质数) 1. 费马最喜欢的数学分支是数论，他曾深入研究过质数的性质，他发现了一个有趣的现象。计算 ,, 它是一个质数吗, 。 2. 那 又是多少呢, 它是一个质数吗, 。 3. 再下去， 是多少呢, 它是一个质数吗, 。 4. 最后， 是多少呢, 它是一个质数吗, 解答: 122，1=5;它是质数。 222，1=17;它是质数。 322，1=257;它是质数。 422，1=65537;它是质数。 费马当年并没有继续算下去，他猜测说:只要,是自然数，由这个公式 得出的数一定都是质数;这是一个很有名的猜想，由于,,5之后演算起来很麻烦，很少有人去验证它。 1732年，大数学家欧拉认真研究了这个问题，它发现费马只要再往下演算一个自然数，就会发现由这个公式得出的数不全是质数。 n5222，12，1,,5时，,,4294967297，4294967297可以分解为641×6700417，它不是质数。也就是说，费马的这个猜想不能成为一个求质数的公式。实际上几千年来，数学家们一直在寻找这样的一个公式，一个能求出所有质数的公式;但直到现在，谁也未能找到这样一个公式，而且谁也未能找到证据，说这样的公式就一定不存在;这样的公式存不存在，也就成了一个著名的数学难题。 费马在数学史上，是一位非常重要的人物，虽然费马的公式是错误的，但是数学家从另一个 第 5 页 共 7 页 让任何人在任何地方任何时候享受最好的教育服务 方向来寻找大质数，也就是之前讲完全数时提到的:『如果2-1是一个质数，那么N,2(2-1)一定是个完全数。』于是，数学家们努力验算不同的 n值，也找出了一些质数，但是由于数字太大，当时又没有计算机的帮忙，所以很多结果都是错的。到了十七世纪，一位法国的天主教修士梅森尼提出了:在 n不大于257的情况下，共有十一个质数。虽然他的结果同样有不少错误，但是后人就把『2-1』这种形式的质数叫做『梅森尼质数』。」 费马定理 费马一心想要找出一个求质数的公式，结果未能成功。人们发现，倒是他无意提出的另一个猜想，对寻找质数很有用处。 是一个质数，那么，对任何自然数,，( )一定能被 整除。费马猜测说;如果 这一回费马猜对了，这个猜想被人称作费马小定理。例如:11是质数，2是自然数，所以( )一定能被11整除。 利用费马定理，这是目前最有效的鉴定质数的方法。要判断一个数,是不是质数，首先看它能不能整除( )，如果不能整除，它一定是合数;如果能整除，它就”极可能”是质数。现在，在电子计算器上运用这种新方法，要鉴定一个上百位的数是不是质数，一般只要15秒钟就够了。 质数公式表 f(x)公式 在100以下令f(x)成合成数的x值 总数 x2-79+1601 80, 81, 84, 89, 96 5 x2+x+41 40,41,44,49, 56, 65, 76,81,82,84,87,89,91,96 14 2x2+29 29, 30, 32, 35, 39,44, 50, 57, 58, 61,63, 65, 25 72,74,76, 84,87, 88, 89,91,92,94,95, 97, 99 第 6 页 共 7 页 让任何人在任何地方任何时候享受最好的教育服务 6x2+6x+31 29, 30, 31, 34, 36,41,44, 51, 55, 59, 61, 62, 25 64,66, 69,76,80, 84, 86. 87, 88, 92, 93, 97, 99 3x2+3x+23 22,23,27, 30, 38,43, 44,45,46,49, 51, 55, 56, 59, 28 62,66,68, 69,70,78, 85, 87, 88, 89, 91,92,95,96 像质数公式 x2+x+41，我们能找到连续 40 个(由 0 到 39)的质数，有没有一条质数公式 f=x2+x+b，能使 (b-1) 个连续 x 值使 f(x) 都是质数呢,有人曾用电算机去找，结果查出如果有，则 b 值一定要超过 1,250,000,000，而且最多只有一个。看来这个问题大概解不了。 现在的数学家们在质数这个领域里，有两个重要的研究方向:一个是利用各种更有效率的筛法，不断地往更大的数里面去搜寻质数;另外就是寻找新的『梅森尼质数』。到公元1996年为止，数学家已经藉由计算机运算，知道1020以内有多少质数了;另一方面，在公元1999年六月，数学家也发现了第三十八个『梅森尼质数』: 26972593-1，这同时也是到目前为止发现的最大质数～它是一个2098960位数。 第 7 页 共 7 页