素数是大于1且恰有两个正因数（1和自身）的正整数。最初的几个素数是2、3、5、7、11、13、17、19、23和29。大于1而不是素数的数称为合数。素数在数论中占据核心地位，因为每个大于1的整数都可以表示为素数的乘积，而且除因子的排列顺序外，这种表示是唯一的。(users.math.msu.edu)
定义与基本性质
判断一个数是否为素数，考察的是整数范围内的整除关系，而不是允许商为任意分数的除法。例如，7是素数，因为除了1和7以外，没有其他正整数能将它整除；12是合数，因为 (12=3\times4)。1既不是素数，也不是合数，因为它只有一个正因数。将1排除在素数之外，也避免了在素因数分解中任意插入多个因子1。(math.gordon.edu)
2是唯一的偶素数，因为每个大于2的偶整数都以2为真因数。每个合数 (n) 都有一个不大于 (\sqrt n) 的素因数。因此，要判断 (n>1) 是否为素数，只需检查不超过这一上界的素数能否整除它。(math.uwaterloo.ca)
欧几里得引理给出了素数的一项基本性质：如果素数 (p) 整除乘积 (ab)，那么 (p) 整除 (a) 或 (b)。对于一般的合数除数，类似的命题并不成立：6能整除 (2\times3)，却不能整除其中任何一个因子。(math.mit.edu)
素因数分解
算术基本定理指出，将素数按固定顺序排列后，每个整数 (n>1) 都有唯一的表示形式：
[ n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}, ]
其中，(p_i) 是互不相同的素数，(a_i) 是正整数。例如，
[ 360=2^3\cdot3^2\cdot5. ]
不断将合数因子分解为更小的因子，即可证明这种分解的存在性；利用欧几里得引理则可证明其唯一性。因此，素数是构成正整数的乘法基本单元，但在加法运算下，并不存在类似的唯一分解。(math.gordon.edu)
素数有无穷多个
对素数的研究可以追溯到古希腊。欧几里得在《几何原本》第九卷中证明了素数有无穷多个。一种常见的现代论证采用反证法：假设 (p_1,\ldots,p_k) 就是全部素数，并构造
[ N=p_1p_2\cdots p_k+1. ]
列出的素数都不能整除 (N)，因为 (N) 除以其中任何一个素数的余数都是1。然而，(N>1) 必定有一个素因数，这就与该列表包含全部素数的假设矛盾。需要注意的是，(N) 本身不一定是素数；这一论证只要求它有一个不在所列素数中的素因数。(faculty.etsu.edu)
分布
随着数值增大，素数平均而言会变得越来越稀疏。用 (\pi(x)) 表示不超过 (x) 的素数个数。素数定理指出：
[ \pi(x)\sim\frac{x}{\ln x}, ]
这意味着，当 (x) 无限增大时，两边表达式的比值趋于1。雅克·阿达马和夏尔-让·德拉瓦莱·普桑于1896年分别独立证明了这一定理。它描述的是素数的平均密度，而不是精确确定每个素数位置的规则。(claymath.org)
此外，还存在任意长的连续合数序列。对于任意整数 (m\ge2)，(m!+2,\ldots,m!+m) 都是合数，因为每个 (m!+j) 都能被 (j) 整除。这表明素数间隔没有上界。(math.uwaterloo.ca)
对素数分布更深入的描述涉及黎曼ζ函数。波恩哈德·黎曼于1859年提出的黎曼猜想断言，该函数所有非平凡零点的实部都为 (1/2)。克雷数学研究所仍将这一猜想列为未解问题。它对素数研究的重要意义，在于能够精确控制素数分布相对于平均分布的偏差。(claymath.org)
寻找素数与素性测试
埃拉托斯特尼筛法是一种用于列出给定上界以内全部素数的算法。它从2开始列出整数，反复将当前最小的未标记数的倍数标记出来。只需依次处理平方不超过上界的素数；最终剩下的未标记整数就是素数。(users.math.msu.edu)
对于单个很大的输入整数，素性测试与求出其完整的因数分解是不同的任务。费马小定理指出，对于素数 (p) 和不能被 (p) 整除的整数 (a)，有
[ a^{p-1}\equiv1\pmod p. ]
然而，仅仅满足这一同余式并不能证明一个数是素数。米勒–拉宾素性测试通过检查更多的模幂运算结果，增强了此类测试的判别能力。采用独立随机选择的参数重复测试，可以降低合数输入通过所有轮次测试的概率。(math.mit.edu)
2002年，马宁德拉·阿格拉瓦尔、尼拉杰·卡亚尔和尼廷·萨克塞纳提出了AKS素性测试。它无需假定任何尚未证明的猜想，就能以确定性的方式，在相对于输入位数的多项式时间内判定素性。这是计算复杂性领域的一项里程碑成果，但并不意味着整数因数分解也有了多项式时间算法。(cse.iitk.ac.in)
代数与密码学
在模算术中，模素数 (p) 的剩余类构成一个有限域：每个非零剩余类都有乘法逆元。模合数的剩余类则不具备这一性质。因此，素数确定了一种重要的代数结构，在这种结构中，可以进行以非零元素为除数的除法。(math.mit.edu)
素数也是密码学中部分方法的基础。在RSA密码系统中，模数由两个互不相同的大素数相乘构成。知道这两个因子，就能计算出构造私钥所需的信息。高效的素性测试为密钥生成提供支持，而从乘积中还原其因子的困难性则是这一系统的核心安全性假设。(math.mit.edu)