欧几里得妙法

简介

数论与几何学一样，是最古老的数学分支。欧几里得的《几何原本》的七、八、九章，讲的就是数论。

对于素数的研究，在数论中占有很重要的位置。

我们知道，正整数是由1、素数（也叫质数）与合数这三类数组成的。一个大于1的正整数，如果只能被1和它本身整除，不能被其他正整数整除，这样的正整数就叫做素数；否则就叫做合数。在整数1、2、3、4、……中，去掉1与全部合数，所得的表：

2，3，5，7，11，13，17，称为素数表。在素数表中，除了第一个素数2，其余都是奇素数。现在世界上最好的素数表是查基尔编的，列有大不大于50000000（五千万）的素数。

关于素数，最古老的问题是：素数有多少个？欧几里得在《几何原本》中，最先证明了素数有无穷多个。他的巧妙的证明方法，闪耀着智慧的光辉。2000多年来，人们虽也提出过一些别的证法，但是直到今天，还是欧几里得的证明方法最好。

欧几里得证明素数有无穷多个的方法，大意是：

假若素数只有有限多个，设最大的一个是P，从2到P的全体素数是：

2，3，5，7，11……，P。

所有的素数都在这里，此外再没有别的素数了。

现在，我们来考察上面从2到P的全体素数相乘、再加上1这个数，设它是A，即

A=2×3×5×7×11×……×P+1。

A是一个大于1的正整数，它不是素数，就是合数。

如果A是素数，那么，就得到了一个比素数P还要大的素数，这与素数P是最大素数的假设矛盾。

如果A是合数，那么，它一定能够被某个素数整除，设它能被g整除。

因为A被从2到P的任何一个素数除，余数都是1，就是都不能整除，而素数g是能整除A的，所以素数g不在从2到P的全体素数之中。这说明素数g是一个比素数P更大的素数，这又与P是最大的素数的假设矛盾。

上面的证明否定了素数只有有限多个的假定，这就证明了素数是无穷多个。

这个证明的构思非常巧妙，它的基本思路是：既然对于无论多大的素数，都一定有比它更大的素数，那当然素数就是无穷多个了。

素数虽然有无穷多个，但是在自然数中，它是排列得相当稀的。人们证明了这样一个道理：无论给定一个多大的正整数，比方说100亿万，一定能找到一个正整数，在这个正整数中，一个素数也没有。如果你不是说100万，而是说100亿万，这个结论也成立。

这个定理的证明，在构思上与证明素数无穷相象。

素数虽然有无穷多个，但人们能具体写出来的，总是有限个。因此，找一个比现在所知道的最大素数更大的素数，是人们经常探讨的难题之一。