费尔马小定理

41.费尔马小定理

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

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

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

当n＝1时，2²n＋1＝2²1＋1＝5；　

当n＝2时，2²ⁿ＋1＝2²²＋1＝17；

当n＝3时，2²n＋1＝2²3＋1＝257；

当n＝4时，2²ⁿ＋1＝2²⁴＋1＝65537；

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

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

n＝5时，2²ⁿ＋1＝2²⁵＋1＝4294967297，

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

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

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

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

如果反过来问：若n能够整除2ⁿ－2，n是否一定就是质数呢？

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

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