费马公式
质数没有负的 所谓质数或称素数,就是一个正整数,除了本身和 1 以外并没有任何其他因子.例如 2,3,5,7 是质数,而 4,6,8,9 则不是,后者称为合成数.从这个观点可将整数分为两种,一种叫质数,一种叫合成数.(有人认为数目字 1 不该称为质数)著名的高斯「唯一分解定理」说,任何一个整数.可以写成一串质数相乘的积. (例1) ,, , , , ,这就是说,任何数都由质数构成的. (例2) 2=(1×2),3,5,7,11…均为质数.而4,6,8不为质数.(因为最少还有因数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位数字的大数,到目前仍未有人或电脑能分解它! 因此,虽然知道一个数目是否质数也许没有多大用处,但仍是很有趣味,最少在找它的过程中会引起很多方法论的问题. 质数的特性 1质数除了2之外,必为奇数.(换句话说,2是最小的质数,也是唯一的偶数) 2「1」不算是质数. 3「算术基本定理」:比1大的任何整数,必可分解为质因数的乘积,且表示的方法是唯一的. 质数的个数与求法 1欧几里德证明了「质数必有无限个」 2「Eratosthenes」滤套 若要求从2到n的质数,只要检查n是否可被不大於的质数整除即可.要判断313是否为质数,则只要检查313是不是可以被小於或等於17的质数整除即可. 3质数有没有一种特殊的型式呢 Mersenne质数:型如,若为质数时称之(但质数不一定型如, 例如就非质数.)目前已知有3, 7, 31, 127,等38个,还在寻找中… 费玛质数:型如,当n=0到4时.(但质数不一定型如,例 如n=5时,非质数.) 【注】型如称为「费玛数」,而费玛质数只有3 , 5, 17 , 257 , 65537等五个. 4可不可以用一个公式,表示出所有的质数呢 (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时,找到有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之间的质数了. 埃拉托塞尼筛法 这种方法是世界上最古老的一种求质数的方法,它的原理很简单,运用起来也很方便.现在,凭著经过改进后的埃拉托塞尼筛法,数学家们已把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 1 2+1=5(质数) 2 2+1=17(质数) 3 2+1=257(质数) 4