附录2 素数无穷的证明

欧几里得第一次证明了这个命题，并由此首创反证法。

首先，他假设素数有穷，共有N个，随后构造按从小到大排列的素数数组：p1,p2, … ,pN，

之后构造QN=p1·p2·…·pN+1，

这样QN就不能被任何一个素数整除，于是有两种情况：

QN是一个素数，但它却比任何一个素数都大，于是矛盾；

QN是一个合数，但它却不能被p1,p2,…pN中的任何一个素数整除，则存在一个pN+1>pN,使得QN能整除pN+1，但这样一来就承认了存在一个比任何素数都要大的素数pN+1的存在，于是矛盾。

综上，得出的结论均与假设矛盾，于是假设错误，素数必有无穷多个。