以下内容整理自《100个著名初等数学问题历史和解》

数论部分

1. 数论基础

同余加法、减法、乘法规则：略

同余除法规则：若 $p$ 与 $m$ 互质，则 $p a \equiv p b\;(\text{mod}\enspace m) \Rightarrow a \equiv b \;(\text{mod}\enspace m)$

2. 完全剩余系定理

如果有 $m$ 个整数的数系中任意两个数不同余，则该数系就称作一个模数 $m$ 的完全剩余系

完全剩余系定理：如果用一个与模数 $m$ 互质的数去乘完全剩余系的各数，则得到对于模数 $m$ 的又一个完全剩余系

证明：令 $p$ 是乘数，假设对于给定剩余系中两个不相等的数 $a,b$

$$pa\equiv pb\;(\text{mod}\enspace m)$$

根据同余除法规则必有 $a\equiv b\;(\text{mod}\enspace m)$，矛盾。证毕

3. 二次剩余计数定理

有两个互质的数 $a,m$，如果 $a$ 和某个平方数模 $m$ 互余，则 $a$ 叫做 $m$ 的二次剩余。如果不存在这样的平方数，则称为二次非剩余

例如 12 是 13 的二次剩余，因为 $12 \equiv 8^2\;(\text{mod}\enspace m)$；2 是 3 的二次非剩余，由于不存在 $x$，$2\equiv x^2\;(\text{mod}\enspace m)$

二次剩余计数定理：（不考虑 $m$ 的倍数）对于奇素数模数 $m$，共有 $p=\dfrac {m-1}2$ 个相互不同余的二次剩余 $1^2,2^2,3^2,...,p^2$，和 $p$ 个相互不同余的二次非剩余

证明：对于集合 $A=\{1^2,2^2,3^2,...,p^2\}$

（证明下界）假设 $x,y\in [1,p],x>y,x^2\equiv y^2\;(\text{mod}\enspace m)$

则 $x^2-y^2=(x+y)(x-y)$ 必能整除 $m$

然而 $(x+y),(x-y)$ 都小于素数 $m$，矛盾

（证明上界）任意平方数 $h^2$（不考虑 $m$ 的倍数）

必然能找到 $k\in [-p,-1]\cup[1,p],k\equiv h\;(\text{mod}\enspace m)$

也就有 $k^2\equiv h^2\;(\text{mod}\enspace m)$，而且 $k^2\in A$

（第二部分）一共 $2p$ 个相互不同余的数，除去 $A$ 的 $p$ 个剩下 $p$ 个。证毕

4. 二次剩余乘积定理

（不考虑 $m$ 的倍数）对于奇素数模数 $m$，两个二次剩余的积仍为二次剩余，一个二次剩余与一个非二次剩余的积为非二次剩余，两个非二次剩余的积为二次剩余

证明：

第一，两个二次剩余的积仍为二次剩余

$$\left\{\begin{array}{c} a\equiv A^2\;(\text{mod}\enspace m)\\ b\equiv B^2\;(\text{mod}\enspace m) \end{array}\right. \Rightarrow ab\equiv (AB)^2\;(\text{mod}\enspace m)$$

第二，一个二次剩余与一个非二次剩余 $N$ 的积为非二次剩余

对于 $2p$ 个数 $1^2,2^2,...,p^2,1^2N,2^2N,...,p^2N$，由二次剩余计数定理，前 $p$ 个数互不同余，后 $p$ 个同理，再由完全剩余系定理，它们互不同余

而且前 $p$ 个数是二次剩余，所以后 $p$ 个数是二次非剩余

第三，两个非二次剩余 $N,M$ 的积为二次剩余

对于 $2p$ 个数 $1^2N,2^2N,...,p^2N,1^2NM,2^2NM,...,p^2NM$，由二次剩余计数定理和完全剩余系定理，它们互不同余

而且前 $p$ 个数是二次非剩余，所以后 $p$ 个数是二次剩余，而 $N,M$ 的积就在其中

证毕

5. 共轭数唯一定理

双线性同余式；（$m$ 还是奇素数，还是不考虑 $m$ 的倍数）

$$xy\equiv D\;(\text{mod}\enspace m)$$

其中 $y$ 被称为 $x$ 的共轭数（或环绕数）

共轭数唯一定理：在完全剩余系中，对于每一个 $x$ 有且仅有一个共轭数 $y$

证明：对于 $x$ 的两个不同余的共轭数 $y,y',\left\{\begin{array}{c} xy\equiv D\;(\text{mod}\enspace m) \\xy'\equiv D\;(\text{mod}\enspace m) \end{array}\right.$

$\Rightarrow xy\equiv xy'\;(\text{mod}\enspace m) \Rightarrow y\equiv y'\;(\text{mod}\enspace m)$（同余除法规则）

矛盾。证毕

6. 二次剩余判定定理（欧拉定理）

前提是 $m$ 是奇素数且 $D$ 不是 $m$ 的倍数

如果 $D^p\equiv 1 \;(\text{mod}\enspace m)$，那么 $D$ 是二次剩余

如果 $D^p\equiv -1 \;(\text{mod}\enspace m)$，那么 $D$ 是二次非剩余

其中 $p=\dfrac{m-1}2$

---

引理1：如果 $D$ 是 $m$ 的二次非剩余

因为不存在 $x^2\equiv D\;(\text{mod}\enspace m)$，所以不存在 $x$ 是自身的共轭数的情况，完全剩余系中的元素两两对应，即

$$\begin{array}{c} x_1y_1\equiv D\;(\text{mod}\enspace m) \\ x_2y_2\equiv D\;(\text{mod}\enspace m) \\ \cdots\\ x_py_p\equiv D\;(\text{mod}\enspace m) \\ \end{array}$$

$p$ 个式子相乘，可以得到 $(m-1)!\equiv D^p \;(\text{mod}\enspace m)$

---

引理2：如果 $D$ 是 $m$ 的二次剩余，假设 $x_1^2 \equiv D \;(\text{mod}\enspace m)$ 成立

那么完全剩余系里一定有且仅有两个数 $x_1,x_2$ 是自身共轭数

证明：

$$x_1^2 \equiv D \;(\text{mod}\enspace m)\Rightarrow (m-x_1)^2\equiv D \;(\text{mod}\enspace m)$$

找到了第二个自身共轭数，不妨设 $x_2=m-x_1$

假设存在第三个数 $x_3$ 满足 $x_3^2\equiv D \;(\text{mod}\enspace m)$

就有 $x_1^2-x_3^2\equiv 0\;(\text{mod}\enspace m) \Rightarrow (x_1+x_3)(x_1-x_3) \equiv 0 \;(\text{mod}\enspace m)$

如果 $(x_1+x_3)$ 是 $m$ 的倍数，那么 $x_3$ 与 $x_2$ 同余

如果 $(x_1-x_3)$ 是 $m$ 的倍数，那么 $x_3$ 与 $x_1$ 同余，证毕

易得 $-x_1x_2=-mx_1+x_1^2\equiv D \;(\text{mod}\enspace m)$

而其他 $(2p-2)$ 个数两两共轭，于是就有

$$\begin{array}{c} -x_1x_2\equiv D \;(\text{mod}\enspace m) \\ x_3y_3\equiv D \;(\text{mod}\enspace m) \\ x_4y_4\equiv D \;(\text{mod}\enspace m) \\ \cdots\\ x_{p+1}y_{p+1}\equiv D \;(\text{mod}\enspace m) \\ \end{array}$$

$p$ 个式子相乘可得 $(m-1)!\equiv -D^p \;(\text{mod}\enspace m)$

---

把 $D=1$ 代入引理2，就变成威尔逊定理 $(m-1)!\equiv -1 \;(\text{mod}\enspace m)$

将威尔逊定理代回引理1 和引理2 即可。证毕

---

如果要判断 $-1$ 是否为二次剩余，代 $-1$ 入二次剩余判定定理得 $(-1)^{\frac{m-1}2}$

而其值是否为 1 取决于 $m$ 是否为 $(4n+1)$ 型素数

因此就有欧拉定理（又是你？）：

当奇素数 $m$ 为 $4n+1$ 时，-1 为二次剩余；反之则为二次非剩余