高等算术习题(3) -- 二次剩余

高等算术习题(3) – 二次剩余

Fri Mar 4, 2022

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

---

3.6 证明 2k 当 k>2 时没有原根。

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

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

下面证明任意奇数的阶都小于 2k−1。事实上，当 k>2 时，对任意奇数 x 都有 x2k−2≡1(mod2k)。

当 n=23=8 时，不难验证 12≡1,32≡1,52≡1,72≡1(mod8) 假设 x2k−2≡1(mod2k)，那么 x2k−2−1=t2k，其中 t 是整数。于是 x2k−1−1=(x2k−2)2−1=(x2k−2+1)(x2k−2−1)=(t2k−1+1)t2k+1 这表明 x2k−1−1≡0(mod2k+1)，即 x2k−1≡1(mod2k+1)。根据数学归纳法，可知 x2k−2≡1(mod2k) 对任意 k=3,4,5,… 都成立。这表明任意奇数的阶至多是 2k−2，因此不可能是原根。

综上所述，2k 没有原根。

---

3.10 证明模质数 p 的原根总是恰有 ϕ(p−1) 个。

证明 本章已经证明了模 p 运算总是存在原根。设原根是 g。那么，gn≡1(modp)⇒P∣n，其中 P=p−1。

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

---

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

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

---

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

证明 根据原根定义可知 g4k≡1(modp)。首先 (p−g)4k≡(−1)4kg4k≡1(modp) 另一方面，(p−g)2k≡g2k≢1(modp) （否则 g 的阶至多是 2k，和原根定义矛盾）。由此可知 p−g 也是原根。

---

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

证明 根据原根定义可知 g4k−2=(g2k−1)2≡1(modp)。解得 g2k−1≡−1(modp)（不可能 ≡+1，因为 g 是原根）。于是 (p−g)2k−1≡−g2k−1≡1(modp) 由此可知 p−g 的阶是 2k−1<p−1，因此不是原根。

---

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

证明 如果 g 是模 p2 的原根，那么 gn 当 n=1,…,p2−1 时（以某种顺序）分别和 1,2,3,…,p−1,p+1,…,p2−1 同余(modp2)。将 p 其中前 p−1 个对 p 取模，得 1,2,3,…,p−1 这说明 g 的幂可以生成 1,…,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,…,−2P(P=p−12) 模 p 并约简到 ±12p 之间时，负数的个数。因此只须考虑不等式 −12p<−2x<0 的解的个数；该不等式等价于 0<x<2k+14r 因为只考虑整数解个数的奇偶性，所以只须考虑不等式 0<x<14r（整数解的个数相差 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)。

解 使用二次互反律： (pq)(qp)={+1if p≡q≡3(mod4)−1else 和第二补充： (2p)={+1if p≡±1(mod8)−1else 计算得 (−2673)=(4773)=(7347)=(2647)=(247)(1347)=(+1)(4713)=(813)=(213)3=(−1)3=−1(1973)=(7319)=(1619)=(219)4=1(3373)=(373)(1173)=(733)(7311)=(13)(711)=(+1)⋅−(117)=−(47)=−(27)2=−1

---

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

1. x2≡125(mod1016)
2. x2≡129(mod1016)
3. x2≡41(mod79)
4. 41x2≡43(mod79)
5. 43x2≡47(mod79)
6. x2≡151(mod840)

说明 这里要利用上一章的一个结论：线性同余方程 y≡c(modp1c1p2c2⋯pncn) 的解等同于方程组 y≡c(modp1c1)y≡c(modp2c2)⋮y≡c(modpncn) 的解，其中 p1,p2,…,pn 是质数。

代入 y=x2 可知一般的二项同余方程 x2≡c 可以等价于一组模质数幂的方程组。对于后者，可以应用二次互反律来判断可解性。如果任意一个方程不可解，则原方程不可解；如果全部方程都可解，那么我们得到一组线性方程组 x≡r1(modp1c1)x≡r2(modp2c2)⋮x≡rn(modpncn) 根据中国剩余定理可知，这组方程有解，从而原方程有解。

答

1. 无解。因为原方程要求 x2≡125(mod127)，但 (125127)=−1。
2. 可解。因为 1016=23⋅127，所以原方程同解于方程组 x2≡1(mod23)x2≡2(mod127) 第一个方程显然有解 x≡±1。第二个方程有解，因为 (2127)=1。
3. 无解。因为 (4179)=−1。
4. 可解。因为 (4179)=(4379)=−1，并按照“非剩余乘剩余等于非剩余；非剩余乘非剩余等于剩余”的规律可知，这里的 x2 等于二次剩余。
5. 可解。理由同上。
6. 无解。因为原方程要求 x2≡7(mod8)，但 7 不是 8 的二次剩余（事实上，8 的二次剩余只有 1 和 4）。

---