隐藏在素数无穷的证明中的一个陷阱

我们知道，关于素数有无穷多个的最普遍的证明方法是欧几里得的反证法：

假设存在最大的素数 P，那么我们可以基于所有的素数构造一个新的数 Q = 2 x 3 x 5 x 7 x … x P + 1。显然这个数不能被任一素数整除（所有素数除它都余1），这说明我们找到了一个更大的素数。

我发现很多人误认为我们构造的这个新数 Q 是一个素数（甚至有些数学教材上也这么写），这其实是不对的。基于 Q 不能被任意素数整除这一事实，我们能够得到的结论是：Q 或者是一个素数，或者包含一个比最大的素数 P 更大的素数因子。

通过简单的几行程序就能找到"存在 Q 为合数“的证据。这个数并不大。当 P 为 13 时，Q = 2 x 3 x 5 x 7 x 11 x 13 +1 = 30031 = 59 x 509。