威尔逊定理

维基百科,自由的百科全书
跳转至: 导航搜索

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

初等数论中,威尔逊定理给出了判定一个自然数是否为素数充分必要条件。即:当且仅当p为素数时:

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

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

证明[编辑]

充分性[编辑]

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

必要性[编辑]

若p是素数,取集合 A = \left\{1,2,3,...p-1\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 * (p-1)\ \equiv\ -1 \pmod{p}

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

故而

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