威尔逊定理

威尔逊定理是以英格兰数学家爱德华·华林的学生约翰·威尔逊命名的，尽管这对师生都未能给出证明。华林于1770年提出该定理，1771年由拉格朗日首次证明^[1]。

在初等数论中，威尔逊定理给出了判定一个自然数是否为質數的充分必要条件。即：当且仅当${\displaystyle p}$为質數时：

${\displaystyle (p-1)!\ \equiv \ -1\ ({\mbox{mod}}\ p)}$

证明

充分性

如果 ${\displaystyle p}$  不是質數，那么它的正因数必然包含在整数 ${\displaystyle 2,3,4,\cdots ,p-1}$  中，因此 ${\displaystyle \gcd((p-1)!\ ,p)>1}$  ，所以不可能得到 ${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$ 。

必要性

若${\displaystyle p}$ 是質數，取集合 ${\displaystyle A=\left\{1,2,3,...p-1\right\}}$ ， 则${\displaystyle A}$ 构成模${\displaystyle p}$ 乘法的缩系，即任意 ${\displaystyle i\in A}$ ，存在 ${\displaystyle j\in A}$ ，使得：

${\displaystyle (ij)\ \equiv \ 1{\pmod {p}}}$ 

這幾乎說明${\displaystyle A}$ 中的元素恰好两两配对。僅有滿足

${\displaystyle x^{2}\ \equiv \ 1{\pmod {p}}}$ 

的元素${\displaystyle x}$ 是例外。

上式解得

${\displaystyle x\ \equiv \ 1{\pmod {p}}}$ 

或

${\displaystyle x\ \equiv \ p-1{\pmod {p}}}$ 

其余两两配对，故而

${\displaystyle (p-1)!\ \equiv \ 1\times (p-1)\ \equiv \ -1{\pmod {p}}.}$ 

若${\displaystyle p}$ 不是質數且大于4， 则易知有${\displaystyle d=\gcd[p,(p-1)!]=p,}$ 

故而

${\displaystyle (p-1)!\ \equiv \ -1{\pmod {p}}.}$ 

推論

可以藉此推論${\displaystyle (p-2)!\equiv 1{\pmod {p}}}$ 如下：

${\displaystyle (p-2)!\equiv -(p-1)(p-2)!\equiv -(p-1)!\equiv 1{\pmod {p}}}$ 

參考文獻

1. Joseph Louis Lagrange. . Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres (Berlin). 1771, 2: 125–137 [2021-11-08]. （原始内容存档于2022-05-11） （法语）.