书城教材教辅必懂的数学知识
10654300000042

第42章 费尔马小定理

17世纪时,有个法国律师叫费尔马。他非常喜欢数学,常常利用业余时间研究高深的数学问题,结果取得了很大的成就,被人称为“业余数学家之王”。

费尔马研究数学时,不喜欢搞证明,喜欢提问题。他凭借丰富的想像力和深刻的洞察力,提出了一系列重要的数学猜想,深刻地影响了数学的发展。他提出了“费尔马大定理”,几百年来吸引了无数的数学家,是一个至今尚未完全解决的著名数学难题。

费尔马最喜欢的数学分支是数论。他曾深入研究过质数的性质。1640年,他发现了一个有趣的现象:

当n=1时,22n+1=221+1=5;

当n=2时,22n+1=222+1=17;

当n=3时,22n+1=223+1=257;

当n=4时,22n+1=224+1=65537;

费尔马没有继续算下去,他猜测说:只要n是自然数,由这个公式算出的数一定都是质数。

这是一个很有名的猜想。由于演算起来很麻烦,很少有人去验证它。1732年,大数学家欧拉认真研究了这个问题。他发现,费尔马只要往下演算一个自然数,就会发现由这个公式算出的数不全是质数。

n=5时,22n+1=225+1=4294967297,

4294967297可以分解成641×6700417,它不是质数。也就是说,费尔马的这个猜想不能成为一个求质数的公式。

实际上,几千年来,数学家们一直在寻找这样一个公式,一个能求出所有质数的公式。但直到现在,谁也未能找到这样一个公式。而且谁也未能找到证据,说这样的公式就一定不存在。这样的公式究竟存在不存在,也就成了一个著名的数学难题。

费尔马有心找出一个求质数的公式,结果未能成功,人们发现,倒是他无意提出的另一个猜想,对寻找质数很有用处。

费尔马猜测说:如果P是一个质数,那么,对于任何自然数n,np-n一定能够被P整除。这一回,费尔马猜对了。这个猜想被人称做费尔马小定理。例如11是质数,2是自然数,所以211-2一定能被11整除。

如果反过来问:若n能够整除2n-2,n是否一定就是质数呢?

答案是否定的。但人们发现,由这个公式算出的数绝大多数是质数。有人统计过,在1010以内,只要n能整除(2n-2),则n有99.9967%的可能是质数。这样,只要能剔除为数极少的冒牌质数,鉴定一个数是不是质数也就不难了。

利用费尔马小定理,这是目前最有效的鉴定质数的方法。要判断一个数的n是不是质数,首先看它能不能被(2n-2)整除,如果不能整除,它一定是合数;如果能整除,它就极有可能是质数。有消息说,在电子计算机上运用这种新方法,要鉴定一个上百位的数是不是质数,一般只要15秒钟就够了。