Complicate less.

Wilson定理学习笔记

一、引入题目 #

考虑一道数学题目：求 10!10! 除以 1111 的余数。

我们要算的是

10!=1⋅2⋅3⋅4⋅5⋅6⋅7⋅8⋅9⋅10 10!=1\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7\cdot8\cdot9\cdot10

除以 1111 后剩下多少，也就是求 10! mod 1110!\bmod11。

这么长的一串乘积，怎样计算更方便？

1. 暴力计算 #

最直接的办法是先算出阶乘：

10!=3 628 800=11⋅329 890+10. 10!=3\,628\,800=11\cdot329\,890+10.

所以余数是 1010，写成同余式就是

10!≡10≡−1(mod11). 10!\equiv10\equiv-1\pmod{11}.

也可以边乘边取余，让中间的数保持小一些。

接下来换个角度：能不能调整乘法顺序，让某些部分特别容易计算？

2. 分组计算 #

计算

25⋅17⋅4 25\cdot17\cdot4

时，我们通常会先算 25⋅4=10025\cdot4=100。乘法允许交换顺序，就可以优先组合容易处理的因子。

在模 1111 的计算中，什么样的组合最方便？

乘积余 11 就很好。因为乘以 11，其他部分的余数保持不变。

先看 22。在原来的因子中找一个数，乘以 22 后比 1111 的倍数多 11：

2⋅6=12=11+1. 2\cdot6=12=11+1.

所以

2⋅6≡1(mod11). 2\cdot6\equiv1\pmod{11}.

这样，22 和 66 就可以一起处理了。继续找：

3⋅4=12≡1(mod11), 3\cdot4=12\equiv1\pmod{11},

5⋅9=45≡1(mod11), 5\cdot9=45\equiv1\pmod{11},

7⋅8=56≡1(mod11). 7\cdot8=56\equiv1\pmod{11}.

整个乘积因此可以重排为

10!=1⋅10⋅(2⋅6)(3⋅4)(5⋅9)(7⋅8). 10!=1\cdot10\cdot(2\cdot6)(3\cdot4)(5\cdot9)(7\cdot8).

取模后，括号里的每一组都变成了 11：

10!≡1⋅10⋅1⋅1⋅1⋅1≡−1(mod11). 10!\equiv1\cdot10\cdot1\cdot1\cdot1\cdot1 \equiv-1\pmod{11}.

这次计算里，最值得注意的是：除了 11 和 1010，其余因子恰好能两两配对，每对的乘积都余 11。

二、规律引申 #

把 1111 换成 77，试着计算 6!6! 除以 77 的余数。

我们有

6!=1⋅2⋅3⋅4⋅5⋅6. 6!=1\cdot2\cdot3\cdot4\cdot5\cdot6.

其中

2⋅4=8≡1(mod7),3⋅5=15≡1(mod7). 2\cdot4=8\equiv1\pmod7, \qquad 3\cdot5=15\equiv1\pmod7.

于是

6!=1⋅6⋅(2⋅4)(3⋅5)≡1⋅6≡−1(mod7). 6!=1\cdot6\cdot(2\cdot4)(3\cdot5) \equiv1\cdot6\equiv-1\pmod7.

同样的现象又出现了：配对后，留下最前面的 11 和最后面的 66，结果仍然是 −1-1。

77 和 1111 都是素数。我们自然会问：

对任意素数 pp，是不是都有

(p−1)!≡−1(modp)(p-1)!\equiv-1\pmod p

成立？

要证明之前，需要先理解“逆元”的概念。

刚才找到的 22 和 66 满足

2⋅6≡1(mod11). 2\cdot6\equiv1\pmod{11}.

我们把这种关系叫作：22 和 66 模 1111 互为乘法逆元。

一般地，如果

ab≡1(modm), ab\equiv1\pmod m,

就称 bb 是 aa 模 mm 的乘法逆元；同时，aa 也是 bb 的逆元。

所以，“逆元配对”就是把相乘余 11 的两个因子放在一起。

三、分析思路 #

Wilson定理的思想可以拆分成多个子问题：

  1. 每个因子是不是都能找到对应的搭档（逆元）？
  2. 这个搭档是唯一的吗，会不会有一对多的情况？会不会出现指向自己的情况？
  3. 所有的因子都能被用完吗，会不会有多余因子无法成对？

接下来我们逐个分析。

1. 寻找搭档 #

设 pp 是素数，取一个因子

a∈{1,2,…,p−1}. a\in\{1,2,\ldots,p-1\}.

由于 aa 比 pp 小，且不为 00，所以

gcd⁡(a,p)=1. \gcd(a,p)=1.

根据贝祖等式，存在整数 u,vu,v，使

au+pv=1. au+pv=1.

对 pp 取模，就得到

au≡1(modp). au\equiv1\pmod p.

这已经找到了 aa 的逆元。再把 uu 换成它模 pp 的余数 bb，仍然有

ab≡1(modp). ab\equiv1\pmod p.

这个余数不可能是 00，因此 bb 就在 1,2,…,p−11,2,\ldots,p-1 中。

也就是说，每个因子都能找到搭档，而且搭档就在原来的乘积里面。

2. 搭档唯一 #

假如 aa 同时与 b,cb,c 配对，那么

ab≡1(modp),ac≡1(modp). ab\equiv1\pmod p, \qquad ac\equiv1\pmod p.

于是

a(b−c)≡0(modp). a(b-c)\equiv0\pmod p.

由于 pp 是素数，且 p∤ap\nmid a，只能有 p∣(b−c)p\mid(b-c)，即

b≡c(modp). b\equiv c\pmod p.

而 b,cb,c 都在 1,…,p−11,\ldots,p-1 中，所以 b=cb=c。

因此，每个因子在这组数中只有一个搭档。

而且，ab≡1ab\equiv1 同时意味着 ba≡1ba\equiv1。所以 aa 的搭档是 bb，bb 的搭档就一定是 aa：

a⟷b. a\longleftrightarrow b.

不会出现“aa 找 bb，bb 又找另一个数”的情况。

现在我们解决了不会出现一对多的证明问题，那么会不会在一对一里面出现指向自己的情况呢？

模 1111 的计算中，最后留下了 11 和 1010。看看它们的平方：

12≡1(mod11),102≡1(mod11). 1^2\equiv1\pmod{11}, \qquad 10^2\equiv1\pmod{11}.

它们的逆元正好都是自己。

可是阶乘中，每个因子只出现一次。我们不能再拿一个 1010 与原来的 1010 相乘，所以它需要单独留下。

换成一般的素数 pp，哪些数会有这种情况？只要解

a2≡1(modp). a^2\equiv1\pmod p.

因式分解：

p∣(a−1)(a+1). p\mid(a-1)(a+1).

因为 pp 是素数，必有

a≡1(modp)或a≡−1(modp). a\equiv1\pmod p \quad\text{或}\quad a\equiv-1\pmod p.

因此，对奇素数 pp，恰好只有 11 和 p−1p-1 的逆元是自己。这也解释了为什么前面两道例题最后留下的，总是这两个位置上的数。

3. 完美分组 #

每个数都有唯一搭档，怎么保证把它们放在一起时，不会漏掉谁，也不会重复用到谁？

我们可以实际执行一个“取走配对”的过程。

对奇素数 pp，先留下 1,p−11,p-1，然后：

  1. 从剩余数中任取一个 aa。
  2. 找到它的逆元 bb。
  3. 把 a,ba,b 一起取走。
  4. 对尚未取走的数重复上述操作。

这里的 bb 与 aa 不同，因为自身为逆元的两个数已经留下了。它也不会是 11 或 p−1p-1，因为这两个数各自的唯一搭档就是自己。

最关键的问题是：找到 bb 时，它会不会已经被前面的配对取走了？

假如 bb 之前已经被取走，那么它当时是和谁一起走的？

它唯一的搭档就是 aa。所以，aa 当时也应该一起被取走。

但我们刚刚还能从剩余数中选到 aa，这就矛盾了。

因此，只要 aa 还在，它的搭档 bb 就一定也还在。 每次都能取走两个尚未使用的数。原来的数又是有限的，最后就会全部配完，每个数恰好使用一次。

于是整个乘积只剩下

1⋅(p−1)≡−1(modp). 1\cdot(p-1)\equiv-1\pmod p.

四、标准证明 #

接下来我们给出Wilson定理的标准形式和证明。

Wilson 定理：对整数 n>1n>1，

n 是素数  ⟺  (n−1)!≡−1(modn). \boxed{n\text{ 是素数}\iff(n-1)!\equiv-1\pmod n.}

1. 必要性：若 pp 是素数，则 (p−1)!≡−1(modp)(p-1)!\equiv-1\pmod p #

当 p=2p=2 时，

1!=1≡−1(mod2), 1!=1\equiv-1\pmod2,

结论成立。下面设 pp 是奇素数。

对每个 a∈{1,2,…,p−1}a\in\{1,2,\ldots,p-1\}，因为 gcd⁡(a,p)=1\gcd(a,p)=1，存在唯一的逆元代表 a−1∈{1,2,…,p−1}a^{-1}\in\{1,2,\ldots,p-1\}，使

aa−1≡1(modp). aa^{-1}\equiv1\pmod p.

（贝祖定理推论，详见贝祖定理）

逆元等于自身的条件为

a2≡1(modp), a^2\equiv1\pmod p,

也就是

p∣(a−1)(a+1). p\mid(a-1)(a+1).

由于 pp 是素数，必有

a≡1(modp)或a≡−1(modp). a\equiv1\pmod p \quad\text{或}\quad a\equiv-1\pmod p.

因此，在 1,…,p−11,\ldots,p-1 中，只有 11 和 p−1p-1 的逆元等于自身。

其余元素都能分成互不重叠的二元组

{a,a−1}, \{a,a^{-1}\},

每组的乘积模 pp 都等于 11。所以

(p−1)!≡1⋅(p−1)⋅1⋯1≡−1(modp). (p-1)! \equiv1\cdot(p-1)\cdot1\cdots1 \equiv-1\pmod p.

必要性得证。

2. 充分性：若 (n−1)!≡−1(modn)(n-1)!\equiv-1\pmod n，则 nn 是素数 #

用反证法。假设 nn 是合数，则存在整数 dd 满足

1<d<n,d∣n. 1<d<n,\qquad d\mid n.

因为 dd 是乘积 1⋅2⋯(n−1)1\cdot2\cdots(n-1) 中的一项，所以

d∣(n−1)!. d\mid(n-1)!.

另一方面，由已知同余式，

n∣((n−1)!+1). n\mid\bigl((n-1)!+1\bigr).

结合 d∣nd\mid n，得到

d∣((n−1)!+1). d\mid\bigl((n-1)!+1\bigr).

将这两个整除关系相减，便得

d∣1, d\mid1,

与 d>1d>1 矛盾。因此 nn 必为素数，充分性得证。

五、总结 #

回到最开始的问题：为什么要用逆元配对的思想来分析？

因为我们面对的是一个长乘积，想让计算简单，就可以尝试寻找乘积为 11 的因子对。

试了几个数之后，发现这样的组合恰好能覆盖大部分因子，然后猜测这种规律能不能推广到任意素数？

在证明部分，必要性主要用了贝祖定理的推论，来验证分组乘算模 pp 为1；充分性则采用反证法思路，从合数定义出发推出矛盾。

对于 Wilson 定理本身，核心主线可以记为一句话：

逆元两两配对，乘积都化为 11，最后留下头尾的 11 和 −1-1。

回到顶部