威尔逊定理：(p-1)! ≡ -1 (mod p)

阶乘和素数看起来不像一类东西。$(p-1)!$ 是把 $1$ 到 $p-1$ 全乘起来，素数是不能再拆的整数。威尔逊定理把它们钉在同一条同余上：$p$ 为素数，当且仅当 $(p-1)!\equiv -1\pmod p$。下面用配对逆元把这件事算清楚，再看合数如何一律失败，以及为什么它几乎不能拿来判断素数。

定理

设 $n\ge 2$ 是整数。则 $n$ 是素数，当且仅当

右边也可以写成 $n-1$，因为 $-1\equiv n-1\pmod n$。$n=2$：$$。：。后面证明奇数素数时，默认 。

「当且仅当」有两半。一半是：素数满足这条同余。另一半是：合数一律不满足。两半的理由完全不同，前一半靠模逆元配对，后一半靠合数自己的因子已经出现在阶乘里。

同余在说：$(n-1)!+1$ 能被 $n$ 整除。素数时，多出来的那一个 $1$ 刚好补成 $n$ 的倍数；合数时，阶乘往往已经被 $n$ 吃干净，再加 $1$ 反而余 $$，整除关系立刻破裂。把这句话记成

和原式完全等价，手算验整除有时比看余数更直接。

正向：素数为什么成立

关键是模 $p$ 的乘法。$p$ 为素数时，$\{1,2,\dots,p-1\}$ 里每个 $a$ 都有唯一逆元 $a^{-1}$，满足

这正是一次同余 $ax\equiv 1\pmod p$ 有解：$\gcd(a,p)=1$。把这 $p-1$ 个数按「互为逆元」配对。大多数对是两个不同的数，乘积同余 。只有等于自己逆元的数会单独留下：

$p$ 是素数，所以 $p\mid(a-1)$ 或 $p\mid(a+1)$，也就是 $a\equiv 1$ 或 。二次同余在素域上至多两个根，这里恰好两个，不会再多。

于是 $1$ 和 $p-1$ 各自成对，其余 $p-3$ 个数配成 $(p-3)/2$ 对，每对乘积 $\equiv 1$。整条阶乘变成

这就是配对逆元证明。它没有真的去乘那一长串整数，只是把「谁和谁抵消成 $1$」算清楚。

找逆元不必猜。解一次同余 $ax\equiv 1\pmod p$，用扩展欧几里得，或在 $p$ 不大时直接试乘到余 $1$。费马小定理也给一条公式：若 $p\nmid a$，则 $a^{-1}$。无论哪条路，逆元存在且唯一，配对就不会漏、不会重。

有人会问：为什么不把 $2$ 和 $p-2$ 也看成「对称」？那是加法对称，$2+(p-2)=p\equiv 0$，乘积是 $2(p-2)=2p-4\equiv -4$，一般不是 。威尔逊要的是乘法单位元，只能按逆元配对，不能按正负配对。

也可以换一种群论的说法，结论一样。$(\mathbb{Z}/p\mathbb{Z})^*$ 是 $p-1$ 阶有限交换群，其中恰好有一个 $2$ 阶元，就是 $-1$。有限交换群里全部元素的乘积等于单位元，除非恰好存在一个 $2$ 阶元，此时乘积等于那个元素。于是 。配对证明其实就是把这句话展开成中学语言。

$p=2$ 时乘法群只有 $\{1\}$，$1\equiv -1\pmod 2$，定理仍成立，只是「自逆的两个数」塌成同一个。所以小素数不必硬套「$1$ 和 $p$ 分开」的图景，先单独验证即可。

手算例子

例一：$p=5$

$4!=24$。$24=4\cdot 5+4$，所以 $24\equiv 4\equiv -1\pmod 5$。

配对：$1$ 的逆元是 $1$，$4$ 的逆元是 $4$，因为 $4\cdot 4=16\equiv 1$。$2$ 和 $$ 互逆：。于是

例二：$p=7$

$6!=720$。$720=102\cdot 7+6$，余 $6$，即 $\equiv -1$。

配对：$1\leftrightarrow 1$，$6\leftrightarrow 6$，$2\leftrightarrow 4$（$2\cdot 4=8\equiv 1$），（）。四对里三对贡献 ，剩下 。

例三：$p=13$

不必先算出 $12!$。配对如下：

• $1$ 和 $12$ 自逆
• $2\cdot 7=14\equiv 1$
• $3\cdot 9=27\equiv 1$

六对里五对贡献 $1$，剩下 $12\equiv -1$。所以 $12!\equiv -1\pmod{13}$。

若要验算：$12!=479001600$，$479001600=36846276\cdot 13+12$，余 $12$。手算时更值得做的是写出逆元表，而不是硬乘阶乘。

例四：$p=11$

$10!$ 已经是 $3628800$，直接除以 $11$ 不如配对。逆元表：

五对里四对贡献 $1$，剩下 $10\equiv -1$。所以 $10!\equiv -1\pmod{11}$。验算：$3628800=329890\cdot 11+10$。

这四个例子共用同一张草图：先标出自逆的 $1$ 和 $p-1$，再从 $2$ 往上找还没配对的数，试乘直到余 $1$。表填完，定理就已经证过这一次 $p$。

逆命题：合数为什么失败

反过来：若 $n\ge 2$ 且 $(n-1)!\equiv -1\pmod n$，则 $n$ 必为素数。只要说明每个合数都让同余式失败即可。这些合数就是逆命题的反例——不是「定理有漏洞」，而是「合数不满足前提」。

最小合数 $n=4$：$3!=6\equiv 2\pmod 4$，而 $-1\equiv 3\pmod 4$，不相等。 是唯一需要单独看的合数，因为它太小，因子会「撞车」： 在 里只出现一次， 本身还没出现，所以 ，余数不是 ，但也不是 。若有人把 也拿来试，，模 的同余没有信息——任何整数都整除差，通常不把 算进定理的陈述。

$n>4$ 的合数一定有素因子 $q\le\sqrt{n}<n-1$。分两类。

若 $n$ 不是素数的平方，则能写成 $n=ab$，其中 $1<a\le b<n$ 且 $a\neq b$。于是 和 都出现在 里，从而 ，即

而 $n>1$ 时 $0\not\equiv -1$。例如 $15$：$14!$ 含 $3$ 和 $5$，故 ，。：。：，里面有 ，至少三个 ，所以 ，仍是 。： 含 和 ；： 含 和 。只要两个真因子能拆开，阶乘里各出现一次就够。

偶合数 $n=2m$ 且 $m>2$ 时，$2$ 和 $m$ 都小于 $n$，结论同样是 $0$。不要误以为「偶数模偶数阶乘」会余 $2$ 或余 ；因子配齐之后余数就是 。

若 $n=q^2$ 是素数平方，且 $n>4$，则 $q\ge 3$，$n\ge 9$。此时 ，所以 和 都出现在 里，于是 ，同样

例如 $9$：$8!=40320=4480\cdot 9+0$，余 $0$，不是 $-1\equiv 8$。这里用到的是 $$ 和 ，不是两个不同的 —— 在 到 里只出现一次，单靠它除不尽 ，必须把 里多出来的那个 算上。： 含 和 ，故 。： 含 和 。更高次幂 （）只会含有更多的 ，余数照样是 。例如 已经算过，： 里有 ，远多于三个 。

一句话：合数 $n>4$ 总能在 $1$ 到 $n-1$ 里找到足够的因子把 $n$ 配齐，阶乘被 $n$ 整除；唯一的例外 $n=4$ 余 ，也不是 。所以合数全部是反例，威尔逊定理是充要条件。不存在「威尔逊伪素数」：没有任何合数能让 。

常见误读是把「$(n-1)!\equiv 0\pmod n$」当成合数的定义。$n=4$ 已经说明不是。正确的分界是：素数余 $-1$，合数余的不是 $-1$（大于 时通常是 ）。

再列一张对照，避免只记住公式：

用它判断素数的局限性

充要条件听起来像完美的素性测试：算 $(n-1)!\bmod n$，看是不是 $n-1$。问题在计算量，不在正确性。

朴素连乘要做 $n-2$ 次模 $n$ 乘法，复杂度 $\Theta(n)$。$n=10^6$ 还能接受，$n=10^{12}$ 就完全不能用。真正要判断的整数常常有几百位，威尔逊定理没有竞争力。试除法检查到 只需 次除法，比直接乘阶乘还快；Miller–Rabin 对 轮测试大约是 量级，处理千位整数仍轻松。威尔逊定理作为判素算法，连试除都赢不了。

可以做一个数量级对照。判断 $n=10^{12}+39$ 是否为素数，试除大约要 $10^6$ 次；威尔逊要做 $10^{12}$ 次模乘，差一百万倍。位数再涨，差距按指数拉开。定理给出的是判定准则，不是判定算法。准则可以在证明里引用，算法必须在时间预算里跑完。

阶乘本身增长极快。斯特林公式说 $n!\approx\sqrt{2\pi n}\,(n/e)^n$，未取模的 $(n-1)!$ 有 位。即使用模运算避免保存裸阶乘，循环次数仍是线性的。没有实用的亚线性算法专算 并能和常用素性测试抗衡。AKS 是确定性多项式时间，但常数大，实践中也不走威尔逊这条路。

还有数值细节。Python 整数任意精度，先算完整的 $(n-1)!$ 再取模，会在 $n$ 稍大时把时间和内存都耗在中间结果上。必须边乘边模。即便如此，$O(n)$ 次乘法仍在。$n=2,3$ 太小，不要为了「优化」写成空积或漏掉循环。并行化也救不了渐近：把乘积分段再合并，总乘法次数还是 $\Theta(n)$。

所以威尔逊定理的价值在证明和化简，不在工程筛素数。竞赛里偶尔出现「对很小的 $p$ 验证」或「把 $(p-1)!$ 写成乘积再配对消去」，那是在用同余化简表达式，不是在当 primality test。例如已知 $p$ 为素数，求 $1\cdot 2\cdots(p-2)\bmod p$，由威尔逊立刻得到它同余 ，因为 ，逆元是自己。这类化简比真去判素常见得多。

另外不要和威尔逊素数混淆。威尔逊素数是满足

的素数，目前只知道 $5$、$13$、$563$。这是把模数从 $p$ 加强到 $p^2$，和「用原定理判素」不是一件事。对应的威尔逊商

对每个素数都是整数，威尔逊素数就是 $p\mid w_p$ 的那些。原定理只保证模 $p$ 余 $-1$，模 $p^2$ 余多少是更细的算术，已知例子极少，也没有实用的判素价值。

一份可直接用的实现

下面给出边乘边模的判定，以及素数上逆元配对的展示，方便对照前面的手算。

跑出来可以对上前面的例子：素数的余数都是 $n-1$；合数 $4$ 余 $2$，其余不超过 $30$ 的合数余 $0$。pow(a, -1, p) 是 Python 3.8+ 的模逆。

写代码时注意三件事。判断时比较的是 $n-1$ 而不是 -1，因为 % n 的结果落在 $[0,n)$ 里，-1 % n 才会变成 $n-1$，直接写 == -1 恒为假。合数不要对 inverse_pairs 调用模逆，没有逆元的元素会抛异常。若只想演示定理，把上界留在几十、几百即可，不要拿它去扫大整数。想核对配对证明时，打印 inverse_pairs(p) 比打印阶乘更有用：表里应恰好出现一对自逆的 $(1,1)$ 和 $$，其余每对乘积模 都是 。

和费马小定理的边界

费马小定理：$p$ 为素数且 $p\nmid a$ 时，$a^{p-1}\equiv 1\pmod p$。威尔逊处理连续整数的乘积，费马处理同一个底的幂。两者都在刻画素数模上的乘法群 $$：费马说每个非零元的阶整除 ，威尔逊说把群里所有元素乘完，恰好得到唯一的 阶元 。

合数模上这两件事会同时垮掉。$(\mathbb{Z}/n\mathbb{Z})^*$ 一般不是「恰好一个 $2$ 阶元」；更关键的是，$(n-1)!$ 里已经含有与 $n$ 不互素的因子，阶乘直接变成 $0$，连单位群都没待在里面。费马小定理的合数反例是伪素数，可以骗过「」这种测试；威尔逊没有这种伪素数——合数骗不过 。它不是不够强，是太贵。

一次同余给出逆元，配对逆元给出威尔逊，威尔逊给出阶乘在素模上的取值。需要理解「为什么 $1$ 到 $p-1$ 乘完刚好差 $1$」时，回到这对逆元；需要判断一个大整数是不是素数时，换更快的算法。把存在性、配对和复杂度三件事分开，定理就不会被误用成筛法。它回答的是「阶乘在素模上等于什么」，不是「怎样快速认出素数」。