1

设整数 $\alpha \geqslant 1, p$ 是奇素数，若 $p^\alpha \nmid a$ ，求

$$x^2 \equiv a\left(\bmod p^\alpha\right)$$

的一切解．

解：

(1) 若 $\left(\frac{a}{p}\right) = -1$，则 $x^2 \equiv a \pmod{p}$ 无解，故 $x^2 \equiv a \pmod{p^\alpha}$ 无解。

(2) 若 $\left(\frac{a}{p}\right) = 1$，则 $x^2 \equiv a \pmod{p}$ 有解，由 Hensel 引理知 $x^2 \equiv a \pmod{p^\alpha}$ 恰有两解且在模 $p^\alpha$ 意义下互为相反数。

(3) 若 $\left(\frac{a}{p}\right) = 0$，设 $a = p^k b$，其中 $1 \leq k < \alpha$ 且 $p \nmid b$

1. 若 $2 \nmid k$，则方程无解。

2. 若 $2 \mid k$，设 $k = 2m$，令 $x = p^m y$，则

$$\begin{align} x^2 &\equiv a \pmod{p^\alpha}\\ &\Longleftrightarrow p^{2m} y^2 \equiv p^{2m} b \pmod{p^\alpha}\\ &\Longleftrightarrow y^2 \equiv b \pmod{p^{\alpha-2m}} \end{align}$$

同上，若 $\left(\frac{b}{p}\right) = 1$，则恰有两解，设 $y_0^2 \equiv b \pmod{p^{\alpha-2m}}$，

则 $x_1 \equiv p^m y_0 \pmod{p^\alpha}$，$x_2 \equiv p^m(p^{\alpha-2m} - y_0) \pmod{p^\alpha}$。

若 $\left(\frac{b}{p}\right) = -1$，则方程无解。

3

分别写出 $7,13,29,37$ 的全体二次剩余和非剩余．

解：

素数	二次剩余	二次非剩余
7	1, 2, 4	3, 5, 6
13	1, 3, 4, 9, 10, 12	2, 5, 6, 7, 8, 11
29	1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28	2, 3, 8, 10, 11, 12, 14, 15, 17, 18, 19, 21, 26, 27
37	1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36	2, 5, 6, 8, 13, 14, 15, 17, 18, 19, 20, 22, 23, 24, 29, 31, 32, 35

4

设 $p>2$ 为奇素数，证明： (1) $\left(\frac{-1}{p}\right)=1$ 的充要条件是 $p=4 n+1$ ； (2) $\left(\frac{2}{p}\right)=1$ 的充要条件是 $p=8 n \pm 1$ ； (3) $\left(\frac{-2}{p}\right)=1$ 的充要条件是 $p=8 n+1,8 n+3$ ；并由此进一步证明对任意素数 $p,-1,-2,2$ 中必有一个是 $p$ 的平方剩余．

证明：

(1) $\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = 1 \Leftrightarrow p = 4n+1$

(2) $\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} = 1 \Leftrightarrow p = 8n \pm 1$

(3) $\left(\frac{-2}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{2}{p}\right) = (-1)^{\frac{(p-1)(p+5)}{8}}$

$\left(\frac{-2}{p}\right) = 1 \Leftrightarrow p = 8n+1, 8n+3$

因此，对于任意奇素数 $p$, $-1, -2, 2$ 中必有一个是 $p$ 的二次剩余。

7

设 $x, y$ 为整数，$(x, y)=1$ ，问：$x^2+y^2$ 的大于 2 的素因子一定具有什么形式？$x^2+2 y^2$ 的大于 2 的素因子一定具有什么形式？

解：

(1)

$$\begin{align} & x^2 \equiv -y^2 \pmod{p}\\ &\Leftrightarrow \left(\frac{-1}{p}\right) = 1\\ &\Leftrightarrow p = 4n+1 \end{align}$$

(2)

$$\begin{align} & x^2 \equiv -2y^2 \pmod{p}\\ &\Leftrightarrow \left(\frac{-2}{p}\right) = 1\\ &\Leftrightarrow p = 8n+1, 8n+3 \end{align}$$

5

利用上题证明：对任意素数 $p$，必有整数 $x$，使

$$p \mid x^8-16$$

证明： 若 $\left(\frac{2}{p}\right)=1$ 或 $\left(\frac{-2}{p}\right)=1$，则有

$$x^2 \equiv 2 \pmod p \text{ 或 } x^2 \equiv -2 \pmod p$$

故

$$x^8 \equiv 16 \pmod p$$

若 $\left(\frac{-1}{p}\right)=1$，则有

$$t^2 \equiv -1 \pmod p$$

设 $x=1+t$，有

$$\begin{align} x^2 &= t^2+2t+1 \equiv 2t \pmod p\\ x^4 &\equiv -4 \pmod p\\ x^8 &\equiv 16 \pmod p \end{align}$$

6

证明：同余式 $x^2+1 \equiv 0(\bmod p), p=4 m+1$ 的解是

$$x \equiv(2 m)!(\bmod p) .$$

证明： 由 Wilson 定理，知

$$(p-1)! \equiv -1 \pmod p$$

即

$$\begin{align} [(2m)!]^2 &= 1\times2\times\cdots\times2m\times(-2m)\times\cdots\times(-1)\\ &= 1\times2\times\cdots\times2m\times(2m+1)\times\cdots\times(4m)\\ &= (4m)!\\ &\equiv -1 \pmod p \end{align}$$

8

计算：$\left(\frac{-23}{83}\right),\left(\frac{51}{71}\right),\left(\frac{71}{73}\right),\left(\frac{-35}{97}\right)$

解：

$$\begin{align*} \left(\frac{-23}{83}\right) &= \left(\frac{-1}{83}\right) \cdot \left(\frac{23}{83}\right)\\ &= (-1)^{\frac{83-1}{2}} \cdot (-1) \cdot \left(\frac{83}{23}\right)\\ &= \left(\frac{83}{23}\right)\\ &= \left(\frac{-9}{23}\right)\\ &= \left(\frac{-1}{23}\right) \cdot \left(\frac{9}{23}\right)\\ &= (-1)^{\frac{23-1}{2}} \cdot (-1) \cdot \left(\frac{23}{9}\right)\\ &= -1 \cdot 1 \end{align*}$$

因此 $\left(\frac{-23}{83}\right) = -1$

$$\begin{align*} \left(\frac{51}{71}\right) &= \left(\frac{3}{71}\right) \cdot \left(\frac{17}{71}\right)\\ &= (-1) \cdot \left(\frac{71}{3}\right) \cdot \left(\frac{71}{17}\right)\\ &= (-1) \cdot \left(\frac{2}{3}\right) \cdot \left(\frac{3}{17}\right)\\ &= (-1) \cdot (-1)^{\frac{9-1}{8}} \cdot \left(\frac{17}{3}\right)\\ &= (-1) \cdot \left(\frac{2}{3}\right)\\ &= -1 \end{align*}$$

$$\begin{align*} \left(\frac{71}{73}\right) &= \left(\frac{73}{71}\right)\\ &= \left(\frac{2}{71}\right)\\ &= (-1)^{\frac{71^2-1}{8}}\\ &= 1 \end{align*}$$

$$\begin{align*} \left(\frac{-35}{97}\right) &= \left(\frac{-1}{97}\right) \cdot \left(\frac{35}{97}\right)\\ &= \left(\frac{-1}{97}\right) \cdot \left(\frac{97}{35}\right)\\ &= (-1)^{\frac{97-1}{2}} \cdot (\frac{-1}{35}) \cdot (\frac{2}{35}) \cdot (\frac{4}{35})\\ &= (-1)^{\frac{35-1}{2}} \cdot (-1)^{\frac{35^2-1}{8}} \cdot 1 \\ &= (-1) \cdot (-1) \cdot 1\\ &= 1 \end{align*}$$

9

设 $p>3$ 为素数，证明：

1. $\left(\frac{3}{p}\right)=1$ 之充要条件为 $p=12 n \pm 1$；
2. $\left(\frac{-3}{p}\right)=1$ 之充要条件为 $p=6 n+1$。

证明：

1. $$\left(\frac{3}{p}\right) \left(\frac{p}{3}\right) = (-1)^{\frac{p-1}{2} \frac{3-1}{2}} = (-1)^{\frac{p-1}{2}}$$

于是

$$\left(\frac{3}{p}\right) = (-1)^{\frac{p-1}{2}} \left(\frac{p}{3}\right)$$

其中

$$\begin{align} \left(\frac{p}{3}\right)=1 &\iff p \equiv 1 \pmod 3 \\ \left(\frac{p}{3}\right)=-1 &\iff p \equiv 2 \pmod 3 \end{align}$$

故

$$\begin{align} &\left(\frac{3}{p}\right)=1 \\ &\iff p \equiv 3 \pmod 4 \land p \equiv 2 \pmod 3 \\ &\text{或 } p \equiv 1 \pmod 4 \land p \equiv 1 \pmod 3 \\ &\iff p \equiv \pm 1 \pmod{12} \\ &\iff p = 12n \pm 1 \end{align}$$

$$\begin{align*} \left(\frac{-3}{p}\right) &= \left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)\\ &= (-1)^{\frac{p-1}{2}} \cdot (-1)^{\frac{p-1}{2}}\left(\frac{p}{3}\right)\\ &= (-1)^{p-1} \left(\frac{p}{3}\right) \end{align*}$$

于是

$$\begin{align} \left(\frac{-3}{p}\right) = 1 &\Leftrightarrow p \equiv 1 \pmod{2} \land p \equiv 1 \pmod{3} \\ &\lor p \equiv 0 \pmod{2} \land p \equiv 2 \pmod{3} \\ &\Leftrightarrow p \equiv 1 \pmod{6} \\ &\Leftrightarrow p = 6n+1. \end{align}$$

12

设 $p>2$ 为素数，$(a, p)=1$，则

$$\sum_{x=1}^p\left(\frac{a x+b}{p}\right)=0 .$$

证明：

$$\sum_{x=1}^p\left(\frac{ax+b}{p}\right) = \sum_{y=1}^p\left(\frac{y}{p}\right) = \frac{p-1}{2} - \frac{p-1}{2} + 0 = 0$$

参考

• https://zhuanlan.zhihu.com/p/543010816

• https://zhuanlan.zhihu.com/p/544792225

• https://zhuanlan.zhihu.com/p/545595129

• https://zhuanlan.zhihu.com/p/546385318

• https://zhuanlan.zhihu.com/p/547333984

• https://zhuanlan.zhihu.com/p/548061254

贡献者: Ming Wei

上一页潘承洞《数论基础》选解：第二章

下一页漫画资源导航