继续阅读 Davenport 的《高等算术》的第三章。这一章讲了原根、二次剩余和二次互反律。这些内容在 Pinter 的《抽象代数》第二十三章也略有涉及。本章提到了欧拉准则、高斯引理，并给出了二次互反律的证明。

3.6 证明 \(2^k\) 当 \(k>2\) 时没有原根。

证明 如果 \(2^k\) 有原根，那么它必须能生成与 \(2^k\) 互质的所有数。在同构意义下，即小于 \(2^k\) 的所有奇数，共 \(2^{k-1}\) 个。

首先，偶数肯定不可能是原根，因为偶数的任意次方模 \(2^k\) 都是偶数，不可能是 \(1\)。

下面证明任意奇数的阶都小于 \(2^{k-1}\)。事实上，当 \(k>2\) 时，对任意奇数 \(x\) 都有 \(x^{2^{k-2}} \equiv 1 \pmod {2^k}\)。

当 \(n=2^3=8\) 时，不难验证 \[1^2\equiv 1, 3^2\equiv 1, 5^2\equiv 1, 7^2\equiv 1\pmod 8\] 假设 \(x^{2^{k-2}} \equiv 1 \pmod {2^k}\)，那么 \(x^{2^{k-2}}-1=t2^k\)，其中 \(t\) 是整数。于是 \begin{align*} x^{2^{k-1}}-1 &= \bigl(x^{2^{k-2}}\bigr)^2-1 \\ &= \bigl(x^{2^{k-2}}+1\bigr)\bigl(x^{2^{k-2}}-1\bigr) \\ &= (t2^{k-1}+1)t2^{k+1} \\ \end{align*} 这表明 \(x^{2^{k-1}}-1 \equiv 0 \pmod {2^{k+1}}\)，即 \(x^{2^{k-1}}\equiv 1 \pmod{2^{k+1}}\)。根据数学归纳法，可知 \(x^{2^{k-2}}\equiv 1\pmod {2^k}\) 对任意 \(k=3,4,5,\ldots\) 都成立。这表明任意奇数的阶至多是 \(2^{k-2}\)，因此不可能是原根。

综上所述，\(2^k\) 没有原根。

3.10 证明模质数 \(p\) 的原根总是恰有 \(\phi(p-1)\) 个。

证明 本章已经证明了模 \(p\) 运算总是存在原根。设原根是 \(g\)。那么，\(g^n\equiv 1 \pmod p\Rightarrow P\mid n\)，其中 \(P=p-1\)。

显然 \(p\) 的倍数不是原根。设 \(p\nmid x\)，那么 \(x=g^a\)，其中 \(a\) 是 \(x\) 模 \(p\) 的指数。令 \(x^n=1\)，则有 \(g^{na} = 1\)，因此 \(P\mid na\)。那么满足要求的最小的 \(n=P/\gcd(a,P)\)。当且仅当 \(\gcd(a,P)=1\) 即 \(a\) 与 \(p-1\) 互质时，\(x=g^a\) 的阶等于 \(P\)，因而是原根。而模 \(p\) 意义下与 \(p-1\) 互质的数共有 \(\phi(p-1)\) 个（欧拉函数的定义），这就证明了结论。

3.11 证明模质数 \(p>3\) 的原根的乘积同余于 \(1\)。

证明 设任意原根为 \(g\)，那么 \(g^{-1}\) 也是原根。因此，可以将所有原根两两配对。但是，有必要排除 \(g\equiv g^{-1}\) 的情况。满足这个同余式的 \(g\) 只有 \(\pm 1\)。这里 \(1\) 显然不是原根；\((-1)^2\equiv 1\)，因此在 \(p>3\) 时一定不是原根。由此可知，互逆的原根总是成对出现，因此所有的原根乘积同余于 \(1\)。

3.12 如果 \(p=4k+1\) 是质数，且 \(g\) 是模 \(p\) 的原根，证明 \(p-g\) 也是模 \(p\) 的原根。

证明 根据原根定义可知 \(g^{4k}\equiv 1\pmod p\)。首先 \[(p-g)^{4k}\equiv (-1)^{4k} g^{4k} \equiv 1\pmod p\] 另一方面，\[(p-g)^{2k} \equiv g^{2k} \not\equiv 1\pmod p\] （否则 \(g\) 的阶至多是 \(2k\)，和原根定义矛盾）。由此可知 \(p-g\) 也是原根。

3.13 如果 \(p=4k-1\) 是质数，且 \(g\) 是模 \(p\) 的原根，证明 \(p-g\) 不是模 \(p\) 的原根。

证明 根据原根定义可知 \(g^{4k-2} = (g^{2k-1})^2\equiv 1\pmod p\)。解得 \(g^{2k-1}\equiv -1\pmod p\)（不可能 \(\equiv+1\)，因为 \(g\) 是原根）。于是 \[(p-g)^{2k-1} \equiv -g^{2k-1} \equiv 1\pmod p\] 由此可知 \(p-g\) 的阶是 \(2k-1 < p-1\)，因此不是原根。

3.14 如果 \(g\) 是模 \(p^2\) 的原根（\(p\) 是质数），证明它也是 \(p\) 的原根。逆命题是否成立？

证明 如果 \(g\) 是模 \(p^2\) 的原根，那么 \(g^n\) 当 \(n=1,\ldots,p^2-1\) 时（以某种顺序）分别和 \[1,2,3,\ldots,p-1,p+1,\ldots,p^2-1\] 同余\(\pmod {p^2}\)。将 \(p\) 其中前 \(p-1\) 个对 \(p\) 取模，得 \[1,2,3,\ldots,p-1\] 这说明 \(g\) 的幂可以生成 \(1,\ldots,p-1\) 中的所有数，因此是原根。

逆命题不成立。举一反例即可：当 \(p=2\) 时，\(1\) 是原根；但当 \(p=4\) 时，\(1\) 不是原根。

3.22 用高斯引理证明 \(-2\) 是形如 \(8k+1\) 和 \(8k+3\) 的质数的二次剩余，且是形如 \(8k+5\) 和 \(8k+7\) 的质数的二次非剩余。

证明 设质数 \(p=8k+r\)，其中 \(r=1,3,5,7\)。根据高斯引理，\((-2|p)=(-1)^v\)，其中 \(v\) 是下列数 \[-2,-4,-6,\ldots,-2P\qquad(P=\tfrac{p-1}{2})\] 模 \(p\) 并约简到 \(\pm\frac12p\) 之间时，负数的个数。因此只须考虑不等式 \(-\frac12p<-2x<0\) 的解的个数；该不等式等价于 \[0 < x < 2k+\frac14r\] 因为只考虑整数解个数的奇偶性，所以只须考虑不等式 \(0 < x < \frac14 r\)（整数解的个数相差 \(2k\) 是一个偶数，因此不影响奇偶性）。不难验证，

• 当 \(r=1,3\) 时，不等式无整数解；此时 \((-2|p)=1\)，即 \(-2\) 是 \(p\) 的二次剩余。
• 当 \(r=5,7\) 时，不等式恰有一个整数解 \(x=1\)；此时 \((-2|p)=-1\)，即 \(-2\) 是 \(p\) 的二次非剩余。

这就是所要证明的。

3.25 计算 Legendre 符号 \((-26|73)\), \((19|73)\) 和 \((33|73)\)。

解 使用二次互反律： \[\newcommand{\legendre}[2]{\genfrac(){}{}{#1}{#2}} \legendre p q \legendre q p = \begin{cases} +1 & \text{if }p\equiv q\equiv 3 \pmod 4 \\ -1 & \text{else}\end{cases}\] 和第二补充： \[\legendre 2p = \begin{cases}+1& \text{if }p\equiv\pm1 \pmod 8\\-1&\text{else}\end{cases}\] 计算得 \begin{align*} \legendre{-26}{73} &= \legendre{47}{73} = \legendre{73}{47} = \legendre{26}{47} \\ &= \legendre{2}{47}\legendre{13}{47} \\ &= (+1)\legendre{47}{13} = \legendre{8}{13} = \legendre{2}{13}^{\mkern-6mu3} \\ &= (-1)^3 = -1 \\[6pt] \legendre{19}{73} &= \legendre{73}{19} = \legendre{16}{19} \\ &= \legendre{2}{19}^{\mkern-6mu4} = 1\\[6pt] \legendre{33}{73} &= \legendre{3}{73}\legendre{11}{73} = \legendre{73}{3}\legendre{73}{11} \\ &= \legendre{1}{3} \legendre{7}{11} \\ &= (+1)\cdot -\legendre{11}{7} = -\legendre{4}{7} \\ &= -\legendre{2}{7}^{\mkern-6mu2} = -1 \end{align*}

3.26 下列同余方程哪些是可解的？

1. \(x^2\equiv 125\pmod{1016}\)
2. \(x^2\equiv 129\pmod{1016}\)
3. \(x^2\equiv 41\pmod{79}\)
4. \(41x^2\equiv 43\pmod{79}\)
5. \(43x^2\equiv 47\pmod{79}\)
6. \(x^2\equiv 151\pmod{840}\)

说明 这里要利用上一章的一个结论：线性同余方程 \[y\equiv c\pmod{p_1^{c_1}p_2^{c_2}\cdots p_n^{c_n}}\] 的解等同于方程组 \begin{align*} y&\equiv c \pmod{p_1^{c_1}} \\ y&\equiv c \pmod{p_2^{c_2}} \\ &\vdots\\ y&\equiv c \pmod{p_n^{c_n}} \\ \end{align*} 的解，其中 \(p_1,p_2,\ldots,p_n\) 是质数。

代入 \(y=x^2\) 可知一般的二项同余方程 \(x^2\equiv c\) 可以等价于一组模质数幂的方程组。对于后者，可以应用二次互反律来判断可解性。如果任意一个方程不可解，则原方程不可解；如果全部方程都可解，那么我们得到一组线性方程组 \begin{align*} x&\equiv r_1 \pmod{p_1^{c_1}} \\ x&\equiv r_2 \pmod{p_2^{c_2}} \\ &\vdots\\ x&\equiv r_n \pmod{p_n^{c_n}} \\ \end{align*} 根据中国剩余定理可知，这组方程有解，从而原方程有解。

答

1. 无解。因为原方程要求 \(x^2\equiv 125\pmod{127}\)，但 \(\legendre{125}{127}=-1\)。
2. 可解。因为 \(1016=2^3\cdot127\)，所以原方程同解于方程组 \begin{align*} x^2&\equiv 1 \pmod{2^3} \\ x^2&\equiv 2 \pmod{127} \end{align*} 第一个方程显然有解 \(x\equiv \pm1\)。第二个方程有解，因为 \(\legendre{2}{127}=1\)。
3. 无解。因为 \(\legendre{41}{79}=-1\)。
4. 可解。因为 \(\legendre{41}{79}=\legendre{43}{79}=-1\)，并按照“非剩余乘剩余等于非剩余；非剩余乘非剩余等于剩余”的规律可知，这里的 \(x^2\) 等于二次剩余。
5. 可解。理由同上。
6. 无解。因为原方程要求 \(x^2\equiv 7 \pmod 8\)，但 7 不是 8 的二次剩余（事实上，8 的二次剩余只有 1 和 4）。