很多人第一次看到威尔逊定理反应都是这也太巧了——一个从 1 连乘到 p-1 的阶乘取模之后居然固定落在 p-1 上而且反过来还成立。我第一次在习题里遇到它时第一感觉是这不就是个数值巧合吗等把证明的两个方向都啃下来才明白它的分量它是极少数能把是不是素数这件事用一个纯乘法的等式完全刻画出来的结论。也就是说(p-1)! ≡ -1 (mod p) 与p 是素数之间是充要关系不是必要条件也不是充分条件是等价。这篇文章我打算把自己当年学这条定理的完整路径重走一遍先把定理表述抠清楚然后把证明要用到的三个模运算事实打牢接着分别证充分性和必要性逆命题那一半其实更多人会卡住最后落到手算校验和代码验证再往外延伸到几个更有意思的方向。适合正在学初等数论、准备算法竞赛、或者单纯对素数判定这个话题好奇的人看。基础要求不高会做模运算、知道什么是逆元就行如果你已经学过一遍可以直接跳到第 4 节和第 5 节那两部分的细节比教材上讲得细。1. 定理的准确表述与它为什么值得单独拎出来1.1 一句话版本和它的两个方向定理的完整说法是这样的设 n 是大于 1 的整数则 n 是素数当且仅当(n-1)! ≡ -1 (mod n)。拆成两个方向看第一个方向是素数必满足即 p 为素数时 (p-1)! ≡ -1 (mod p)第二个方向是满足必是素数即若 (n-1)! ≡ -1 (mod n) 且 n 1则 n 一定是素数。两个方向合起来才构成当且仅当。很多人背公式的时候会把它写成 (p-1)! ≡ p-1 (mod p)这两种写法完全等价因为 -1 在模 p 意义下就是 p-1。写代码的时候用p-1更顺手写数学证明的时候用-1更顺手因为 -1 在乘法里的行为更干净乘以 -1 就是取相反数符号好追踪。还有一个等价的除法写法p | (p-1)! 1。这个形式在做整除性论证时特别方便因为它把同余直接翻译成整除可以用上整除的所有性质。我在推逆命题的时候就更喜欢用这个形式后面会看到。注意定理里n 1这个条件不能省。n 1 的时候 (n-1)! 0! 1而模 1 的同余在形式上是平凡的任何数都 ≡ 0 mod 1讨论它没有意义。有些教材直接默认 n ≥ 2写题解的时候要自己补上这个判断否则代码在 n 1 处会给出错误答案。之所以说这个定理值得单独拎出来是因为它给出了素数的一个纯算术刻画不需要引入任何分析工具、不需要概率、不需要辅助算法只要把 1 到 n-1 全部乘起来再加一看能不能被 n 整除就能百分百断定 n 的素性。这种完美但极慢的判据在理论上非常干净是很多数论结论的落脚点。1.2 它比a^{p-1} ≡ 1强在哪学过一点数论的读者肯定见过另一个经典结论p 是素数、a 与 p 互素时a^{p-1} ≡ 1 (mod p)。这个结论只提供了单向信息——素数一定满足但满足的不一定是素数。事实上存在一类特殊的合数对所有与它互素的 a 都满足 a^{n-1} ≡ 1 (mod n)这类数在密码学里是必须专门排查的假阳性。威尔逊定理的强度就在于它把假阳性彻底堵死了。一个合数无论长什么样都不可能让 (n-1)! ≡ -1 (mod n) 成立唯一的例外是 n 4后面细讲。所以它是一个无误差的判据只是代价太高。这里还有个更细的对比维度那个指数型的结论可以推广到a^{n-1} ≡ 1 对多少个 a 成立这种概率化的判据从而衍生出现代素性检测算法而威尔逊定理的等式只有一条没有中间地带要么成立要么不成立所以它没法做概率化处理这也是它止步于理论的原因之一。理解这一点后面第 6.4 节讨论为什么它做不了实际判素工具时会顺很多。2. 证明前必须打牢的三个模运算事实2.1 逆元配对把 1 到 p-1 按互为倒数分组第一个事实是逆元的存在性与唯一性。设 p 是素数a 是 1 到 p-1 之间的整数。因为 gcd(a, p) 1p 是素数且 a 不是 p 的倍数所以一次同余方程 ax ≡ 1 (mod p) 有解而且解在模 p 意义下唯一。把那个唯一解记作 a⁻¹它同样落在 1 到 p-1 之间因为 0 不可能是解a·0 0 ≠ 1。这个事实的意义在于它允许我们对集合 {1, 2, ..., p-1} 做一次完美配对。规则很简单把 a 和它的逆元配成一对。因为逆元唯一所以这个配对不会出现一个人属于两对的情况又因为逆运算是对合的a 的逆元的逆元还是 a所以配对关系是对称的。于是整个集合被切成若干个二元组可能还剩下几个自己配自己的元素。这种配对思路在数论里出现频率极高它本质上是一种消元——每对元素的乘积是 1乘起来就消失了只剩下无法配对的那几个。我第一次见到这个技巧是在算阶乘取模当时觉得这也太巧了后来发现它在很多地方都能复用比如计算模意义下的乘积、判断某些特殊集合的元素之和等等。你把它理解成把一堆数按能约掉的方式两两搭配就很好记了。提示这个配对能成立的前提是每个元素都有唯一的逆元而唯一的逆元需要 p 是素数或者更一般地需要元素与模数互素。如果模数不是素数那些与模数不互素的元素没有逆元配对就崩了——这正是逆命题成立的根本原因也是整个定理的分水岭。2.2 自逆元方程 x² ≡ 1 在模素数下只有两个解第二个事实是自逆元的个数。什么样的元素会在配对中剩下显然是满足 a ≡ a⁻¹ (mod p) 的元素等价于 a² ≡ 1 (mod p)也就是 (a-1)(a1) ≡ 0 (mod p)。到这里素性的作用就体现出来了p 是素数意味着乘积被 p 整除则至少有一个因子被 p 整除。所以要么 a-1 ≡ 0要么 a1 ≡ 0得到 a ≡ 1 或 a ≡ -1 ≡ p-1 (mod p)。而这两个解确实都在 1 到 p-1 范围内p ≥ 3 时 1 和 p-1 是不同元素所以自逆元恰好两个。这个乘法可消去律是素数最核心的性质整条定理的成败都压在它上面。反过来看如果模数 n 是合数方程 x² ≡ 1 (mod n) 的解会变多。举个最小的例子n 8 时1² 1、3² 9 ≡ 1、5² 25 ≡ 1、7² 49 ≡ 1四个解。解变多意味着配对之后剩下的元素不止两个整个乘积的结构就乱了。这个现象在算法里有直接应用如果一个数满足某个平方同余但解不止两个它就一定是合数这正是现代素性检测算法的核心思想之一。我建议在纸上亲手验一遍 n 8、9、12、15 这几个合数的 x² ≡ 1 的解的个数感受一下解变多这件事比看文字描述直观得多。2.3 多项式恒等x^{p-1}-1 恰好被所有非零剩余整除第三个事实是多项式视角。在模 p 的域上取任意 a ∈ {1, ..., p-1}由 a^{p-1} ≡ 1 (mod p)可知 a 是多项式 f(x) x^{p-1} - 1 的一个根。这个多项式次数是 p-1而它已经有了 p-1 个不同的根 1, 2, ..., p-1。一个次数为 d 的多项式在一个域里最多有 d 个根除非它是零多项式现在根的数量正好等于次数说明这 p-1 个根用满了。于是多项式可以完全分解成一次因式的乘积x^{p-1} - 1 ≡ ∏(x - a)其中 a 跑遍 1 到 p-1。这个分解式两边都是首一多项式恒等成立。它的价值在于一旦有了恒等式就可以比较任意次项的系数而威尔逊定理恰好就是比较常数项的直接结果。这种从根的个数推导多项式分解再比系数的套路在数论和组合里都非常常见比纯粹的配对论证更简洁也更容易推广。需要注意的是这个论证默认了 p 是素数——因为次数为 d 的多项式最多 d 个根这个性质要求系数环是域或至少是整环而模合数的剩余类环有零因子多项式可能有超出次数的根。比如模 8 时 x² - 1 就有四个根次数是 2直接违反。所以三个事实环环相扣都建立在p 是素数这个前提上。3. 充分性证明p 是素数时阶乘必为 -13.1 配对法完整走一遍含 p2 的边界先把最直观的配对证明写完整。设 p ≥ 3 为素数考虑阶乘 (p-1)! 1 × 2 × ... × (p-1)。对这 p-1 个因子按a 与 a⁻¹ 配对的规则分组。按照 2.1 的论证每一对的两个元素不同除非是自逆元乘积 ≡ 1 (mod p)于是这些对在整体乘积中的贡献全为 1。剩下的只有自逆元。按照 2.2 的论证自逆元恰好是 1 和 p-1。所以(p-1)! ≡ 1 × (p-1) ≡ p - 1 ≡ -1 (mod p)。整个过程就这么短。但我要强调的是这里面藏着一个容易忽略的细节配对之后同一对里的两个元素乘起来是 1这句话的严格含义是a 乘上 a 的逆元等于 1而不是a 乘上任意另一个元素等于 1。初学的时候容易把它想成随便配对都能消掉那是错的配对规则必须严格按逆元来。p 2 需要单独处理因为此时 1 到 p-1 只有元素 1配对论证里的1 和 p-1 是两个不同元素不成立了1 和 1 是同一个。直接代入验证(2-1)! 1! 1而 -1 ≡ 1 (mod 2)成立。所以 p 2 时定理照样对只是不能套用 p ≥ 3 的推导。这种小素数单独验证的处理在研究素数相关结论时几乎是标配因为 p 2 是唯一的偶素数很多关于奇偶对称正负号的论证在它身上会失效。写证明时不写这一句严格的评审会挑毛病。3.2 系数比较法三行推完的另一种写法第二种证法更短。由 2.3在模 p 意义下有恒等式x^{p-1} - 1 (x-1)(x-2)...(x-(p-1))。看左边常数项是 -1。看右边每个因子 (x-k) 的常数项是 -k所以整个乘积的常数项是 (-1)^{p-1} × (1 × 2 × ... × (p-1)) (-1)^{p-1} × (p-1)!。两者相等(-1)^{p-1} × (p-1)! ≡ -1 (mod p)。当 p 是奇素数时p-1 是偶数(-1)^{p-1} 1于是 (p-1)! ≡ -1。当 p 2 时p-1 1(-1)^1 -1得到 -(1!) ≡ -1也就是 1! ≡ 1 ≡ -1 (mod 2)同样成立。所以可以统一写成(p-1)! ≡ (-1)^p (mod p)而 p 奇时 (-1)^p -1p 2 时 (-1)^2 1 与 -1 在模 2 下等价。这个写法把两种情形合并了很干净。我个人更偏爱这个证法原因是它没有配对剩余这些手工操作感全程机械化写恒等式、找常数项、比系数、得结论。而且它天然指向推广——只要你能写出别的多项式恒等式就能得到别的乘积型同余式。比如把 (x^{p-1}-1)/(x-1) 拿出来单独分析或者考虑更高次的分解都能挤出新东西。不过要提醒一句交叉验证两种证法的每一步是我强烈推荐的习惯。两种证法结论一致但中间用到的工具完全不同一个是逆元配对一个是多项式根与系数如果哪一步想不清楚换另一种证法往往能补上漏洞。我有一次在给同学讲的时候配对法讲到一半卡在为什么自逆元只有两个换成系数比较法三句话就讲通了。3.3 群论视角有限交换群的全体元素之积如果熟悉一点群论这个过程可以抽象成一个更一般的结论在有限交换群里所有元素的乘积等于所有二阶元的乘积。理由和配对法完全一样——非二阶元都能和自己的逆元配对成对消掉因为交换群里的乘法可以任意重排剩下的只有满足 g² e 的元素。把这条结论套到模 p 的非零剩余构成的乘法群上这个群有 p-1 个元素是交换群且它的二阶元只有一个就是 -1因为方程 x² 1 在域里只有 ±1 两个解而 1 是一阶元不算二阶。所以全体元素之积等于 -1正是威尔逊定理。这个视角的价值在于它揭示了定理的真正来源不是阶乘本身有什么魔力而是有限交换群的元素乘积结构决定的。阶乘只是一个恰好把所有群元素乘一遍的载体。理解了这一点你就能马上知道这个结论可以推广到哪些对象上——任何有限交换群只要它的二阶元好数就能写出对应的乘积公式。更进一步模 n 的乘法群只取与 n 互素的元素在什么条件下是循环群是一个经典结论它恰好刻画了一类能让全体元素之积 ≡ -1成立的 n。这些 n 除了素数之外还包括 4、素数的幂、以及素数幂的两倍。这算是威尔逊定理的一个自然推广有意思的是 n 4 在这种推广框架下是正常成员但在原版定理里它是唯一的反例——两个视角不冲突只是讨论的对象不同原版讨论的是完整的 1 到 n-1推广版讨论的是与 n 互素的子集。3.4 小素数逐项核对表把前几个素数代进去算一遍建立数值直觉。这一步别跳过很多人证完定理但心里对到底等于几没概念。| p | (p-1)! | 阶乘值 | 除以 p 的余数 | (p-1)!1 分解 | | 2 | 1! | 1 | 1 | 2 2 | | 3 | 2! | 2 | 2 | 3 3 | | 5 | 4! | 24 | 4 | 25 5×5 | | 7 | 6! | 720 | 6 | 721 7×103 | | 11 | 10! | 3628800 | 10 | 3628801 11×329891 | | 13 | 12! | 479001600 | 12 | 479001601 13×36846277 |注意 p 5 那一行(p-1)! 1 25被 5 整除而且是被 5 的平方整除。这不是巧合5 是最小的那种威尔逊商还能被 p 整除的素数第 6.1 节会专门讲。p 13 那一行同样如此36846277 ÷ 13 2834329整除。这张表还顺便给出了一个实用的检查点如果你写的验证程序在这六个数上全部通过基本可以认为逻辑没问题如果有任何一个不对大概率是边界处理p 2 或者 n 1出了问题。4. 逆命题证明合数为什么一定不行4.1 主思路因子对凑出 n逆命题的证明思路和正向完全不同。正向是在结构清晰的集合里做配对逆向则是要证明结构崩坏——当 n 是合数时阶乘 (n-1)! 里已经包含了 n 的所有因子所以它必然是 n 的倍数不可能是 -1。核心机制是这样的n 是合数就能写成 n a × b 的形式其中 a、b 都是大于 1 小于 n 的整数。而 1 到 n-1 这个范围里恰好把 a 和 b 都包含进去了。两个因子都在阶乘的乘积里那么阶乘自然就被 a×b n 整除。这个论证有个漏洞需要补如果 a b 怎么办比如 n 9 3×3那阶乘里只有一个 3凑不出两个 3。这就是为什么分类讨论是必须的。另一种情况是 a 和 b 虽然不同但其中一个可能等于 1那就不算真分解。所以完整证明必须按 n 的形态分情况不能一句话带过。我当年第一次写这个证明就栽在这里直接写n ab故 n | (n-1)!被指出 a b 的情形没覆盖。4.2 三种形态分类讨论情形一n 有真分解 n ab且 1 a b。因为 a ≥ 2所以 b n/a ≤ n/2 n说明 b 确实在 1 到 n-1 范围内。a 和 b 都是阶乘的因子且互不相同因为 a b所以它们的乘积 ab n 整除 (n-1)!。于是 (n-1)! ≡ 0 (mod n)不等于 -1。情形二n 是完全平方 n a²且 a 2。此时 a 和 2a 都在 1 到 n-1 范围内a a² 显然a 1而 2a a² 等价于 a 2正是我们的条件。两者不同因为 a 0所以它们的乘积 2a² 2n 整除 (n-1)!自然 n 也整除 (n-1)!。同样得到 (n-1)! ≡ 0 (mod n)。这里的技巧是用 2a 代替第二个 a。因为阶乘里只有一个 a凑不出 a²但可以拿 2a 来凑——2a 本身就含有因子 aa × 2a 2a² 含有 a² 因子。多出来的那个 2 无所谓整除性只要求至少不要求恰好。情形三n 4。这是唯一被漏掉的合数4 2²a 2不满足 a 2情形二失效4 也不能写成两个不同的大于 1 的因子之积。直接验证3! 66 mod 4 2不等于 3也就是不等于 -1 mod 4。所以 4 不满足定理定理对它不成立。三种情形合起来覆盖了所有大于 4 的合数加上 4 单独验证逆命题证完。把结论整理一下对 n 1(n-1)! ≡ -1 (mod n) 成立当且仅当 n 是素数其中 n 4 是必须单独排除的假阳性它本来就不是素数只是它也不满足同余式所以不影响定理的正确性——真正的意思是 n 4 是合数里唯一需要单独讨论的那个因为它不落入阶乘 ≡ 0的模式。等等这里要说清楚一件事避免读者混淆n 4 时 (n-1)! ≡ 2 (mod 4)既不是 -1 也不是 0。它不属于合数时阶乘恒为 0的规律但结论不等于 -1依然成立。所以威尔逊定理本身没有例外例外只存在于合数时阶乘 ≡ 0这个辅助结论里。写证明的时候如果把辅助结论当成定理的一部分就会误以为定理有反例。注意区分定理有例外和证明中的辅助引理有例外。威尔逊定理对 n 4 完全成立3! 6 ≡ 2 ≠ 3所以 4 不是素数与定理一致只是证明路径上合数阶乘 ≡ 0这句话对 4 不成立需要单独验证。这个区分在写严谨证明时是硬性要求。4.3 CRT 视角补一刀还有一种更结构化的看法用中国剩余定理CRT。假设 n 4 是合数n ab 且 gcd(a, b) 1当 n 不是素数幂时总能这样拆。因为 a ≤ n/2 n-1n 4 时阶乘里含有因子 a也含有因子 b所以 (n-1)! 同时被 a 和 b 整除。a、b 互素故 (n-1)! 被 ab n 整除即 (n-1)! ≡ 0 (mod n)。CRT 视角的好处是它把凑因子的过程说清楚了阶乘里同时出现 a 和 b等价于说这个数在模 a 和模 b 下都是 0由 CRT 就知道它在模 ab 下是 0。如果 n 不是两个互素因子的乘积即 n 是素数幂就退回情形二的2a 技巧。这个视角还有一个副产品它解释了为什么素数幂是最难缠的合数。因为素数幂只有一个素因子你的因子对必须从同一个数里抠出来所以才需要借助 2a 这样的辅助元素。n 4 之所以特殊就是因为它是唯一一个连 2a 都凑不出来的素数幂a 2 时 2a 4 n超出范围。5. 从手算到代码的完整验证流程5.1 手算的规范流程以 p11、p13 为例手算不是为了得到答案是为了建立每步可查的习惯。以 p 11 为例我的一般流程是先算阶乘再做带余除法最后验证整除关系。10! 3628800。除以 1111 × 329890 3628790余 10。所以 10! ≡ 10 ≡ -1 (mod 11)。再验证整除形式10! 1 36288013628801 ÷ 11 329891整除余 0。p 13 时12! 479001600。除以 1313 × 36846277 479001601这比 12! 大 1说明 12! ≡ -1 (mod 13)。用整除形式看更直接12! 1 479001601 13 × 36846277。注意 p 13 这个例子里我用了从后往前验证的技巧先算 13 × 36846277 看是不是等于 12! 1比自己去除要快。手算大数的除法很容易出错而从商反推乘积、再对比出错率低得多。这个习惯在做数论计算题时很有用。再挑一个看起来不像的数验证一下定理的另一面。取 n 15合数14! 87178291200。按定理预测它应该 ≡ 0 (mod 15)。验证15 3 × 5阶乘里既有 3 又有 5所以被 15 整除。实际算 87178291200 ÷ 15 5811886080整除余 0符合预测。这个例子也说明合数时阶乘 ≡ 0这条规律在 n 有大因子对时非常直观。5.2 Python 实现朴素版、分块版最朴素也最不容易出错的实现就是边乘边取模。关键点是每一步都取模让中间结果永远小于 n避免阶乘值爆炸。def is_prime_wilson(n: int) - bool: if n 2: return False if n in (2, 3): return True if n % 2 0: return False f 1 for k in range(2, n): f f * k % n return f n - 1这段代码有几个细节值得说。第一n in (2, 3)提前返回是因为循环range(2, n)对 n 2 和 n 3 不执行f 保持为 1而1 n-1在 n 2 时成立、n 3 时不成立应为 2所以必须单独处理。第二n % 2 0提前排除偶数除了 2 以外的偶数都不是素数而偶数走完整个循环要跑 n-2 次纯属浪费。第三循环从 2 开始而不是从 1 开始因为乘 1 没意义。如果 n 比较大比如十万量级可以用分块累乘来减少取模次数让 Python 的大整数乘法发挥优势def wilson_mod(n: int, block: int 512) - int: f 1 k 2 while k n: end min(k block, n) chunk 1 for i in range(k, end): chunk * i f f * (chunk % n) % n k end return f分块的思路是把小因子先乘成一个中等大小的整数再整体取模。这样每个块的取模只做一次但块内的乘法不会让数字无限增长block 512 时chunk 最多有几千位Python 处理这个规模的大整数乘法还是很快的。实测下来在十万量级分块版本比朴素版本略快但优势不大因为朴素版本每步取模后数字一直很小本身就是高效的。真正拖慢速度的是 Python 的循环开销而不是乘法本身。我的建议是验证用途就用朴素版代码短、好检查只有当你需要跑到百万量级做实验时才考虑分块而且要先用朴素版在同一批数据上对齐结果确认两个版本输出一致。5.3 三个真实踩过的坑坑一直接算阶乘再取模。很多人第一反应是math.factorial(n-1) % n写起来一行搞定。在 n 20 这种小数字上确实没问题但 n 一旦上千阶乘的位数就爆炸了。10006! 大约有 35600 多位十进制数字Python 算它本身不算太慢但你如果顺手print一下或者str()一下就会撞上 Python 3.11 之后的一个限制import math n 10007 fact math.factorial(n - 1) print(len(str(fact))) # ValueError: Exceeds the limit (4300 digits) for integer string conversion这个报错我第一次见的时候懵了很久因为它跟数学毫无关系纯粹是解释器的安全限制防止超大整数转换字符串时卡死。解决办法要么是别转字符串要么调整sys.set_int_max_str_digits但根本上还是应该改成边乘边取模。坑二递归写阶乘。教科书式的def f(n): return 1 if n 1 else n * f(n-1)在 n 超过 1000 左右就会RecursionError因为 Python 默认递归深度限制是 1000。验证威尔逊定理时 n 稍微大一点就炸而且报错信息不直观容易误以为是数学逻辑有错。坑三把-1和n-1混着比。写代码时判断f n - 1但心里想着数学上的-1于是有时候会误写成f -1。Python 的%对正数返回非负余数所以f永远在 0 到 n-1 之间永远不会等于 -1这个条件恒为 False程序会认为所有数都不是素数。这种 bug 的可怕之处在于它不报错只是默默给出全错的答案。我建议在函数里加一句断言0 f n把不变量显式写出来。还有一个相关的坑n 1时如果不提前返回range(2, 1)不执行f 1而1 1 - 1 0为 False返回 False——结果碰巧是对的1 不是素数但这是错得正确逻辑上站不住。如果哪天代码结构改了这个巧合就保不住了。6. 定理往外延伸的四条线索6.1 威尔逊商与已知的三个例外把 (p-1)! 1 除以 p得到的商 W(p) ((p-1)! 1) / p 叫作威尔逊商。定理保证这个商永远是整数但它本身是不是 p 的倍数则是另一个问题。当 p 整除 W(p) 时说明 (p-1)! ≡ -1 (mod p²)这类素数被单独命名。前几个数算一下p 5 时 W 25/5 55 被 5 整除符合p 7 时 W 721/7 103103 不被 7 整除7 × 14 987 × 15 105不符合p 11 时 W 3628801/11 329891试着除一下 1111 × 29990 329890余 1不符合p 13 时 W 479001601/13 3684627713 × 2834329 36846277符合。目前已知满足这个更强条件的素数只有三个5、13、563。第三个要算到 562! 才能验证手算是不可能的必须靠程序。这个只有三个的事实本身挺有意思——一个看起来应该有无穷多个的性质实际搜下来只有三个而且已经搜到了极大的范围还是没有第四个。有没有无穷多个、甚至有没有第五个目前都是开放问题。提示这类满足某个加强同余条件的素数在数论里很常见它们的共同特点是验证一个需要 O(p) 的工作量而候选者要遍历所有素数所以搜索范围的上限基本由算力决定。如果你想动手试试可以写个程序扫前几十万个素数看能不能找到第四个——大概率找不到但这个过程能让你对稀疏性有切身体会。6.2 半阶乘的平方与二次剩余判别把阶乘劈成两半会得到一个很有用的推论。对奇素数 p考虑(p-1)! 1 × 2 × ... × ((p-1)/2) × ((p1)/2) × ... × (p-1)。后半段的每个因子都可以写成 p - k 的形式其中 k 从 1 到 (p-1)/2。于是 p - k ≡ -k后半段整体 ≡ (-1)^{(p-1)/2} × ((p-1)/2)!。合并两半(p-1)! ≡ (-1)^{(p-1)/2} × [((p-1)/2)!]² (mod p)。左边由威尔逊定理等于 -1所以[((p-1)/2)!]² ≡ (-1)^{(p1)/2} (mod p)。这个式子的意义是当 p ≡ 1 (mod 4) 时右边等于 -1说明 -1 是模 p 的二次剩余因为它等于某个数的平方当 p ≡ 3 (mod 4) 时右边等于 1。这就给出了-1 是不是二次剩余的一个显式判据而且这个判据是构造性的——它直接告诉你 -1 的平方根就是 ((p-1)/2)! 本身或者它的相反数。代码验证很直接def half_fact_sq(p: int) - int: h 1 for k in range(1, (p - 1) // 2 1): h h * k % p return h * h % p for p in [5, 7, 11, 13, 17, 19, 23, 29]: print(p, p % 4, half_fact_sq(p))跑出来的规律是p ≡ 1 (mod 4) 时输出 p-1即 -1p ≡ 3 (mod 4) 时输出 1。p 5 输出 4p