Wilson 定理

贡献者： int256

预备知识　二次剩余，Legendre 符号（数论）

定理 1　威尔逊定理

　　 威尔逊定理（Wilson 定理）指，对于一个素数 $p$ 有 $(p - 1)! \equiv - 1 (\mod p)$ 。

　　证明：对于 $2$ 显然成立。否则对于奇素数 $p$ ，对 Legendre 符号中的定理 1 取特例，当 $a = 1$ 时，则将化为 $x^{2} \equiv 1 (\mod p)$ ，有解 $x = \pm 1$ ，从而 $1$ 是 $p$ 的一个二次剩余而 $(\frac{1}{p}) = 1$ ，得证！

　　利用 Wilson 定理与定理 1 可以得到 Legendre 符号的计算方法。

定理 2　Legendre 符号的计算方法

\begin{matrix} (1) & (\frac{a}{p}) \equiv a^{(p - 1) / 2} (\mod p) . \end{matrix}

　　证明：由于定理 1 ：

\begin{matrix} (2) & (p - 1)! \equiv - (\frac{a}{p}) a^{(p - 1) / 2} (\mod p), \end{matrix}

对等式两边同时乘以 Legendre 符号

(\frac{a}{p})

，利用

{(\frac{a}{p})}^{2} = 1

得到

\begin{matrix} (3) & (p - 1)! (\frac{a}{p}) \equiv - a^{(p - 1) / 2} (\mod p), \end{matrix}

而利用 Wilson 定理，

(p - 1)! \equiv - 1 (\mod p)

，故

\begin{matrix} (4) & - (\frac{a}{p}) \equiv - a^{(p - 1) / 2} (\mod p), \end{matrix}

也就是

\begin{matrix} (5) & (\frac{a}{p}) \equiv a^{(p - 1) / 2} (\mod p) . \end{matrix}

证毕！

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。

Wilson 定理

定理 1 威尔逊定理

定理 2 Legendre 符号的计算方法

定理 1　威尔逊定理

定理 2　Legendre 符号的计算方法