4.2.zy1, $a \equiv b \mod m$ 当且仅当在定理 3.3 带余除法表示中 $a = mq_1 + r_1, b = mq_2 + r_2, r_1 = r_2$.
证明: 若 $a \equiv b \mod m$, 即 $m \mid a - b$, 即 $a - b = mk, a = b + mk = mq_2 + r_2 + mk = m(q_2 + k) + r_2$, 由定理 3.3 带余除法唯一性可知 $q_2 + k = q_1, r_2 = r_1$.
命题 4.8(3) 的证明.
证明: $\forall i, m_i \mid a - b$, 所以 a - b 是 $m_i$ 的公倍数, 结合命题 3.11(1) 可得 $[m_1, \cdots, m_n] \mid a - b$ 得证.
4.11.zy1, 这里若 m 是素数, 则 Z/mZ 是整环.
证明: 假设 Z/mZ 不是整环, 即存在元素 [a] != [0], [b] != [0], [a][b] = [0]; 由 (4.4) 可知, 这里总存在 i, j 位于 [0, m) 之间使得 [a] = [i], [b] = [j]; 此时 [i][j] = [ij] = [0], 意味着 $ij \mid m$, 这与 m 是素数矛盾.
定理 4.12, 这里应该印刷错误. $(Z/mZ)^{\times} = {[a] | (a,m) = 1, 0 \le a \lt m}$. 因为由 (4.4) 可知, [0] = [m].
命题 4.18(3), 这里补充下满射证明:
证明: 欲证明是满射, 只需证明 $\forall a \in Z/mZ, b \in Z/nZ, \exists c, \Phi(c)=(a, b)$ 即可. 此时 $c \mod m = a \mod m, c \mod n = b \mod n$, 即 $c \equiv a \mod m, c \equiv b \mod n$; 注意 $c \mod m, a \mod m$ 都是集合的表示. 即 $\exists k_1, c - a = mk_1, c - b = nk_2$. 即要找到 $k_1, k_2$ 使得 $a - b = nk_2 - mk_1$, 而根据 bezout 等式, $nk_2 - mk_1$ 恰好是 $(m, n)Z=Z$, 所以一定存在这样的 $k_1, k_2$, 即 c 是存在的.
P.S. 我其实是没理解原文 “映射两边均是 mn 元集合, 只要证明 $\Phi$ 是单射即可” 啥意思才琢磨出上面满射的证明. 在我完成满射证明之后也就理解原文这句话意思了.. 简单来说就是映射 f 定义域值域都是有限集合且具有相同数目的元素, 若 f 是单射, 则 f 也一定是满射.
推论 4.19, 这里对证明略作补充.
- 原文证明依赖这么个小结论, 设 f 是集合 A 到 B 的双射, $A = A_1 \cup A_2, A_1 \cap A_2 = \emptyset; B = B_1 \cup B_2, B_1 \cap B_2 = \emptyset$. 且同时 f 也是 $A_1$ 到 $B_1$, $A_2$ 到 $B_2$ 的映射. 则 f 是 $A_1$ 到 $B_1$ 的双射.
证明: 这里主要证明下 $f:A_1 \to B_1$ 是满射, 即 $\forall b \in B_1, \exists a \in A_1, f(a) = b$. 假设 $A_1$ 中不存在 a, 则由于 f 是 A 到 B 的双射, 则意味着 $\exists a \in A_2, f(a) = b$, 这违背了 $f: A_2 \to B_2$ 的前提.
- 4.19.zy1, 若 f 是环 $R_1 \to R_2$ 的同构, 则 f 逆函数 $f^{-1}$ 是 $R_2 \to R_1$ 的同构.
证明: 根据环同构定义易证.
- 4.19.zy2, 若 f 是环 $R_1 \to R_2$ 的同构, 则 f 也是群 $R_1^{\times} \to R_2^{\times}$ 的群同构.
证明: 根据命题 2.51 可知若 g 可逆, 则 f(g) 也可逆. 即 $f: R_1^{\times} \to R_2^{\times}$. 接下来我们证明 f 是满射. 因为 f 是 $R_1 \to R_2$ 的双射, 所以存在逆函数 $f^{-1}: R_2 \to R_1$ 也是环同构, 且对于 $\forall y \in R_2^{\times}, \exists x \in R_1^{\times}, f(x) = y$.
推论 4.20, 略作补充
- $(p,q) = 1 \to (p^i, q^j) = 1$
证明: 见命题 3.8(4) 可知 $(p,q) = 1 \to (p, q\times q) = 1 \to (p, q^j) = 1$. 证明结束.
- $\varphi(p^s) = (Z/p^sZ)^{\times} = {a | (a, p^s) = 1, a\in [0, p^s)}$, $(a, p^s) = 1$ 意味着 (a,p) = 1. 证明 $A={a | (a, p) = 1, a\in [0, p^s)} = {x + yp|x \in (0, p-1], y\in [0,p^{s-1})}=B$.
证明: 已知 $\forall a\in A, (a,p)=1$ 根据定理 3.3 可知 $a = p*k + r, r \in (0, p-1], k \in [0,p^{s-1}), A \subseteq B$. 现在 $\forall b \in B$, 易证 $b \in [0, p^s)$, 根据命题 3.5(4) 可知 (b, p)=(x + yp, p) = (x,p) = 1. 即 $B\subseteq A$. 结论得证.
定理 4.22, 这里补充下证明.
证明: 令 $(a_1 \mod m_1, \cdots, a_n \mod m_n) \in Z/m_1Z \times \cdots \times Z/m_nZ$. 可知 $\exists c, \Phi(c \mod m_1 \cdots m_n) = (a_1 \mod m_1, \cdots, a_n \mod m_n) = (c \mod m_1, \cdots, c \mod m_n)$. 现在 $\forall x \in c \mod m_1 \cdots m_n, x \equiv c \mod m_1 \cdots m_n$ 由命题 4.8(1) 可知 $x \equiv c \mod m_i, i \in [1, n]$. 结合 $c \equiv a_i \mod m_i$ 可知 $x \equiv a_i \mod m_i$.
现在对于其他同余类 $\forall c’ \in Z/m_1 \cdots m_nZ$ 易证这些同余类中元素不满足定理中的解.
定理 4.23, 原文这个证明我没看懂== 符号使用上有点混乱. 以 $[a]r_i$ 为例, 这里我理解 $[a] = a \mod m$ 即 m 的一个同余类, $[a]r_i = {xr_i | x \in [a]}$, 但 $[a]r_1\cdots[a]r_{\varphi(m)}$ 集合乘以集合? 我就实在解释不了了. 幸运的是在 欧拉定理 wiki 中找到了与原文类似的证明. 这里总结下.
4.23.zy1, 已知 Z/mZ 集合有多种表示形式, 其可以写成 ${[a_1], \cdots [a_m]}$, 也可以写成 ${[b_1], \cdots [b_m]}$, 这里 $[a_i], [b_i]$ 都是 m 的一个同余类. 证明这里 $\prod_{i=1}^m a_i \equiv \prod_{j=1}^m b_j \mod m$.
证明: 由 (4.4) 可知 $\forall i, \exists j, a_i \equiv b_j \mod m$, 据此定义映射 f, $a_i \equiv b_{f(i)} \mod m$, 易证 f 是双射. 则由命题 4.6(2) 可得 $\prod_{i=1}^m a_i \equiv \prod_{i=1}^m b_{f(i)} \mod m$, 结合 $\prod_{i=1}^m b_{f(i)} = \prod_{j=1}^m b_j$ 结论可证.
P.S. 关于这里映射 f 存在性说明. 首先 Z/mZ 有一个主表示(我自己起的名字)是 ${[0], \cdots, [m-1]}$, 对于 Z/mZ 其他表示 ${[a_1], \cdots [a_m]}$, 对于每一个 $a_i$ 我们都可以使用 $a_i$ 除以 m 得到的余数 $a_i’$ 替代, 易知这里 ${[a_1’], \cdots [a_m’]} = {[0], \cdots, [m-1]}$; 因为若 $i\in [0, m)$ 不存在于 ${[a_1’], \cdots [a_m’]}$, 那么 ${[a_1’], \cdots [a_m’]}$ 就不能算是 Z/mZ 的一个表示.
P.S. 同理对于 $(Z/mZ)^{\times}$, 其也可以有多种表示, 其主表示由定理 4.12 定义. 实际上对于每一个集合 ${[r_1], \cdots, [r_{\varphi(m)}]}$, 只要其满足:
- $\forall i, (r_i, m) = 1$
- $\forall i\ne j, r_i \not\equiv r_j \mod m$
- 集合元素的个数为 $\varphi(m)$.
那么该集合就可以看作 $(Z/mZ)^{\times}$ 一种表示. 即使用 $r_i’$ 作为 $r_i$ 除以 m 得到的余数, 那么易证 $A={[r_1’], \cdots, [r_{\varphi(m)}’]} \subseteq {[a]|(a,m)=1, a\in[0,m)} = B$, 根据定义 4.13 可知这里 $\varphi(m)$ 便是集合 B 元素个数, 所以这里 A, B 均为有限集合且个数相同, 且 $A\subseteq B$ 则只能是 A = B.
P.S. 也即若 ${[a_1], \cdots, [a_{\varphi(m)}]}$, ${[b_1], \cdots, [b_{\varphi(m)}]}$ 均是 $(Z/mZ)^{\times}$ 表示, 则 4.23.zy1 提到的映射 f 同样存在; 即 $\prod_{i=1}^{\varphi(m)} a_i \equiv \prod_{j=1}^{\varphi(m)} b_j \mod m$ 也成立.
4.23.zy2, 接着 4.23.zy1 可知对于 Z/mZ 集合中不同的元素 $[a_i], [a_j], i \ne j$; 则 $a_i \not\equiv b_j \mod m$.
证明: 因为 $a \equiv b \mod m$ 等价于集合 $a \mod m, b \mod m$ 相同.
4.23.zy3 消去, 已知 (k, m) = 1; 则 $kx \equiv ky \mod m$ 当且仅当 $x \equiv y \mod m$.
证明: 由 $kx \equiv ky \mod m$ 结合 $kx \equiv ky \mod k$, 根据命题 4.8(3) 可知 $kx \equiv ky \mod [k, m]$, 又因为 (k, m)=1, 所以 $[k, m] = km$, 即 $kx \equiv ky \mod km$, 根据命题 4.8(2) 可知 $x \equiv y \mod m$.
由 $x \equiv y \mod m$ 结合命题 4.8(2) 可知 $kx \equiv ky \mod km$ 再由命题 4.8(1) $m\mid km, kx \equiv ky \mod m$.
4.23 证明: 设 $(Z/mZ)^{\times} = {[r_1], \cdots, [r_{\varphi(m)}]}$, 由定理 4.12 可知 $(r_i, m) = 1, i \in [1, \varphi(m)]$. 由 4.23.zy2 可知 $r_i \not\equiv r_j \mod m, i\ne j$, 则由 4.23.zy3 易证 $ar_i \equiv ar_j \mod m$ 当且仅当 i=j. 且根据命题 3.8(4) $(a,m)=1, (r_i,m)=1, (ar_i,m)=1$. 则可知 ${[ar_1], \cdots, [ar_{\varphi(m)}]}$ 也是 $(Z/mZ)^{\times}$ 的一种等价表示. 即:
\[\prod_{i=1}^{\varphi(m)}ar_i \equiv \prod_{i=1}^{\varphi(m)}r_i \equiv a^{\varphi(m)}\prod_{i=1}^{\varphi(m)}r_i \mod m\]由命题 3.8(4) 可知 $(\prod_{i=1}^{\varphi(m)}r_i, m) = 1$, 则根据 4.23.zy3 易证 $1 \equiv a^{\varphi(m)} \mod m$.
