威爾遜定理

威爾遜定理是以英格蘭數學家愛德華·華林的學生約翰·威爾遜命名的，儘管這對師生都未能給出證明。華林於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}}$