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

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

( p 1 ) !     1   ( mod   p ) {\displaystyle (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 = { 1 , 2 , 3 , . . . p 1 } {\displaystyle A=\left\{1,2,3,...p-1\right\}} ;则A 构成模p乘法的缩系,即任意i∈A ,存在j∈A,使得:

( i j )     1 ( mod p ) {\displaystyle (ij)\ \equiv \ 1{\pmod {p}}}

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

x 2     1 ( mod p ) {\displaystyle x^{2}\ \equiv \ 1{\pmod {p}}} ;

解得: x     1 ( mod p ) {\displaystyle x\ \equiv \ 1{\pmod {p}}}

x     p 1 ( mod p ) {\displaystyle x\ \equiv \ p-1{\pmod {p}}}

其余两两配对;故而

( p 1 ) !     1 ( p 1 )     1 ( mod p ) {\displaystyle (p-1)!\ \equiv \ 1*(p-1)\ \equiv \ -1{\pmod {p}}}

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

故而

( p 1 ) !     1 ( mod p ) {\displaystyle (p-1)!\ \equiv \ -1{\pmod {p}}}
www.zuoweixin.com
问题反馈联系QQ:暂无联系方式,也可发qq邮箱。