定理 8.7, 略作补充
- $m = m_1 \cdot m_2, m_1, m_2 \gt 2, (m_1, m_2) = 1$, 证明下这里 m 总能分解出满足条件的 $m_1, m_2$.
证明: 从定理 3.17 可以看出 $m = 2^{v_2(m)}\prod_{p \gt 2}p^{v_p(m)}$. 若 $v_2(m) = 0$, 则由上下文易知 m 一定可以分为 $p_1^{v_1} p_2^{v_2} p_3^{v_3}$ 这种形式, 即 m 分解中 $v_p(m) \gt 0$ 的 p 至少 2 个, 此时随便切分一下便得 $m_1, m_2$.
若 $v_2(m) = 1$, 则由上下文易知 m 一定可以分为 $2 p_1^{v_1} p_2^{v_2} p_3^{v_3}$ 这种形式, 即 m 分解中 $p \gt 2, v_p(m) \gt 0$ 的 p 至少 2 个. 此时随便切分一下即可. 同理易证若 $v_2(m) \ge 2$ 情况.
- $(\mathbb{Z}/m\mathbb{Z})^{\times}$ 任何元素的阶 $d \mid \varphi(m)/2$.
证明: $x = (\varphi(m_1), \varphi(m_2)), y = [\varphi(m_1), \varphi(m_2)], xy=\varphi(m_1)\varphi(m_2)$, 且这里 $2\mid x, x=2x’, 2x’y = \varphi(m_1)\varphi(m_2)$. 由引理 8.8, 8.2.zy2 可知 $d \mid y$ 自然 $d \mid \frac{\varphi(m_1)\varphi(m_2)}{2}$.
P.S. 这里原文印刷问题么, 印刷成任何元素的阶总能被 $\varphi(m)/2$ 整除了, 应该是阶总能整除 $\varphi(m)/2$.
- 8.1.2 原根的计算,
解: 在 (3) 中, 若 g 是奇数, 此时 $(g, p^k) = 1, (g, 2) = 1, (g, 2p^k) = 1$, 即 $g \in (\mathbb{Z}/2p^k \mathbb{Z})^{\times}$. 根据 4.18 易知 $(\mathbb{Z}/2p^k \mathbb{Z})^{\times} \cong (\mathbb{Z}/p^k \mathbb{Z})^{\times}$ 中的映射 $\Phi(a \mod 2 p^k) = a \mod p^k$. 所以可知 $g \in (\mathbb{Z}/2p^k \mathbb{Z})^{\times}$ 的阶与 $g \in (\mathbb{Z}/p^k \mathbb{Z})^{\times}$ 一致.
若 g 是偶数, 假设 $\Phi(g’ \mod 2 p^k) = g \mod p^k, p^k \mid g - g’$, 易证 $g+p^k$ 为奇数且 $(g+p^k, p^k) = (g, p^k) = 1, (g+p^k, 2p^k) = 1, g+p^k \in (\mathbb{Z}/2p^k \mathbb{Z})^{\times}$.
命题 8.11, 略作补充. 这里 $x^k \equiv a \mod m$ 等价于 $(x \mod m)^k = a \mod m$, 这里 $x \mod m, a \mod m$ 是 $\mathbb{Z}/m\mathbb{Z}$ 中的元素, 对应着命题 6.8 中的 x, a.
定义 8.12, 原文 $\mathbb{F}_p^{\times 2} = { a^2 | a \in \mathbb{F}_p^{\times} } = { 1, g^2, \cdots, g^{p-2} }$, 我理解的应该是 ${ 1, g^2, \cdots, g^{2(p-2)} }$.
我理解原文这是印刷错误. 但又不是很确定, 毕竟在模集合中, 两个不同的数取模之后可能相同. 即 $g^{2(p-2)} \equiv g^{p-2} \mod p$ 也说不定, 但我试图化解半天也没得到这个结论. 暂且认为这里确实是印刷错误. 举例: $\mathbb{F}_5^{\times 2} = {1, 4}$.
定理 8.14, 略作补充. 这里解释下 $\left(\frac{g^k}{p}\right) = (-1)^k$.
解: 首先若 $g^x$ 是二次剩余, 即 $\exists k, x \equiv 2k \mod p-1$, 这里 p 为奇数, 易证 x 不可能是奇数. 对于 $\mathbb{F}_p^{\times}$ 中 $g^x$, 若 x 是偶数 $x = 2k$, 则易知 $\mathbb{F}_p^{\times}$ 中的 $g^k$ 会被映射到 $\mathbb{F}_p^{\times 2}$ 中的 $g^{2k} = g^x$.
命题 8.15, 这里证明下 (3) 推出 (2)
证明: 已知 $x^2 - a$ 可约, 即 $\exists a_1, a_2; x^2 - a = (x + a_1)(x + a_2)$, 即 $a_2^2 = a$ 有解 $a_2$.
命题 8.16, 略作补充.
解: 当 a = 0 时, $\mathbb{F}_p$ 是域, 是整环, 所以 x 只能为 0, 即只有 1 个解. 当 $a \in \mathbb{F}_p^{\times}$, 易知解 $x \in \mathbb{F}_p^{\times}$. 此时原方程等同于 $(x \mod p)^2 = a \mod p$, 令 g 表示原根, $x \mod p = g^y, a \mod p = g^{2k}$, 这里只考虑 a 为二次剩余情况, a 为二次非剩余时易证无解. 即 $2y \equiv 2k \mod p-1$, 根据 6.8.zy2 可知有两解分别是 $x=g^k, x = g^{k + \frac{p-1}{2}}$.
公式 (8.8) 推导, 设 $a = mn, (a, p) = 1, \left(\frac{a}{p}\right) = \left(\frac{m}{p}\right)\left(\frac{n}{p}\right)$.
证明: 此时 $(a, p)=1, a\mod p \in \mathbb{F}_p^{\times}$, 同时易证 $(m, p) = (n, p) = 1, m\mod p \in \mathbb{F}_p^{\times}, n\mod p \in \mathbb{F}_p^{\times}$.
\[\begin{align} \left(\frac{a}{p}\right) &= \left(\frac{a \mod p}{p}\right) \\ &= \left(\frac{m \mod p \cdot n \mod p}{p}\right) \\ &= \left(\frac{m \mod p}{p}\right) \left(\frac{n \mod p}{p}\right) \\ &= \left(\frac{m}{p}\right)\left(\frac{n}{p}\right) \end{align}\]8.17.zy1, p 为奇素数, 考虑 g 为模 p 原根之一, 求证 $-1 \mod p = g^{\frac{p-1}{2}}$
证明: 假设 $g^x, x \in [0, p-1)$ 逆元为自身, 则 $p-1 \mid 2x$ 易知 x 只能为 0 或者 $\frac{p-1}{2}$. 易证 $-1 \mod p \ne 1 \mod p$, 否则 $-1 \equiv 1 \mod p, p \mid 2$, 矛盾! 且 $-1 \mod p$ 逆元为自身, 则 $-1 \mod p$ 只能是 $g^{\frac{p-1}{2}}$ 了.
命题 8.17, 欧拉判别法, 针对 $p \nmid a$ 情况略作补充, 这里原文有几处印刷问题.
证明: 如下所示, 文中公式等价于 $(-1)^k \mod p = g^{\frac{p-1}{2}k \mod p-1}$.
\[\begin{align} \left(\frac{a}{p}\right) \mod p &= (a \mod p)^{\frac{p-1}{2}} \\ \left(\frac{a}{p}\right) \mod p &= (-1)^k \mod p \\ (a \mod p)^{\frac{p-1}{2}} &= g^{\frac{p-1}{2}k \mod p-1} \end{align}\]当 k 为偶数时, 易证公式成立. 当 k 为奇数时等同于求证 $-1 \mod p = g^{\frac{p-1}{2}}$.
P.S. 妹的, 一开始看成了 $\left(\frac{a}{p}\right) = a^{\frac{p-1}{2}} \mod p$, 还似模似样算了半天后意识到, 不对呀, 左侧是值 $-1, 0, 1$, 右侧是同余类啊..
命题 8.19 略作补充, 原文有几处 typo.
-
$\lambda + \mu = r$, 我还试图证明有一些 $ia, ia \mod p = \frac{p}{2}$, 之后才意识到 $\frac{p}{2}$ 都丫的不是整数…
-
$\forall i, j; p \nmid ia - ja, p \nmid ia + ja$
证明: 假设 $p \mid ia - ja, (a, p) = 1, p \mid i-j$, 在 $0 \le i \lt j \le r$ 情况下, 这是不可能的. 同理 $p \mid ia + ja, p \mid i + j$ 也不可能.
- $A={b_1, \cdots, b_\lambda, p - c_1, \cdots, p - c_\mu} = {1, \cdots, r}=B$
证明: 由上下文可知, 集合 A 中元素互不相等, 且取值均位于 $[1, r]$, 且 A 中元素个数为 r. 易得结论.
- $r! \equiv (-1)^\mu a^r r! \mod p$
证明: 易证 $c_i - p \equiv c_i \mod p$, 结合 4.6(2) 可得 $\prod_{i=1}^\mu(c_i - p) \equiv \prod_{i=1}^\mu c_i \mod p$. 所以 $b_1 \cdots b_\lambda (p-c_1) \cdots (p-c_\mu) \equiv b_1 \cdots b_\lambda (-1)^\mu c_1 \cdots c_\mu \mod p$. 继而得 $r! \equiv (-1)^\mu a^r r! \mod p$.
由 3.14, 欧几里得引理可得 $(p, r!) = 1$, 即而 $1 \equiv (-1)^\mu a^r \mod p, (-1)^\mu \equiv a^r \mod p$. 根据 8.17 欧拉判别法 $\left( \frac{a}{p}\right) \equiv a^r \mod p$, 所以 $\left( \frac{a}{p}\right) \equiv (-1)^\mu \mod p$. 继而易得结论.
推论 8.20, 这里 $2, 2\cdot 2, \cdots, r \cdot 2$ 都是 $\le p$ 的, 所以她们除以 p 所得余数就是自身. 同时这里 $\gt p/2$ 等同于 $\ge 4k+4$.
定理 8.21, 二次互反律. 这里公式 (8.11) p, q 不全为 $3 \mod 4$ 的意思是指计算 $p \mod 4, q \mod 4$; 若这俩值均为 3 则意味着 $\left( \frac{q}{p}\right) = - \left( \frac{p}{q}\right) $; 若这俩值至少有一个不为 3, 则意味着 $\left( \frac{q}{p}\right) = \left( \frac{p}{q}\right) $.
例 8.23, $x^2 + 6$ 可约等同于 $(x+1)^2 + 6$ 可约
证明: 若 $(x+1)^2 + 6 = (x+a)(x+b)$, 易证此时 $x^2 + 6 = (x + a - 1)(x + b - 1)$.
