The number of primes is unlimited

按:内容来源于从前在 CSDN 上的 blog

【定义】:素数(也称质数)是指在大于1的自然数中,除了1和此整数自身外,无法被其他自然数整除的数(也可定义为只有1和本身两个因数的数)。

【求证】:素数有无限多个

【证明】:

如果素数是有限的,设从小到大依次是 p0, p1, ..., pn (p0 < p1 < ... < pn)

设 p = p0 * p1 * ... * pn + 1

显然 p != pi ( 0 <= i <= n)

依据假设,p 在素数集合之外,即为合数。

而p mod pi = 1

即 p 无法被任何素数整除,那么因为 p 本身不是素数,它就一定能被除1和其本身之外的一个数整除,既然这个数不能是素数,那么就是另外一个合数,而合数即能分解出素数因子,即 p 含有素数因子,和前面的推断「p无法被任何素数整除」的假定矛盾,故假设素数是有限个数的说法是错误的。

所以,素数的个数是无限的。

注:

  1. 这个问题也记录在 CSDN 的博客上: 素数的个数为什么是无限的
  2. 维基百科有关质数的词条:「素数」、「Prime Number