模算術/威爾遜定理

威爾遜定理

自然數 $\alpha$ 是素數，當且僅當

$(\alpha -1)!\equiv -1{\pmod {\alpha }}$

其中 $\alpha !$ 表示 $\alpha$ 的階乘，即小於或等於 $\alpha$ 的所有自然數的乘積，對於每個自然數。

示例

5 是素數，因為

$4!=24$

並且

$24\equiv -1{\pmod {5}}\implies 25|5$

這是正確的。另一方面，6 不是素數，因為

$5!=120$

並且

$120\equiv -1{\pmod {6}}\implies 121|6$

這是錯誤的。