小池有话说

如何证明素数有无穷多个呢？和勾股定理一样，有很多证明方法，也是异彩纷呈。好多证明方法都是神证明（经典证明：素数无穷多的拓扑学证明）。有一本书叫做 Proofs from THE BOOK ，中文译名 来自圣经的证明 ，这本书就是专门搜集这些神证明的。显然 BOOK 在英文中就指圣经。不过，个人觉得翻译成 来自天书的证明 更恰当些。在中国古典小说中，天书就相当于现代武侠小说中的秘笈，一个人一旦得了天书，就立刻跃升为神一样的人物。

扯远了。什么是素数呢？素数就是 只能被1和它本身整除的数 。早在初中的时候我们就学过定义（或许是小学？），但我还是不理解什么是素数。直到有一天看到了某大牛（matrix67？）的博客才恍然大悟：素数就是组成数的基本元素，别的其他任何数都是若干个素数的积（所以合数才叫合数，因为是由别的数合成的）。这种理解类似于化学中的单素和化合物。当时看到这里脑袋里大概灵光一闪，快感如泥石流一般袭来。

又跑题了……素数有无穷多个，如何证明之呢？我曾经看过一个精彩的证明（很多人也看过吧），刚刚搜了一下才发现这个证明竟然是由欧几里得（Euclid） 作出的！

这个证明是这样的：

1. 假设素数不是有无穷多个。
2. 所以素数的个数有限。我们因此可以找出所有素数。
3. 将所有素数乘起来，然后加上1。
4. 所得的结果这个数很神奇，神奇的地方在于，它除以任何素数都余1。也就说，这个数除以所有的素数都除不尽。
5. 这个数除以所以的合数也除不尽，因为合数一定可以写成两个或者多个素数的积的形式。
6. 因此这个数是个素数。而且很明显，这个数大于最大的素数（之前假定的最大素数）。
7. 我们惊奇的发现我们找到了比“最大的素数”还要大的素数。
8. 由此发现矛盾。故原假设错误，由此得证。

如何证明 素数之间的间隔可以任意大 （即：对任意大的 n ，都可以找到两个素数 p1 p2 使得 p2-p1>n ）。

证明如下：

1. 引理：n!+a, (1<a<n)是合数。注意到，对任意a，其中(1<a<n)都可以整除n!+a。（因为n!+a = ((n!/a) * a)+a = ((n!/a)+1) * a，从这个形式可以看出a整除它）

2. 则对于一个自然数序列n!+2, n!+3, n!+4, … , n!+(n-1)，它们都是合数。故命题得证。