非存在证明

算法（逻辑）与启发法不仅仅是二选一的竞争关系。一般情况下，在一个证明之中，算法和启发法会同时存在。接下来让我们来看看其中的代表例——“不存在最大的质数”的证明。

质数指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的自然数。那么，最大的质数是否存在呢？也就是说，是不是当自然数变大到一个界限之后，质数就不会再出现了呢？这个问题虽然非常单纯，但其难度也超越了人脑的性能。不管一个人再聪明，都无法靠直觉想出正确答案。

此时，我们就要运用一种逻辑算法——“反证法”（见第4章第12小节）。在运用反证法时，先将我们要证明的命题a进行否定，并假设此否定命题成立，然后推理出明显矛盾的结果，从而下结论说原假设不成立，最后得出命题a为真。于是，为了证明最大质数不存在，我们就应对其进行否定，假设“存在最大质数”。

我们将此最大质数表示为n。再假定一个数m，它具有如下性质。

m=（1×2×3×4×…×n）+1

从这个等式来看，m要比n大。因为n是最大的质数，所以m理应不是质数。因为它不是质数，所以我们可以对其进行整数分解，表示如下（整数分解即对乘法算式进行分解，直到算式中的每个乘数都被分解为质数为止）。

m=a×b×c×d×…×z

从m的性质来看，当它被比n小的自然数所除时，余数一定是1，所以从a到z的所有质数一定都要比n来得大。但这个推理和“n是最大的质数”这一假设是相矛盾的。没错，这个时候我们就可以知道，“存在最大质数”这一假设是错误的。

逻辑和直觉相结合才能够完成证明

假设如果“a”那么“b”成立，当出现“b”不成立这一矛盾时，就可以反过来推断“a不成立”。此反证法也属于“逻辑”，其论证步骤还可运用于不在场证明——“如果他是犯人，那当天他应该出现在了犯罪现场。但那天他并不在现场，因此他不是犯人”。

质数问题的证明在整体上都遵循了逻辑算法，但在其中两个关键的地方则依赖于启发法。各位知道具体是哪两个关键点吗？没错，第一点就是m的等式构成。为什么会把m规定为（1×2×3×4×…×n）+1呢？这无法用逻辑算法来决定。

第二点在于，究竟为什么会选反证法来作为证明方法呢？也许是因为我们从一开始就预料到“不存在最大质数”，所以才试图从其否定形式中推导出前后矛盾的结果吧。从最开始就准确地（尽管根据十分薄弱）对真正的结论进行预想。这并非逻辑，只能称其为直觉，或是灵感。