质数为什么有无数多个

反证法

当我们想要证明某个序列中元素个数是无穷大时，我们往往可以考虑通过反证法，

也即先假设这个序列中的元素个数是有限的，然后从该假设出发去寻找矛盾。

证明

假设质数的个数是有限的，它们构成一个集合 P={p1​,p2​,...,pr​}，我们考虑这样一个数 n=p1​p2​⋯pr​+1，显然它要么是质数，要么是合数 。

假设它是质数，显然它不属于 P ，因此 P 就并未包含所有质数，这与「P 是所有质数的集合」矛盾。

假设它是合数，那么n必有一个质因子，我们设为 p ，也即n可写作 p 与另一个正整数 N 的乘积。

如果p∉P ，那么 P 就并未包含所有质数，产生矛盾。

如果 p∈P ，我们可以将 p记作pk​ ，这里 k 是 1 到 r 中的某个数，这是因为p 是 p1​,p2​,⋯,pr​ 中的任意一个，那就意味着 p 也是p1​p2​⋯pr​ 的质因子 。

置m:=p1​p2​⋯pr​ ，由于p 是它的质因子，那么 m 也可以写作 p×Nk​ （这里Nk​是一个正整数） 。而 n=m+1 ，我们经过一系列的变换最终得到 N−Nk​=1/p，由于 N 和 Nk​ 都是整数，则 1/p 也是整数，而由于 p 是质数，则 p≥2 ，因此 1/p 不可能为整数，这就与刚才得出的 1/p 是整数产生矛盾。

至此，我们的讨论已经囊括了所有情况，但均得出了矛盾，这也就意味着，我们无法用一个有限的集合来表示所有的质数，也即，质数的个数是无限的。