注：本节内容为《具体数学》(原书第二版) 第四章 数论 4.4 阶乘的因子 的旁注。
P93 引理：$k(n+1-k)\leq (k+1)(n-k), k\leq n/2$
证明：
$$
k(n+1-k)\leq (k+1)(n-k)
$$
$$
\Leftrightarrow nk + k - k ^2 \leq nk + n - k^2 - k
$$
$$
\Leftrightarrow k \leq n / 2
$$
Q.E.D.
这个可以帮我们说明书中的：
$$
n \leq k(n+1-k) \leq \frac {n+1} 2 \frac {n+1} 2
$$
因为前半段即为：
$$
1 \times (n+1-1) \leq k(n+1-k), 1 \leq k \leq n
$$
对于后半段，我们稍作处理。所有项中最大的结果为：
$$
\frac n 2 (\frac n 2 + 1)
$$
易证其小于
$$
\frac {n+1} 2\frac {n+1} 2 = \frac {n^2} 4 + \frac n 2 + \frac 1 4
$$
P95 $\epsilon_2(n!)$ 的证明
试证：
$$
\epsilon_2(n!) = n - v_2(n)
$$
证明：
我们已经证明了:
$$
\epsilon_2(n!) = \sum_{k\geq 1} \Big \lfloor \frac n {p^k} \Big \rfloor
$$
我们不妨考虑 $n$ 的二进制位表示。上面这个式子当中对于每一个二进制中位是 $1$ 的第 $k$ 位的贡献都为
$$
2^0 + 2^1 + \cdots + 2^{k-1} = 2^k - 1
$$
而其原来的贡献为 $2^k$，所以对于每一个是 $1$ 的位，其对答案的贡献都损失 $1$。所以最后的答案即为:
$$
n - v_2(n)
$$
P95 无穷多素数另一个证明的补充
补充一下推出矛盾的公式的推导：
已知
$$
n = 2^{2k}
$$
则
$$
n^{n / 2} = (2^{2k})^{2^{2k} / 2} = (2^{2k})^{2^{2k-1}} = 2^{2k \times 2^{2k-1}} = 2^{k2^{2k}}
$$
也就可以得到
$$
n! < 2^{nk} = 2^{k2^{2k}} = n^{n/2}
$$
P95 素数的粗略界的补充
在本页的最后书上给出了素数的一个粗略的近似。
$$
n! < 2^{n\pi(n)}
$$
这样做的原因是：
- 我们已经证明了对于 $n!$，每个素数的贡献是小于 $2^n$ 的
- $n!$ 由于是 $n$ 的阶乘，所以不可能有大于 $n$ 的素数成为贡献，也就是能贡献的素数个数就是 $\pi(n)$，也就是不大于 $n$ 的素数的个数。
所以我们便有了上面的不等式。
