威尔逊定理

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

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

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

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

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

: (ij)\ \equiv\ 1 \pmod{p}

這幾乎說明A中的元素恰好两两配对。僅有滿足
:x^2\ \equiv\ 1 \pmod{p}
的元素x是例外。

上式解得
: x\ \equiv\ 1 \pmod{p}
或
: x\ \equiv\ p-1 \pmod{p}

其余两两配对，故而
:(p-1)!\ \equiv\ 1 \times (p-1)\ \equiv\ -1 \pmod{p}.

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

故而

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

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

參考文獻