《算法导论学习笔记》-如何证明有无穷多个素数

证明的定理

在自然数集合中,

素数有无穷多个。

证明

假设我们已知这么几个素数$p_1,p_2,p_3……p_n$,我们需要证明的是已知这些素数能推出第$n+1$个素数,那么数学归纳法就可以证明有无穷多个素数了。
我们构造一个新数$d=p_1\times p_2\times p_3……\times p_n+1$显然可以证明$d$不能被上述素数中的任何一个整除。
现在我们进行分类讨论:
如果这是一个素数,那么已经证明了能通过$n$个素数求出第$n+1$个素数。下面一种情况有点复杂。
如果这是一个合数。我们先来回顾素数的定义:素数是只能被它自己的平凡约数(即1和它本身)整除的自然数。所以一个合数一定有非平凡约数。所以一定存在上述$n$个素数以外的素约数。这样也证明了通过$n$个素数证明存在第$n+1$个素数。

文章目录
  1. 1. 证明的定理
  2. 2. 证明