Wilson 定理
贡献者： int256
预备知识 二次剩余，Legendre 符号（数论）
定理 1 威尔逊定理
威尔逊定理（Wilson 定理）指，对于一个素数 $p$ 有 $(p-1)! \equiv -1 \pmod p$。
证明：对于 $2$ 显然成立。否则对于奇素数 $p$，对 Legendre 符号中的定理 1 取特例，当 $a=1$ 时，则将化为 $x^2 \equiv 1 \pmod p$，有解 $x = \pm 1$，从而 $1$ 是 $p$ 的一个二次剩余而 $\left(\frac 1p\right)=1$，得证！
利用 Wilson 定理与定理 1 可以得到 Legendre 符号的计算方法。
定理 2 Legendre 符号的计算方法
\begin{equation}
\left(\frac ap\right) \equiv a^{(p-1)/2} \pmod p ~.
\end{equation}
证明：由于定理 1 ：
\begin{equation}
(p-1)! \equiv -\left(\frac ap\right) a^{(p-1)/2} \pmod p ~,
\end{equation}
对等式两边同时乘以 Legendre 符号 $\left(\frac ap\right)$，利用 $\left(\frac ap\right)^2 = 1$ 得到
\begin{equation}
(p-1)!\left(\frac ap\right) \equiv - a^{(p-1)/2} \pmod p ~,
\end{equation}
而利用 Wilson 定理，$(p-1)! \equiv -1 \pmod p$，故
\begin{equation}
-\left(\frac ap\right) \equiv - a^{(p-1)/2} \pmod p ~,
\end{equation}
也就是
\begin{equation}
\left(\frac ap\right) \equiv a^{(p-1)/2} \pmod p ~.
\end{equation}
证毕！