威尔逊定理

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

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

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

但是由于阶乘是呈爆炸增长的，其结论对于实际操作意义不大。

证明

如果“p”不是質數，那么它的正因数必然包含在整数2, 3, 4, … , p − 1 中，因此gcd((p − 1)!, p) > 1，所以我们不可能得到(p − 1)! ≡ −1 (mod p)。

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

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

那么A中的元素是不是恰好两两配对呢? 不一定,但只需考虑这种情况

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

;

解得: $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}}$ 如下：

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

所以

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

，移項左右交換位置即得

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

。

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.