Tao–Vu · 加性组合学 · 第 1 章 概率方法

1.10　附录：素数的分布Appendix: the distribution of the primes

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演 / 注记）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。本节是数论附录，核心是几条关于“素数有多密”的初等估计，证明出奇地漂亮，请耐心跟随每一步动机。

本节目标本章前面好几处结论都用到了“素数到底有多少、有多密”这件事。本附录就来回答它：先给出最有名的素数定理（不证），再用初等方法（不靠复变函数）证明三条关于素数的求和估计（Chebyshev 与 Mertens 的经典结果），最后给出一条关于“区间里有多少素数”的较深定理，并把它和 Abel 求和法结合，推出后面会用到的两条估计。一句话：把“素数稀疏到什么程度”量化成可以代入计算的公式。

本章中有若干结果依赖于关于素数集合 \[P=\{2,3,5,\dots\}\] 之分布的一些事实。这个集合的分布当然是解析数论中一个研究得非常透彻的课题，其中最基本的结果之一便是素数定理（prime number theorem）： \[\tag{1.44}|P\cap[1,n]|=(1+o(1))\,\frac{n}{\log n}.\] 一个等价的表述是：若 \(p_k\) 表示第 \(k\) 个素数，则 \(p_k=(1+o(1))\,k\log k\)。著名的、至今仍未解决的黎曼猜想（Riemann hypothesis）等价于下面这个更强的论断：对任意 \(\varepsilon>0\)， \[\tag{1.45}|P\cap[1,n]|=\int_2^{n}\frac{dx}{\log x}+O_\varepsilon\!\left(n^{1/2+\varepsilon}\right),\] 或等价地说，对任意 \(\varepsilon>0\) 有 \(p_k=k\log k+O_\varepsilon\!\left(k^{1/2+\varepsilon}\right)\)。

读符号记号 \(|P\cap[1,n]|\) 就是“不超过 \(n\) 的素数个数”，数论里常记作 \(\pi(n)\)。\(o(1)\) 表示“当 \(n\to\infty\) 时趋于 \(0\) 的量”，所以 \((1+o(1))\) 表示“比值趋于 \(1\)”。\(O(\cdot)\) 表示“最多是这么大的量（差一个常数倍）”，下标如 \(O_\varepsilon\) 表示那个常数可以依赖于 \(\varepsilon\)。本节通篇约定：对变量 \(p\) 求和时，\(p\) 一律只取素数。
例：素数定理在说什么取 \(n=10^6\)。素数定理说素数个数约为 \(n/\log n=10^6/\log(10^6)\approx 10^6/13.8\approx 72\,382\)。真实值是 \(\pi(10^6)=78\,498\)。两者比值约 \(1.08\)，已经相当接近 \(1\)；\(n\) 越大比值越靠近 \(1\)，这正是 \((1+o(1))\) 的含义。直观结论：在 \(1\) 到 \(n\) 之间，大约每 \(\log n\) 个整数里有一个素数，素数越往后越稀疏。
n（整数从小到大） 个数 π(n)=|P∩[1,n]|（阶梯） n/log n（光滑曲线）
蓝色阶梯每遇到一个素数就上跳一格，红色虚线是 \(n/\log n\)。素数定理说：阶梯与曲线的比值随 \(n\to\infty\) 趋于 \(1\)，即两条线“几乎贴在一起”。

素数定理相当深刻，这里不予证明。本附录中我们呈现一些相关的结果，其中大多数都有出人意料地初等而优美的证明。由于它们在本质上属于数论而非概率，我们选择把这些结果放在本章的附录里。

我们从 Chebyshev 与 Mertens 的一些经典估计开始。按照惯例，当对变量 \(p\) 求和时，\(p\) 理解为表示一个素数。

命题 1.51（初等素数估计）设 \(n\ge 1\) 为整数，则有如下估计： \[\tag{1.46}\sum_{p\le n}\log p=O(n),\] \[\tag{1.47}\sum_{p\le n}\frac{\log p}{p}=\log n+O(1),\] \[\tag{1.48}\sum_{p\le n}\frac{1}{p}=\log\log n+O(1).\]
注记 1.52有了素数定理，我们可以把 (1.46) 改进为 \(\sum_{p\le n}\log p=(1+o(1))n\)，但对我们这里的应用而言并无此必要。
先看清这三条在说什么它们都是“把不超过 \(n\) 的所有素数按某个权重加起来”的估计，且每往下一条都比上一条更精细：
  1. (1.46)：把素数的“对数”加起来，约为 \(n\)。等价于 \(\prod_{p\le n}p\approx e^{n}\)，即素数之积大约是 \(e^n\)——这给出了素数“不太少”的下界感。
  2. (1.47)：加权 \(1/p\) 后再乘 \(\log p\)，结果约为 \(\log n\)。这是通向 (1.48) 的跳板。
  3. (1.48)：最有名的一条——素数倒数之和发散，且增长速度恰为 \(\log\log n\)。它比“调和级数 \(\sum 1/k\approx\log n\) 发散”更强地告诉我们素数有多稠密。

命题 1.51 的证明

第一步：证明 (1.46)

证明. 我们首先证明 (1.46)。不失一般性，可设 \(n\) 为 \(2\) 的幂。考虑二项式系数 \(\binom{2n}{n}\)。由 Pascal 公式（即 \(\sum_{k}\binom{2n}{k}=2^{2n}=4^n\)，而 \(\binom{2n}{n}\) 只是其中一项）我们知道 \[\binom{2n}{n}\le 4^n.\] 另一方面，显然每个介于 \(n\) 与 \(2n\) 之间的素数都整除 \(\binom{2n}{n}\)。因此 \[\prod_{n♦

为什么“\(n\) 到 \(2n\) 之间的素数整除 \(\binom{2n}{n}\)”关键观察。写 \(\binom{2n}{n}=\dfrac{(2n)!}{n!\,n!}=\dfrac{(n+1)(n+2)\cdots(2n)}{1\cdot 2\cdots n}\)。设素数 \(p\) 满足 \(n
  • 分子是 \(n+1\) 到 \(2n\) 这 \(n\) 个连续整数之积，其中恰好有一个是 \(p\) 的倍数（就是 \(p\) 自己，因为 \(2p>2n\) 已超出范围），所以分子含有因子 \(p\)。
  • 分母是 \(1\) 到 \(n\) 的乘积，而 \(p>n\)，所以分母里没有 \(p\) 这个因子，约不掉。
  • 于是 \(p\mid\binom{2n}{n}\)。这对每个这样的 \(p\) 都成立，且这些素数互不相同，故它们的乘积 \(\prod_{n 取对数即把“乘积 \(\le 4^n\)”变成“对数之和 \(\le n\log4=O(n)\)”。
    • 例：用 \(n=4\) 检验整除性\(\binom{8}{4}=70=2\cdot 5\cdot 7\)。介于 \(4\) 与 \(8\) 之间的素数是 \(5,7\)，果然都整除 \(70\)。而它们的乘积 \(5\cdot 7=35\le 4^4=256\)，符合 \(\prod_{n
    为什么“代入 \(n/2,n/4,\dots\) 再求和”就得到完整的 (1.46)上面只控制住了一段区间 \((n,2n]\) 上素数对数之和。要覆盖全部 \(p\le n\)，把整段 \([1,n]\) 切成一串首尾相接、长度成倍缩小的区间，对每一段用刚证的界： \[\sum_{p\le n}\log p=\underbrace{\sum_{n/2
    n n/2 n/4 n/8 …0 O(n/2) O(n/4) O(n/8) 每段用 (n,2n] 的界，右端点相加成几何级数 = n
    把 \([0,n]\) 反复二分成 \((n/2,n],(n/4,n/2],\dots\)，每段素数对数之和被该段长度的 \(O(\cdot)\) 控制，全部相加仍是 \(O(n)\)。

    第二步：证明 (1.47)

    现在我们证明 (1.47)。这是一个类似的论证，但围绕阶乘 \(n!\) 而非 \(\binom{2n}{n}\) 展开。注意到整除 \(n!\) 的素数只能是那些不超过 \(n\) 的素数。对每个素数 \(p\le n\)，介于 \(1\) 与 \(n\) 之间能被 \(p\) 整除的数有 \(\lfloor n/p\rfloor\) 个，能被 \(p^2\) 整除的有 \(\lfloor n/p^2\rfloor\) 个，依此类推。因此 \[\tag{1.49}n!=\prod_{p\le n}p^{\,\lfloor n/p\rfloor+\lfloor n/p^2\rfloor+\cdots}.\] 对两边取对数，并应用 Stirling 公式（习题 1.10.1），我们得到 \[n\log n+O(n)=\sum_{p\le n}\bigl(\lfloor n/p\rfloor+\lfloor n/p^2\rfloor+\cdots\bigr)\log p.\] 由于 \[\lfloor n/p\rfloor+\lfloor n/p^2\rfloor+\cdots=\frac{n}{p}+O(1)+O\!\left(\frac{n}{p^2}\right),\] 经过一些整理，我们得出 \[n\log n+O(n)=\sum_{p\le n}\frac{n\log p}{p}+\sum_{p\le n}O(\log p)+\sum_{p\le n}O\!\left(\frac{n\log p}{p^2}\right).\] 由于 \(\sum_k\frac{\log k}{k^2}\) 收敛，最后一项是 \(O(n)\)。结合 (1.46)（它给出 \(\sum_{p\le n}O(\log p)=O(n)\)），结论随之得到。♦

    为什么 \(p\) 在 \(n!\) 中的指数是 \(\lfloor n/p\rfloor+\lfloor n/p^2\rfloor+\cdots\)（Legendre 公式）\(n!=1\cdot2\cdots n\)。要数 \(p\) 在 \(n!\) 中总共出现几次，就把每个因子贡献的 \(p\) 都算上：
    1. 是 \(p\) 倍数的因子各至少贡献 \(1\) 个 \(p\)，这样的因子有 \(\lfloor n/p\rfloor\) 个。
    2. 是 \(p^2\) 倍数的因子额外再贡献 \(1\) 个 \(p\)（因为它含 \(p^2\)），这样的因子有 \(\lfloor n/p^2\rfloor\) 个。
    3. 是 \(p^3\) 倍数的再额外贡献 \(1\) 个，\(\dots\) 如此累加。
    把所有贡献加起来就是 \(\lfloor n/p\rfloor+\lfloor n/p^2\rfloor+\cdots\)。
    例：用 \(n=6\) 验证 (1.49)\(6!=720\)。对 \(p=2\)：\(\lfloor6/2\rfloor+\lfloor6/4\rfloor=3+1=4\)，故 \(2^4\)；对 \(p=3\)：\(\lfloor6/3\rfloor=2\)，故 \(3^2\)；对 \(p=5\)：\(\lfloor6/5\rfloor=1\)，故 \(5^1\)。于是 \(2^4\cdot3^2\cdot5=16\cdot9\cdot5=720\)，正确。
    为什么近似 \(\lfloor n/p\rfloor+\lfloor n/p^2\rfloor+\cdots=\dfrac np+O(1)+O\!\left(\dfrac n{p^2}\right)\)逐项拆：
    1. 第一项 \(\lfloor n/p\rfloor=\dfrac np+O(1)\)，因为去掉小数部分最多差 \(1\)。
    2. 剩下的尾巴 \(\lfloor n/p^2\rfloor+\lfloor n/p^3\rfloor+\cdots\le \dfrac n{p^2}+\dfrac n{p^3}+\cdots=\dfrac{n/p^2}{1-1/p}=O\!\left(\dfrac n{p^2}\right)\)（几何级数）。
    代回求和：主项给出 \(\sum_p\frac{n\log p}{p}\)（这是我们要的）；\(O(1)\) 那项乘 \(\log p\) 求和得 \(\sum_p O(\log p)=O(n)\)（用 (1.46)）；\(O(n/p^2)\) 那项乘 \(\log p\) 求和得 \(n\sum_p O(\log p/p^2)=O(n)\)（因 \(\sum_k\frac{\log k}{k^2}\) 收敛）。把 \(O(n)\) 项全部并入误差，左边的 \(n\log n+O(n)\) 除以 \(n\) 后就得到 \(\sum_{p\le n}\frac{\log p}{p}=\log n+O(1)\)。

    第三步：用 Abel 求和法从 (1.47) 推出 (1.48)

    我们将利用 Abel 求和技巧从 (1.47) 推出 (1.48)，即把一个关于素数的部分和改写成另一些部分和的平均。由微积分基本定理注意到 \[\frac{1}{p}=\frac{\log p}{p}\cdot\frac{1}{\log p}=\frac{\log p}{p}\int_p^{\infty}\frac{dt}{t\log^2 t}=\frac{\log p}{p}\int_1^{\infty}I(t>p)\,\frac{dt}{t\log^2 t},\] 因而 \[\sum_{p\le n}\frac{1}{p}=\sum_{p\le n}\frac{\log p}{p}\int_1^{\infty}I(t>p)\,\frac{dt}{t\log^2 t}.\] 交换求和与积分的次序，我们得到 \[\sum_{p\le n}\frac{1}{p}=\int_1^{\infty}\Bigl(\sum_{p\le t}\frac{\log p}{p}\Bigr)\frac{dt}{t\log^2 t}.\] 应用 (1.47)，我们得到 \[\sum_{p\le n}\frac{1}{p}=\int_1^{\infty}\bigl(\log t+O(1)\bigr)\frac{dt}{t\log^2 t}.\] 由于 \(\dfrac{\log t}{t\log^2 t}=\dfrac{1}{t\log t}\) 的原函数是 \(\log\log t\)，而 \(\dfrac{1}{t\log^2 t}\) 是绝对可积的，结论随之得到。♦

    把 Abel 求和法这一步拆开看核心思路：直接对 \(\sum 1/p\) 估计很难，但我们已经会估 \(\sum (\log p)/p\)（即 (1.47)）。Abel 法的窍门是把权重 \(1/p\) 写成 \((\log p)/p\) 乘上一个积分，从而把“难的和”转成“已知的和”的积分平均。
    1. 恒等式：\(\displaystyle\int_p^\infty\frac{dt}{t\log^2 t}=\Bigl[-\frac{1}{\log t}\Bigr]_p^\infty=\frac{1}{\log p}\)。所以 \(\dfrac{\log p}{p}\cdot\dfrac{1}{\log p}=\dfrac1p\)，等式成立。
    2. 引入指示函数：把下限 \(p\) 写成 \(\int_1^\infty I(t>p)\,(\cdots)\)，这样积分下限统一为 \(1\)，便于交换次序。
    3. 交换求和与积分：原来是“先对每个 \(p\) 积分、再求和”；交换后是“先在固定 \(t\) 处把满足 \(p
    4. 代入 (1.47)：内层和 \(=\log t+O(1)\)，于是积分变成 \(\int_1^\infty(\log t+O(1))\frac{dt}{t\log^2 t}\)。
    5. 算积分：主项 \(\int\frac{\log t}{t\log^2 t}dt=\int\frac{dt}{t\log t}=\log\log t\)，从 \(\sim\) 到 \(n\) 给出 \(\log\log n\)；误差项 \(\int O(1)\frac{dt}{t\log^2t}\) 收敛，是 \(O(1)\)。合起来 \(\sum_{p\le n}\frac1p=\log\log n+O(1)\)。
    例：感受 \(\log\log n\) 增长之慢\(\log\log n\) 是出了名地慢。取 \(n=10^9\)：\(\log n\approx 20.7\)，\(\log\log n\approx 3.03\)。也就是说，把十亿以内所有素数的倒数加起来，也才大约 \(3\) 出头（精确值约 \(3.29\)）。要让这个和达到 \(4\)，需要的 \(n\) 大到天文数字。这就是“素数倒数和发散，但慢得惊人”的真实写照。
    把和与积分的次序交换（图示） 原式：对每个素数 p，沿 t>p 积分 p₁p₂p₃ 交换后：对每个 t，先把 p<t 的素数加起来 固定 t ∑_{p<t} log p / p t 轴 →
    Abel 法的几何含义：同一块“求和-积分”区域，既可“先固定素数沿 \(t\) 积分”，也可“先固定 \(t\) 对素数求和”。交换次序后内层和恰能用已知的 (1.47) 替换。

    素数在区间中的分布

    我们现在转向一个关于素数在区间中分布的更深刻的事实。

    定理 1.53对所有充分大的 \(n\)，对一切 \(n^{2/3}
    读符号 \(\Theta\)\(f=\Theta(g)\) 表示 \(f\) 与 \(g\) 同阶——既有上界 \(f=O(g)\) 又有下界 \(f\ge c\,g\)（\(c>0\) 为某常数）。所以本定理是说：长度为 \(x\) 的区间 \([n-x,n)\) 里的素数个数，既不会多太多、也不会少太多，大约就是 \(x/\log n\) 个——这与素数定理给出的“平均密度约 \(1/\log n\)”一致，但要点在于它对较短的区间（只要长度 \(x>n^{2/3}\)）也成立。

    此类结果最早由 Hoheisel [183] 给出；这里所述形式归功于 Ingham [188]。注意，本定理可由黎曼猜想 (1.45) 立即推出。然而，本定理也可以不使用黎曼猜想而证明，只需用到关于黎曼 \(\zeta\) 函数零点分布的一些较弱（但仍非常不平凡）的事实：参见 [170]。我们指出，如果只追求 \(|P\cap[n-x,n)|\) 的上界，那么可以用相对初等的筛法来确立该论断。常数 \(2/3\) 已被降低（当前纪录是 \(7/12\)，见 [187]、[178]）。然而，对这里的应用而言，任何小于 \(1\) 的指数都已足够。

    区间 [n−x, n)，长度 x n−x n 素数个数 ≈ x / log n（只要 x > n^{2/3}）
    定理 1.53：靠近 \(n\) 的一段长度为 \(x\) 的短区间内，素数个数与 \(x/\log n\) 同阶。短到 \(x>n^{2/3}\) 仍然成立，这是它“深”的地方。

    我们现在把这条定理与 Abel 求和法结合，建立一些关于素数求和的进一步估计。

    命题 1.54设 \(n\) 为一个大整数，则有如下估计： \[\tag{1.50}\sum_{p\in P\cap[1,\,n-n^{2/3})}\frac{1}{n-p}=\Theta(1),\] \[\tag{1.51}\sum_{p\in P\cap[1,\,n-n^{2/3})}\frac{\log(n-p)}{n-p}=\Theta(\log n).\]
    这两条在数什么把目光放在“\(n\) 减去一个素数 \(p\)”得到的差 \(n-p\) 上。求和范围 \(pn^{2/3}\)（差不会太小，避开了定理 1.53 不管用的区域）。(1.50) 说这些 \(1/(n-p)\) 加起来是有界的常数量级；(1.51) 是它带 \(\log\) 权重的版本。后面章节用到的正是这种“对所有可能的 \(n-p\) 求和”的估计。

    证明. 我们先证明 (1.50)。由微积分基本定理，对一切 \(p\in P\cap[1,n-n^{2/3})\) 有 \[\frac{1}{n-p}=\int_1^{\infty}I\bigl(p\in[n-x,\,n-n^{2/3})\bigr)\frac{1}{x^2}\,dx,\] 因而 \[\sum_{p\in P\cap[1,\,n-n^{2/3})}\frac{1}{n-p}=\int_1^{\infty}\bigl|P\cap[n-x,\,n-n^{2/3})\bigr|\,\frac{dx}{x^2}.\] 当 \(x\le n^{2/3}\) 时被积函数为零。当 \(n^{2/3}n\) 时为 \(\Theta\!\left(\dfrac{n}{x^2\log n}\right)\)。把所有这些估计放在一起，我们得到 (1.50)。而估计 (1.51) 则由 (1.50) 立即推出，因为当 \(p\in[1,n-n^{2/3}]\) 时 \(\log(n-p)=\Theta(\log n)\)。♦

    把 (1.50) 的证明拆开看又是 Abel 法的套路：把权重 \(1/(n-p)\) 写成积分，再交换次序，把“对素数求和”转成“素数计数 \(|P\cap\cdots|\)”，后者正是定理 1.53 能控制的量。
    1. 恒等式：当 \(a=n-p>0\) 时，\(\displaystyle\int_a^\infty\frac{dx}{x^2}=\frac1a=\frac{1}{n-p}\)。用指示函数 \(I(p\in[n-x,n-n^{2/3}))\) 把下限 \(x\ge n-p\) 表达出来。
    2. 交换次序：求和与积分交换后，内层变成“对固定 \(x\)，落在 \([n-x,n-n^{2/3})\) 里的素数个数”，即 \(|P\cap[n-x,n-n^{2/3})|\)。
    3. 分段用定理 1.53：按 \(x\) 的大小把积分分成三段—— \(x\le n^{2/3}\) 区间为空、被积函数为 \(0\)；中段与右段用定理 1.53 把素数个数换成 \(\Theta(\cdot/\log n)\)。
    4. 逐段积分相加：主要贡献来自 \(n^{2/3}n\) 那段贡献也是 \(O(1)\)。合起来 (1.50) 成立。
    5. (1.51) 顺带得到：在求和范围内 \(n-p\) 介于 \(n^{2/3}\) 与 \(n\) 之间，故 \(\log(n-p)\) 总是在 \(\tfrac23\log n\) 与 \(\log n\) 之间，即 \(\Theta(\log n)\)。把这个公共因子提出来乘上 (1.50)，就得到 (1.51) 的 \(\Theta(\log n)\)。

    习题

    习题 1.10.1通过用积分 \(\int_1^{n}\log x\,dx\) 来逼近求和 \(\sum_{m=1}^{n}\log m\)，证明 Stirling 公式 \[\tag{1.52}\log n!=n\log n-n+O(\log n)\] 对一切 \(n>1\) 成立。
    习题 1.10.2利用命题 1.51，证明存在一个常数 \(c\)，使得对每个正整数 \(n\)，在 \(n\) 与 \(cn\) 之间总有一个素数。
    习题 1.10.3通过在 (1.46) 的证明中更加仔细，证明 \[\sum_{pBertrand 假设，即对每个充分大的整数 \(n\)，在 \(n\) 与 \(2n\) 之间存在一个素数。（此论证归功于 Ramanujan。事实上 Bertrand 假设对所有整数 \(n\) 都成立，因为小的 \(n\) 的情形可以直接验证。）
    习题 1.10.4在不使用素数定理的前提下，证明 \(|P\cap[1,n]|=\Theta\!\left(\dfrac{n}{\log n}\right)\)；这被称为 Chebyshev 定理。当然，这个定理被素数定理 \(\pi(n)=(1+o(1))\dfrac{n}{\log n}\) 所取代，但它的优点是有一个简短的初等证明。
    习题 1.10.5证明 \(p_k=\Theta(k\log k)\)，其中 \(p_k\) 表示第 \(k\) 个素数。同样，这被素数定理 \(p_k=(1+o(1))k\log k\) 所取代。
    习题 1.10.6定义 von Mangoldt 函数 \(\Lambda:\mathbb{Z}^+\to\mathbb{R}\)：若 \(n>1\) 是某素数 \(p\) 的幂，则令 \(\Lambda(n):=\log p\)，否则 \(\Lambda(n)=0\)。证明对一切整数 \(n\ge 1\) 有 \[\tag{1.53}\sum_{d\mid n}\Lambda(d)=\log n.\] 用它证明对一切实数 \(s>1\) 有 \[\Bigl(\sum_{n=1}^{\infty}\frac{\Lambda(n)}{n^s}\Bigr)\Bigl(\sum_{n=1}^{\infty}\frac{1}{n^s}\Bigr)=\sum_{n=1}^{\infty}\frac{\log n}{n^s}.\] 此外，利用 (1.53) 给出 (1.49) 的另一个证明。
    习题 1.10.7利用前一道习题，证明对一切 \(s>1\) 有 \[\sum_{p}\frac{\log p}{p^s}=\frac{1}{s-1}+O(1);\] 对其积分，得出对一切 \(s>1\) 有 \[\tag{1.54}\sum_{p}\frac{1}{p^s}=\log\frac{1}{s-1}+O(1).\] 证明这些估计也可经由 Abel 法从命题 1.51 推出。反过来，利用 (1.54) 与 (1.46) 给出 (1.48) 的另一个证明。
    习题 1.10.8利用 Abel 求和法，证明素数定理 \(\pi(x)=(1+o(1))\dfrac{x}{\log x}\) 等价于估计 \(\sum_{n\le x}\Lambda(n)=(1+o(1))x\)。
    习题 1.10.9通过在 (1.48) 的证明中更加仔细，证明 \[\sum_{pMertens 定理 \[\tag{1.55}\prod_{p1\) 成立。（事实上 \(C=e^{-\gamma}\)，其中 \(\gamma=0.577\ldots\) 是 Euler 常数。）
    例：习题 1.10.6 中 (1.53) 是怎么回事取 \(n=12=2^2\cdot 3\)。它的因子 \(d\) 中只有素数幂才让 \(\Lambda(d)\neq0\)：\(\Lambda(2)=\log2\)，\(\Lambda(4)=\log2\)，\(\Lambda(3)=\log3\)（其余 \(d=1,6,12\) 的 \(\Lambda=0\)）。求和 \[\sum_{d\mid 12}\Lambda(d)=\log2+\log2+\log3=\log(2\cdot2\cdot3)=\log12.\] 果然等于 \(\log n\)。直观原因：把 \(n\) 做素因子分解 \(n=\prod p^{a_p}\)，则 \(\log n=\sum_p a_p\log p\)；而 (1.53) 左边对每个素数 \(p\)，正好把 \(\Lambda(p),\Lambda(p^2),\dots,\Lambda(p^{a_p})\) 各贡献一个 \(\log p\)，合计 \(a_p\log p\)。两边逐素数对上。

    返回 全书目录