素数定理

概述

素数定理（Prime Number Theorem, PNT）：不超过 $x$ 的素数个数 $\pi (x)$ 满足渐近公式 $\pi (x)\sim \frac{x}{\ln x}$，即素数在自然数中的分布密度随 $x$ 增大而趋近于 $1/\ln x$。

定理陈述

形式化陈述

定理（Hadamard & de la Vallée Poussin, 1896）：设 $\pi (x)$ 表示不超过 $x$ 的素数个数，则 ${\lim }_{x\to \infty }\frac{\pi (x)}{x/\ln x}=1$ 即 $\pi (x)\sim \frac{x}{\ln x}$。

等价形式

素数定理有多种等价表述：

1. Chebyshev函数形式：$\psi (x)\sim x$，其中 $\psi (x)={\sum }_{p^k\le x}\ln p$
2. 对数积分形式：$\pi (x)\sim \mathrm{Li}(x)={\int }_2^x\frac{dt}{\ln t}$
3. 第 $n$ 个素数：第 $n$ 个素数 $p_n\sim n\ln n$

历史背景

• 1792年，Gauss（15岁时）通过观察素数表猜测 $\pi (x)\approx x/\ln x$
• 1850年，Chebyshev证明了 $\pi (x)$ 与 $x/\ln x$ 的比值介于 0.921 和 1.106 之间
• 1896年，Hadamard和de la Vallée Poussin独立给出严格证明
• 1949年，Selberg和Erdős给出了初等证明（不使用复分析）

证明概要

证明思路

素数定理的证明有两条主要路线：

路线一：解析证明（Hadamard / de la Vallée Poussin）

核心工具：Riemann zeta函数 $\zeta (s)={\sum }_{n=1}^{\infty }\frac{1}{n^s}={\prod }_{p\text{ prime}}\frac{1}{1-p^{-s}},\text{Re}(s)>1$

关键步骤：

1. 解析延拓：将 $\zeta (s)$ 解析延拓到 $\text{Re}(s)>0$（除 $s=1$ 处有简单极点）
2. 零点分布：证明 $\zeta (s)$ 在直线 $\text{Re}(s)=1$ 上没有零点（这是最关键的技术步骤）
3. Perron公式：利用围道积分将 $\psi (x)$ 表示为 $\zeta (s)$ 的对数导数的积分
4. 误差估计：通过移动积分围道，利用零点分布信息得到 $\psi (x)=x+o(x)$

Newman的简化证明（1980）：D.J. Newman发现了一种精巧的方法，用Cauchy积分公式和Tauber型定理给出了更简洁的证明框架。

路线二：初等证明（Selberg / Erdős, 1949）

核心工具：Selberg恒等式 $\psi (x)\ln x+{\sum }_{p\le x}\psi \left(\frac{x}{p}\right)\ln p=2x\ln x+O(x)$

关键步骤：

1. 从Selberg恒等式出发，推导出 $\psi (x)$ 的渐近估计
2. 利用对称化技巧和数论恒等式
3. 通过精巧的迭代和估计，最终得到 $\psi (x)\sim x$

参考文献

• Hadamard, J. (1896). Sur la distribution des zéros de la fonction $\zeta (s)$. Bull. Soc. Math. France, 24, 199-220.
• de la Vallée Poussin, C. (1896). Recherches analytiques sur la théorie des nombres premiers. Ann. Soc. Sci. Bruxelles, 20, 183-256.
• Newman, D. J. (1980). Simple analytic proof of the prime number theorem. Amer. Math. Monthly, 87(9), 693-696.
• 证明概述: Harvard - Proof of the Prime Number Theorem
• Leiden课程: Introduction to Prime Number Theory
• 自包含证明: KSU - The Prime Number Theorem

关键推论

• 推论1：第 $n$ 个素数 $p_n$ 满足 $p_n\sim n\ln n$，即素数越来越稀疏
• 推论2：相邻素数之间的平均间隔约为 $\ln n$
• 推论3（Bertrand假设的加强）：对充分大的 $x$，区间 $(x,x+x^{0.525})$ 中必有素数（Baker-Harman-Pintz, 2001）
• 推论4：若Riemann假设成立，则误差项可改进为 $\pi (x)=\mathrm{Li}(x)+O(\sqrt{x}\ln x)$

应用场景

• 密码学：RSA等公钥密码系统的安全性依赖于大素数的分布——素数定理保证在 $N$ 附近找到素数需要约 $\ln N$ 次尝试
• 算法分析：素性测试算法（如Miller-Rabin）的效率分析需要素数分布信息
• 哈希函数设计：开放寻址哈希中表大小常选为素数，素数定理指导素数的选择
• 计算数论：素数分布在解析数论中有广泛应用，如Goldbach猜想、孪生素数猜想等

参见

• 素数
• 整除
• 最大公约数
• 欧几里得算法
• 费马小定理