威爾遜定理

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