引理 4.25, 对于任意素数 p, $k \in [1, p), p \mid \binom{p}{k}$. 这个引理忽然让我想到一个问题, 我好像还没证过 $\binom{p}{k} = \frac{p!}{k!(p-k)!}$ 一定是一个整数来着…
4.25.zy1, 对于自然数 1 < m <= n, 一定存在 k 使得 $m^k \le n \lt m^{k+1}$.
证明: 根据陶 analysis 可知指数函数 $f(x) = m^x, R \to (0, +\infty)$ 是个满射且单调递增; 即对于 n, 存在 $x_0, f(x_0) = m^{x_0} = n, x_0 \gt 0$. 所以存在 $k = \left \lfloor x \right \rfloor$.
4.25.zy2, 对于任意实数 a, b; 有 $ \left \lfloor a+b\right \rfloor \ge \left \lfloor a \right \rfloor + \left \lfloor b \right \rfloor$.
证明: 已知 $a = \left \lfloor a \right \rfloor + a’, a’ \in [0, 1), b = \left \lfloor b \right \rfloor + b’, b’ \in [0, 1)$. $a + b = \left \lfloor a \right \rfloor + \left \lfloor b \right \rfloor + a’ + b’$. $\left \lfloor a+b\right \rfloor = \left \lfloor a \right \rfloor + \left \lfloor b \right \rfloor + \left \lfloor a’ + b’ \right \rfloor$ 结论得证.
4.25.zy3, Legendre’s Theorem: 在 n! 的质因数分解中, 即定理 3.17 提到的因数分解, 素数 p 的次数:
\[v_p(n!) = \sum_{i=1}^{\infty} \left \lfloor\frac{n}{p^i}\right \rfloor\]证明: 易证 $\forall n \lt p, v_p(n!)=0$, 这是因为 $n \lt p, \forall i \le n, v_p(i) = 0$, 所以 $v_p(n!) = \sum_{i=1}^nv_p(i) = 0$. 令对于 $\forall i \in (Kp, (K+1)p), v_p(i) = 0$, 这是因为 $i = Kp + r, r \in (0, p), i \equiv r \mod p, p \nmid r$.
所以 n! 中仅有形如 $p, 2p, \cdots, K_1p, K_1 = \left \lfloor \frac{n}{p} \right \rfloor$ 这样的数才会贡献 p 的次数, 即 $v_p(n!) = \sum_{k=1}^{K_1} v_p(kp)$. 在 $p, 2p, \cdots, K_1p$ 中又有 $p^2, 2p^2, \cdots, K_2p^2, K_2 = \left \lfloor \frac{n}{p^2} \right \rfloor$ 个数, 针对这些数 $v_p(jp^2) \ge 2$, 其他的数 $v_p(ip) = 1$. 同理在 $p^{M-1}, 2p^{M-1}, \cdots, K_{M-1}p^{M-1}, K_{M-1} = \left \lfloor \frac{n}{p^{M-1}} \right \rfloor$ 中有 $p^M, 2p^M, \cdots, K_Mp^M, K_M = \left \lfloor \frac{n}{p^M} \right \rfloor$ 个数, 这里 M 满足 $p^M \le n \lt p^{M+1}$, 根据 4.25.zy1 可知这里 M 是必存在的, 且 $K_j = 0, \forall j \gt M$. 所以有:
\[\begin{align} v_p(n!) &= (K_1 - K_2) * 1 + (K_2 - K_3) * 2 + \cdots + (K_{M-1} - K_M) * (M-1) + K_M * M \\ &= K_1 + K_2 + K_3 + \cdots + K_{M-1} + K_M \\ &= \sum_{i=1}^{\infty} \left \lfloor\frac{n}{p^i}\right \rfloor \end{align}\]4.25.zy4, 证明 $\binom{p}{k} = \frac{p!}{k!(p-k)!}$ 是一个整数.
证明: 欲证该表达式为整数, 只需证明对于任意质数 q, $v_q(p!) \ge v_q(k!(p-k)!) = v_q(k!) + v_q((p-k)!)$, 即证 $\sum_{i=1}^{\infty} \left \lfloor\frac{p}{q^i}\right \rfloor \ge \sum_{i=1}^{\infty} \left \lfloor\frac{p-k}{q^i}\right \rfloor + \sum_{i=1}^{\infty} \left \lfloor\frac{k}{q^i}\right \rfloor$.
由 $\frac{p}{q^i} = \frac{k}{q^i} + \frac{p-k}{q^i}$ 结合 4.25.zy2 可得 $\left \lfloor\frac{p}{q^i}\right \rfloor \ge \left \lfloor\frac{p-k}{q^i}\right \rfloor + \left \lfloor\frac{k}{q^i}\right \rfloor$, 结合陶级数相关定理结论可证.
引理 4.25 证明补充说明.
- 证明: $p \nmid k!(p-k)!$.
证明: $p \mid k!(p-k)!$ 意味着 $v_p(k!(p-k)!) \ge 1$. 在 4.25.zy3 证明过程中, 可知由于 $k \lt p, p - k \lt p$, 所以 $v_p(k!) = 0, v_p((p-k)!) = 0$, 所以 $v_p(k!(p-k)!) = v_p(k!) + v_p((p-k)!) = 0$, 所以结论得证.
- 证明 $p \mid \binom{p}{k}$.
证明: $p \mid \binom{p}{k}$ 意味着 $v_p(\binom{p}{k}) \ge 1$, $v_p(\binom{p}{k}) = v_p(p!) - v_p(k!(p-k)!) = v_p(p!) \ge 1$, 结论得证.
命题 4.26, 在 $\mathbb{F}_p$ 中, $(a+b)^p = a^p + b^p$.
证明: 唉, 这个命题这么写非常令人迷惑, 我认为严格的写法应该是 $([a]+[b])^p = [a]^p + [b]^p, [a] = a \mod p, [b] = b \mod p$. 这样我们便清楚欲该定理只需证 $(a+b)^p \equiv a^p + b^p \mod p, a, b, p\in N$ 即可. 别忘了按照域 $\mathbb{F}_p$ 的加法乘法定义 $([a]+[b])^p = ([a+b])^p = [(a+b)^p] = (a+b)^p \mod p$.
这样就像原文所说, 结合二项式展开以及引理 4.25 很容易证明.
4.26.zy1, 已知 $a \equiv b + c \mod p, b \equiv d \mod p$ 求证 $a \equiv d + c \mod p$.
证明: $b \equiv d \mod p$ 意味着 $0 \equiv d-b \mod p$, 结合命题 4.6(1) 可得 $a + 0 \equiv b + c + d -b \mod p$, 即结论得证.
4.8.zy4, 这里扩充下命题 4.8(3), 设 $m_1, \cdots, m_n$ 互素, 已知 $a \equiv b \mod m_1 \cdots m_n$, 则 $a\equiv b \mod m_i, i \in [1, n]$ 成立.
证明: 根据 4.21 中国剩余定理, 已知 $a \equiv b \mod m_1 \cdots m_n$, 即 $a \mod m_1 \cdots m_n$ 与 $b \mod m_1 \cdots m_n$ 在集合 $Z/m_1 \cdots m_nZ$ 中表示相同元素. 即 $\Phi(a \mod m_1 \cdots m_n) = \Phi(b \mod m_1 \cdots m_n)$, 即 $(a \mod m_1, \cdots, a \mod m_n) = (b \mod m_1, \cdots, b \mod m_n)$. 即集合 $a \mod m_i$, $b \mod m_i$ 在集合 $Z/m_iZ$ 中表示相同元素, 即 $a \equiv b \mod m_i$.
欧拉定理再证明, 这里重新整理下, 原文有一些关键性笔误, 比如把 $a^{\varphi(p_i^{e_i})} \equiv 1 \mod p_i^{e_i}$ 误写为 $a^{p_i^{e_i}} \equiv 1 \mod p_i^{e_i}$, 可是让我一阵苦思.
证明: 设 m 质因数分解为 $m = p_1^{e_1}\cdots p_s^{e_s}, \varphi(m)=\varphi(p_1^{e_1})\cdots \varphi(p_s^{e_s})$. 欲证 $a^{\varphi(m)} \equiv 1 \mod m$, 根据 4.8.zy4 只需证 $a^{\varphi(m)} \equiv 1 \mod p_i^{e_i}$ 即可. 根据命题 4.6(2) 可知只要证了 $a^{\varphi(p_i^{e_i})} \equiv 1 \mod p_i^{e_i}$, 那么 $a^{\varphi(m)} = (a^{\varphi(p_i^{e_i})})^{\varphi(p_1^{e_1})\cdots \varphi(p_{i-1}^{e_{i-1}})\varphi(p_{i+1}^{e_{i+1}})\cdots \varphi(p_s^{e_s})} \equiv 1 \mod p_i^{e_i}$ 便成立. 接下来根据原文证法证明 (4.16) 成立即可, 别忘了 $\varphi(p_i^{e_i}) = p_i^{e_i-1}(p_i - 1)$.
命题 4.28, 略作补充
-
原文 $a^p = a$ 即 $[a^p] = [a]$, 即 $a^p \equiv a \mod p$, 这即是定理 4.24 费马小定理的内容.
-
原文 $a^{-1} = a^{p-2}$, 是指 [a] 在域 $\mathbb{F}_p$ 的乘法逆元 $[a]^{-1}$ 为 $[a^{p-2}]$.
证明: 这里 a 不为 0, 即 a 在域 $\mathbb{F}_p$ 中可逆, 即 $a \in \mathbb{F}_p^{\times}$, 即 (a, p) = 1, 根据 4.23.zy3, 定理 4.24 可知 $a^{p-1} \equiv 1 \mod p$. 根据根据命题 4.6(2) 可知 $a^{p-1}a^{p-1} \equiv 1 \mod p$, 即 $a^p a^{p-2} \equiv 1 \mod p$, 即 $[a^p]$ 乘法逆元为 $[a^{p-2}]$.
