素数

质数又称素数，是指只能被$1$或自身整除的自然数，一般用$p$表示，数论的研究中，许多主题与质数相关。

从某种角度来看，质数可说是整数的原子。不是质数且比2大的数称为合数，另0与1不是质数，也不是合数。

虽已在两千多年前，欧几里德就已用反证法证明质数有无限多个，但直至今日，人们对质数于正整数中的分布并没有很确切的了解。

OEIS数列编号A000040

性质

• 除了$2$以外，所有的质数都是奇数；且除了5以外，在十进制下，没有质数以$5$结尾。
• 可以很容易证明质数有无限多个，而且许多定理亦蕴含了质数是无限多个的事实。
• 有些质数和另一个质数之间只差$2$，这一对差$2$的质数又称孪生质数，目前尚不知孪生质数是否有无限多对。
• 若$p$和$p+2$为任意大于等于$5$的孪生质数，则其间的$p+1$可被$6$除尽，因为$p$、$p+1$和$p+2$必有一数可为$3$除尽，且$p$和$p+2$皆为大于$5$质数之故(除了$2$以外，所有的质数都是奇数)，因此$p+1$必为偶数且为3所除尽。
• 对于任意的正整数$n$而言，$n$与$2n$间至少有一质数。
• 任意正整数都可唯一地表示成质数乘方的乘积(算术基本定理)。
• 若一个数$n$是合数，则它必定有一个因数小于等于$\sqrt{n}$，因此若要验证任意数$n$是否是质数，只要让$n$被所有小于等于$\sqrt{n}$的质数除过一遍就好了。
• 对于任意正整数$n \geqslant 1$而言，$n$和$2n$间至少会有一个质数。
• 对于任意正整数$n$而言，我们永远可以找到$n$个彼此相邻且不是质数的数，只要取$(n+1)! + 2, (n+1)! + 3, \cdots, (n+1)! + (n+1)$(其中第一个数可被$2$除尽、第二个数可被$3$除尽，以此类推)即可。

应用

质数自从被发现以来，有很长一段时间，质数在人类社会都没有什么数学研究外的用途，但近年来此现象已出现改变，以下为已知质数的可能用途。

• 目前质数已被用于某些加密系统中，如RSA加密演算法。
• 某些种类的蝉需要13或17年的时间才能羽化，某些生物学家认为之所以使用质数的周期，可能和借此将生命周期与猎食者、寄生虫等的生命周期错开的因素有关。

参见

• 质因数分解(整数的惟一因子分解定理)
• 质数分布(介绍有关质数分布的初等结果)
• Eratosthenes筛法(一种寻找质数的方法)
• 威尔森定理(验证某数是否是质数的一个方法)
• 费马数(形如$F_n = 2^{2^n} + 1$的数)
• 完全数
• 哥德巴赫猜想
• 黎曼Zeta猜想
• 孪生质数猜想

上下节

• 上一节：带余除法
• 下一节：公因数