3.2

解答题

1

直接通过 sage 计算：

1
2
#!/usr/bin/env sage
print(kronecker(2, 29)) # -1

另外，可以具体过程为：

对于勒让德符号 $$\displaystyle (\frac{a}{p}) = (\frac{2}{29})$$，根据欧拉判别条件 $$\displaystyle (\frac{2}{29}) = 2^{\frac{28}{2}} \equiv 32^2 * 16 \equiv 9 * 16 \equiv 144 \equiv -1 \pmod{29}$$

或者 $$p \equiv -3 \pmod{8}$$，因此 $$\displaystyle (\frac{2}{29}) = -1$$

所以 2 不为 29 的二次剩余。

2

-1 是模 p 的二次剩余 $$\displaystyle \Leftrightarrow (\frac{-1}{p}) = 1$$

对于左侧勒让德符号 $$\displaystyle (\frac{-1}{p}) = (-1)^{\frac{p-1}{2}} = \begin{cases} 1 & \text{若 } p \equiv 1 \pmod{4} \ -1 & \text{若 } p \equiv 3\pmod{4}\end{cases}$$

所以 -1 是模 p 的二次剩余的一个充要条件是 $$p \equiv 1 \pmod{4}$$

3

1
2
#!/usr/bin/env sage
print(kronecker(191, 397)) # 1

这说明 191 对 397 的勒让德符号为 1，说明 191 是 397 的二次剩余。即方程有解。

1
2
3
#!/usr/bin/env sage
solve_mod(x**2 == 191, 397)
# [(117,), (280,)]

另外，手算可以使用二次互反律：

首先：

1
2
#!/usr/bin/env sage
is_prime(191), is_prime(397) # True, True

$$\displaystyle (\frac{191}{397})(\frac{397}{191}) = (-1)^{95 * 198} = 1 \Leftrightarrow (\frac{191}{397}) = 1*(\frac{15}{191})$$

对于 15 对模 191 的勒让德符号：$$\displaystyle (\frac{15}{191}) = (\frac{3}{191})(\frac{5}{191}) = (-1)^{195}(\frac{191}{3})(-1)^{295}(\frac{191}{5}) = -1*(\frac{2}{3})* 1 *(\frac{1}{5})$$

而我们有 $$\displaystyle (\frac{2}{3}) = 2^{\frac{3-1}{2}} = -1, (\frac{1}{5}) = 1$$

因而对于原式：$$\displaystyle (\frac{191}{397}) = 1*(-1)1(-1)*1 = 1$$

4

1
2
#!/usr/bin/env sage
print(kronecker(11, 511)) # -1

这说明 11 对 511 的雅可比符号为 -1，说明 11 是 511 的二次非剩余。即方程无解。

另外，也可以使用二次互反律：

首先：

1
2
3
#!/usr/bin/env sage
factor(511)
# 7 * 73

$$\displaystyle (\frac{11}{511}) = (\frac{11}{7})(\frac{11}{73})$$

对于前者 $$\displaystyle (\frac{3}{7}) =3^{\frac{7 - 1}{2}} \equiv 3^3 \equiv -1 \pmod{7}$$

对于后者 $$\displaystyle (\frac{11}{73}) = (-1)^{\frac{11 - 1}{2} \frac{73-1}{2}} (\frac{73}{11}) = (\frac{-2}{11}) = (-2)^{5} = -32 \equiv 1 \pmod{11}$$

所以综上，$$\displaystyle (\frac{11}{511}) = -1$$，因此 11 是 511 的二次非剩余。方程无解。

5

1
2
#!/usr/bin/env sage
print(kronecker(2, 73)) # 1

这说明 2 对 73 的勒让德符号为 1，说明 2 是 73 的二次剩余。即方程有解。

1
2
3
#!/usr/bin/env sage
solve_mod(x**2 == 2, 73)
# [(32,), (41,)]

另外，对于笔算方法。首先：

1
2
3
#!/usr/bin/env sage
print(is_prime(73)) # True
print(73 % 8)  # 1

$$\displaystyle 73 \equiv 1 \pmod{8} \Rightarrow (\frac{2}{73}) = 1$$

6

即方程 $$n^2 \equiv 3 \pmod{313}$$ 是否有解，这等价于求 3 是否为模 313 的二次剩余。

1
2
#!/usr/bin/env sage
kronecker(3, 313) # 1

这表示 3 确实为 313 的二次剩余。

另外也可以：$$\displaystyle (\frac{3}{313}) = (-1)^{1*156} (\frac{313}{3}) = (\frac{1}{3}) = 1$$

7

（1）$$\displaystyle (\frac{17}{37}) = (-1)^{818}(\frac{3}{17}) =(-1)^{18} \frac{2}{3} = -1$$

（2）$$\displaystyle (\frac{151}{373}) = (-1)^{75186}(\frac{71}{151}) = (-1)^{3575} (\frac{9}{71}) = -(\frac{3^2}{71}) = -1$$

（3）$$\displaystyle (\frac{191}{397}) = (-1)^{95198} (\frac{15}{191}) = (\frac{3}{191})(\frac{5}{191}) = (-1)^{195}(\frac{2}{3})(-1)^{2*95}(\frac{1}{5}) = 1$$

（4）$$\displaystyle (\frac{911}{2003}) = (-1)^{4551001} (\frac{181}{911}) = -(-1)^{90455}(\frac{6}{181}) = -(\frac{2}{181})(-1)^{1*90}(\frac{1}{3})$$

注意到 $$181 \equiv -3 \pmod{8}$$，因此 $$\displaystyle (\frac{911}{2003}) = 1$$

（5）首先：

1
2
#!/usr/bin/env sage
is_prime(37), is_prime(20040803) # (True, True)

$$\displaystyle (\frac{37}{20040803}) = (-1)^{18k} (\frac{12}{37}) = (\frac{3}{37})(\frac{2^2}{37}) = (-1)^{118} (\frac{1}{3}) = 1$$

8

设 x 以 5 为二次剩余，亦即 $$\displaystyle (\frac{5}{x}) = 1$$

$$\displaystyle (\frac{5}{x}) = (-1)^{2*k} (\frac{x}{5}) = (\frac{x}{5})$$

穷举 0 到 4 即可以得到解：$$x \in {k \equiv 1, 2, 4 \pmod{5}, k \in \mathbb{Z}}$$

9

1
2
3
#!/usr/bin/env sage
x, y = var('x'), var('y')
len(solve_mod([x**3 - 3*x + 10 == y**2], 23)) # 17

不会不解方程的做法。

10

（1）$$\displaystyle (\frac{51}{71}) = (\frac{3}{71}) (\frac{17}{71}) = (-1)^{135} (\frac{2}{3}) * (-1)^{835} (\frac{3}{17}) = (-1)^{1*8} (\frac{2}{3}) = -1$$

（2）$$\displaystyle (\frac{35}{97}) = (\frac{5}{97})(\frac{7}{97}) = (-1)^{248} (\frac{2}{5})(-1)^{3*48}(\frac{6}{7}) = (-1) * (-1) = 1$$

（3）$$\displaystyle (\frac{313}{401}) = (-1)^{156 * 200} (\frac{88}{313}) = (\frac{11}{313}) (\frac{2}{313}) (\frac{2^2}{313}) = (-1)^{5*156} (\frac{5}{11}) = (\frac{1}{5}) = 1$$

（4）$$\displaystyle (\frac{165}{503}) = (\frac{3}{503}) (\frac{5}{503}) (\frac{11}{503}) = (-1)^{1251} (\frac{2}{3}) * (-1)^{2251}(\frac{3}{5}) * (-1)^{3*251} (\frac{8}{11})$$

$$\displaystyle = 1 * (-1) * (-1) (\frac{2^2}{11})(\frac{2}{11}) = -1$$

证明题

1

充分性：

若 $$x^2 \equiv 3 \pmod{p}$$ 有解，即 3 为模 p 的二次剩余，即 $$\displaystyle (\frac{3}{p}) = 1$$

$$\displaystyle (\frac{3}{p}) = 1 \Leftrightarrow (-1)^{1 * \frac{p - 1}{2}} (\frac{p}{3}) = 1 \Leftrightarrow$$

$$\displaystyle \big(p \equiv 1 \pmod{4} 且 p \equiv 1 \pmod{3}\big) 或 \big(p \equiv 3 \pmod{4} 且 p \equiv 2 \pmod{3}\big)$$

应用中国剩余定理：$$\Leftrightarrow p \equiv 1 \pmod{12} 或 p \equiv 11 \pmod{12}$$

$$\Leftrightarrow p \equiv \pm 1 \pmod{12}$$

必要性：

因为在进行充分性推导时的每一步都是等价的，因此也是必要条件。

2

5 是模 p 的二次剩余 $$\displaystyle \Leftrightarrow (\frac{5}{p}) = 1 \Leftrightarrow (\frac{p}{5}) = 1 \Leftrightarrow \exist x, x^2 \equiv p \pmod{5}$$

因为我们有 $$p \equiv 1 \pmod{5}$$，显然存在 x=1，使得上式成立，因此得证。

3

考虑分解勒让德符号：

$$\displaystyle (\frac{b}{p}) + (\frac{2b}{p}) + \cdots + (\frac{(p-1)b}{p}) = (\frac{b}{p}) \sum_{i = 1}^{p - 1} (\frac{i}{p})$$

对于后面的加和，因为

设 p 是奇素数，则模 p 的缩系中二次剩余与非二次剩余的个数各为 $$\displaystyle \frac{p - 1}{2}$$，且 $$\displaystyle \frac{p - 1}{2}$$ 个二次剩余分别与序列 $$\displaystyle 1^2, 2^2, \cdots, (\frac{p - 1}{2})^2$$ 中的一个数同余，且仅与一个数同余。

所以 $$\displaystyle \sum_{i = 1}^{p-1} (\frac{i}{p}) = 0$$，所以初式为 0。

4

$$\displaystyle (\frac{-3}{p}) = (\frac{-1}{p})(\frac{3}{p}) = (-1)^{\frac{p - 1}{2}}(-1)^{1*\frac{p-1}{2}} (\frac{p}{3}) = \frac{p}{3} =\begin{cases} 1 & p \equiv 1 \pmod{3} \ -1 & p \equiv 2 \pmod{3}\end{cases}$$

考虑到 p 是奇数，即 $$p \equiv 1 \pmod{2}$$

所以根据中国剩余定理：$$\displaystyle (\frac{-3}{p}) = \begin{cases} 1 & p \equiv 1 \pmod{6} \ -1 & p \equiv -1 \pmod{6}\end{cases}$$

5

我们知道以下的结论：

我们知道 1,4 必然是 p 的二次剩余；
其次我们知道 $$\displaystyle (\frac{6}{p}) = (\frac{2}{p})(\frac{3}{p})$$，则 6,2,3 三个数中必然有一个是二次剩余；

则以下三对必然有一个均为二次剩余：

1 与 3，2 与 4，4 与 6