贡献者： int256
1. 定义
定义 1 Legendre 符号
对于一个奇素数 $p$ 与一个不被 $p$ 整除的数 $a$，定义 勒让德符号（Legendre 符号） $\left( \frac{a}{p} \right)$ 是：
- 若 $a \operatorname R p$ 则 $\left( \frac{a}{p} \right) = +1$；
- 若 $a \operatorname N p$ 则 $\left( \frac{a}{p} \right) = -1$。
推论 1
由定义，立刻有
\begin{equation}
\left(\frac ap\right) ^2 = 1 ~.
\end{equation}
推论 2
若 $a \equiv b \pmod p$，而 $a$ 为不被奇素数 $p$ 整除的数，则
\begin{equation}
\left(\frac ap \right) = \left(\frac bp \right) ~.
\end{equation}
当 $p=2$ 时，不考虑其 Legendre 符号。
2. 应用
定理 1
对于奇素数 $p$，若 $a$ 不是 $p$ 的倍数，则
\begin{equation}
(p-1)! \equiv -\left(\frac ap\right) a^{(p-1)/2} \pmod p ~.
\end{equation}
证明：若 $a \operatorname R p$ 且有 $x_1^2 \equiv a \pmod p$，则显然
\begin{equation}
x_2 = p-x_1 \equiv -x_1 \pmod p ~~
\end{equation}
也是 $x^2 \equiv a \pmod p$ 的解，此外若还有其他解 $x'^2 \equiv a \pmod p$，则
\begin{equation}
x^2 \equiv a \pmod p, x'^2 \equiv a \pmod p ~,
\end{equation}
这就指出，
\begin{equation}
x^2 - x'^2 = (x+x')(x-x') \equiv a - a = 0 \pmod p ~,
\end{equation}
从而 $(x+x') \equiv 0 \pmod p$ 或 $(x-x') \equiv 0 \pmod p$，这就指出了仅有 $x_1$ 与 $p-x_1$ 两个代表对应的模 $p$ 的剩余类是解。这就指出，仅有 $x_1$ 与 $p-x_1$ 的伴随数是自己。
此时可以立刻得出，各数 $1, 2, \dots, (p-1)$ 可以分成 $x_1, p-x_1$ 以及 $(p-3)/2$ 对不相等的伴随数对1，其中
\begin{equation}
x_1(p-x_1) \equiv -x_1^2 \equiv -a \pmod p ~,
\end{equation}
而对任意一对伴随数 $x, x'$ 都有 $xx' \equiv a \pmod p$，故
\begin{equation}
(p-1)! = \prod x \equiv -a \cdot a^{(p-3)/2} \equiv -a ^{(p-1)/2} \pmod p ~.
\end{equation}
可以发现当 $a \operatorname R p$ 时，原定理成立。
若 $a \operatorname N p$，则 $x^2 \equiv a \pmod p$ 无解，故各数 $1, 2, \dots, (p-1)$ 可以分成 $(p-1)/2$ 对不相等的伴随数对2，从而
\begin{equation}
(p-1)! = \prod x \equiv a^{(p-1)/2} \pmod p ~.
\end{equation}
故当 $a \operatorname N p$ 时，原定理也成立。证毕！
1. ^ 可以证明这些数一定可以配对，可以利用费马小定理或定理 2 证明总可以构造，而由于 $1$ 至 $p-1$ 都与 $p$ 互素，故必定不重复。
2. ^ 一样的，可以证明一定可以两两配对。