第 18 章：辨清几个计数问题，再用练习回查

本章保留原对话问过的素数数量、质因子数量及欧拉函数的区别。解析数论的渐近公式只作拓展，不参加前面的RSA证明。练习先挑你刚读过的主题，解答用于核对步骤。

18.1 三种“个数”不要混淆

问题	记号	例子
不超过 $x$ 的素数有多少个	$\pi(x)$	$\pi(12)=5$ ：2、3、5、7、11
$n$ 有多少种不同质因子	$\omega(n)$	$\omega(360)=3$
$n$ 的质因子算重数后有多少个	$\Omega(n)$	$\Omega(360)=3+2+1=6$
代表范围内与 $n$ 互质的整数有多少个	$\varphi(n)$	$\varphi(360)=96$

如果 $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ ，则 $\omega(n)=k$ 、 $\Omega(n)=\sum_i\alpha_i$ ，并约定 $\omega(1)=\Omega(1)=0$ 。因每个质因子至少为 $2$ ， $n\ge2^{\Omega(n)}$ ，所以

$\omega(n)\le\Omega(n)\le\lfloor\log_2n\rfloor.$

若有 $k$ 个不同质因子，把它们排序后第 $i$ 个不小于第 $i$ 个质数，所以 $n$ 至少是前 $k$ 个质数的乘积。因此 $n<6$ 时最多一种， $n<30$ 时最多两种， $n<210$ 时最多三种。这个上界讨论的是最大可能数量，不能当成给定整数的实际数量。

18.2 素数计数与渐近公式：只介绍拓展结论

素数定理为

$\pi(x)\sim\frac{x}{\ln x}\quad(x\to\infty).$

$\sim$ 表示两者比值趋于 $1$ ，不是精确相等；相对误差趋于 $0$ ，也不意味着绝对误差趋于 $0$ 。对整数 $n$ ，“小于 $n$ ”的计数是 $\pi(n-1)$ ，不是 $\pi(n)$ 。参看 Carl Pomerance 的数论讲义。

上限 $n$	不超过 $n$ 的素数实际个数	$n/\ln n$ （约）
10	4	4.3
100	25	21.7
1000	168	144.8
10000	1229	1085.7
100000	9592	8685.9
1000000	78498	72382.4

接近大数 $x$ 的整数“成为素数的密度约为 $1/\ln x$ ”是一种启发式解释，不是证明。对数积分是更精细的经典近似；采用从 $2$ 起积分的记号时，可写 $\operatorname{Li}_2(x)=\int_2^xdt/\ln t$ 。它与采用主值积分定义的 $\operatorname{li}(x)$ 相差常数，记号应说明约定。

原对话还提到不同质因子数的最大值与平均值，其渐近量级分别是 $\ln x/\ln\ln x$ 与 $\ln\ln x$ 。它们是关于一批整数的统计结论，不是计算 $\omega(n)$ 的精确公式。为把平均与正常数量分开，准确写成

$\max_{1\le m\le x}\omega(m)\sim\frac{\ln x}{\ln\ln x},\qquad \frac1{\lfloor x\rfloor}\sum_{m\le x}\omega(m)\sim\ln\ln x.$

Hardy–Ramanujan 定理的核心是“正常数量”：对每个固定 $\varepsilon>0$ ，除占比趋于 $0$ 的例外整数外， $\omega(m)$ 接近 $\ln\ln m$ ，相对偏差小于 $\varepsilon$ 。平均值结论与正常数量结论相关，但不是同一个陈述；这一区别可参看 Carl Pomerance 关于数量阶的讲义。

以上解析数论结论不在本篇的证明范围内，也不参与 RSA 正确性证明。拓展资料可参看数论笔记中的算术函数阶。

18.3 练习与解答

题 1。 求 $3^{100}$ 模 $7$ 的余数。
解： $100\equiv4\pmod6$ ， $3^{100}\equiv3^4=81\equiv4$ 。

题 2。 对任意整数 $a$ ， $a^6\equiv1\pmod7$ 与 $a^7\equiv a\pmod7$ 哪个必成立？
解：第二个。第一个还需 $7\nmid a$ ，取 $a=7$ 即得反例。

题 3。 解 $2x\equiv3\pmod5$ 。
解： $2$ 的逆元为 $3$ ，所以 $x\equiv9\equiv4\pmod5$ 。

题 4。 已知 $\operatorname{ord}_{17}(3)=16$ ，求 $3^4$ 的阶。
解： $16/\gcd(16,4)=4$ 。直接检验 $3^4\equiv13$ ， $13^2\equiv-1$ ， $13^4\equiv1$ 。

题 5。 解 $x\equiv1\pmod4$ 、 $x\equiv3\pmod6$ 。
解：公约数 $2$ 整除余数差 $2$ ，有解。写 $x=1+4t$ ，得到 $2t\equiv1\pmod3$ ，所以 $t\equiv2$ ， $x\equiv9\pmod{12}$ 。

题 6。 对 $n=55,e=3,d=27$ ，消息 $m=0,11,54$ 是否都能恢复？
解：是。第 7.3 节已覆盖任意消息，包括 $0$ 与质因子倍数。加密余数分别为 $0,11,54$ ，相应解密余数也是它们本身。

题 7。 一个 $12$ 阶循环群中，阶为 $1,2,3,4,6,12$ 的元素分别有多少个？解：分别为 $\varphi(d)=1,1,2,2,2,4$ ，总和为 $12$ ；其他正整数不整除 $12$ 时个数为 $0$ 。

题 8。 已知 $h$ 模 $13$ 的阶为 $4$ ， $h=8$ ，求 $h^{2026}$ 。解：指数对 $4$ 取余为 $2$ ，幂的值仍模 $13$ ，所以 $8^{2026}\equiv8^2\equiv12\pmod{13}$ 。

题 9。 两个独立随机变量的分布为 $(1/4,1/4,1/2)$ 与 $(1/2,1/2,0)$ ，它们相等的概率是多少？为何仍可写上界 $1/2$ ？解：按相同位置作乘积并求和得 $1/4$ 。第二分布每项至多 $1/2$ ，以第一分布为权重，权重总和为 $1$ ，所以通用上界为 $1/2$ 。上界不等于精确值。

题 10。 对 $n=55,e=3,d=7$ ，连续平方分解仍可用吗？解： $ed-1=20=\lambda(55)$ ，不是 $\varphi(55)=40$ 的倍数，但条件已足够。 $20=2^2\cdot5$ ；取 $a=2$ 得 $32,34,1$ ，照样提取 $11,5$ 。互质底数成功概率仍为 $3/4$ 。