求真百科欢迎当事人提供第一手真实资料,洗刷冤屈,终结网路霸凌。

威尔逊定理查看源代码讨论查看历史

事实揭露 揭密真相
跳转至: 导航搜索
威尔逊定理
图片来自博客园网络

威尔逊定理在初等数论中,它给出了判定一个自然数是否为素数的充分必要条件。即:当且仅当p为素数时:( p -1 )! ≡ -1 ( mod p ),但是由于阶乘是呈爆炸增长的,其结论对于实际操作意义不大,但借助计算机的运算能力有广泛的应用,也可以辅助数学推导。[1]

如果“p”不是素数,当p=4时,显然(p-1)!≡6≡2(mod p), 当p>4时,若p不是完全平方数,则存在两个不等的因数a,b使得ab=p,则(p-1)!≡nab≡0(mod p);若p是完全平方数即p=k^2,因为p>4,所以k>2,(k,2k)<p,(p-1)!≡n(k*2k)≡2nk^2≡0(mod p)。

必要性

若p是素数,取集合 A={1,2,3,...p -1}; 则A 构成模p乘法的简化剩余系,即任意i∈A ,存在j∈A,使得:

( i j ) ≡ 1 ( mod p )那么A中的元素是不是恰好两两配对呢? 不一定,但只需考虑这种情况

x^2 ≡ 1 ( mod p )

解得: x ≡ 1 ( mod p ) 或 x ≡ p - 1 ( mod p )

其余两两配对;故而

( p - 1 )! ≡ 1﹡( p -1 ) ≡ -1 ( mod p )

必要性证明

证明:若p为质数,则p可整除(p-1)!+1。

方法一

p=2,命题显然成立;

p=3,命题显然成立;

假设B中被p除余一的数是γa:

一若γ=1,则γa=a,它被p除余a,又因为a不等于1,所以γ=1不成立;

二若γ=p-1,则γa=(p-1)a,它被p除余p-a,又因为a不等于p-1,所以γ=p-1不成立;

由一二三知γ≠a且a,γ∈A。

a不同时,γ也相异;若a1≠a2, a1,a2∈A,且γa1≡γa2≡1(mod p),因,γa1,γa2∈B,而B中的元素关于mod p不同余,可见a1≠a2,则γ1≠γ2。

即A中的每一个a均可找到与其配对的y,γ∈A使ay≡1(mod p),

又,a不同时,γ也相异。

因此,A中的偶数个(p-3个)元素可以分成(p-3)/2个二元组(a,y),每个二元组都满足ay≡1(mod p),

∴ 1×2×3×4....(p-2)≡1(mod p)

p-1≡-1(mod p)

∴ (p-1)!≡-1(mod p)

从而p可整除(p-1)!+1

方法二

对于偶质数2,命题显然成立;

对于奇质数,令a∈A={2,3,4.....p-2},则B={a,2a,3a,.....,(p-1)a}中不会有对于除数p同余的两个数;事实上αa,βa∈B,αa≡βa(mod p),则a|α-β|能被p整除,而a|α-β|∈B,B中的元素不可能被p除尽。于是B中被p除得的余数形成集合{1,2,3,...,p-1}.

假设b中被p除余一的数是γa:

一若γ=1,则γa=a,它被p除余a,所以γ=1不成立;

二若γ=p-1,则γa=(p-1)a,它被p除余a,所以γ=p-1不成立;

三若γ=a,则γa=a*a,由于a*a≡1(mod p),故应有a*a-1=(a+1)(a-1)≡0(mod p),这只能是a=1或a=p-1,此与a∈A矛盾,故不成立;

由一二三知γ≠a且a∈A。

a不同时,γ也相异;若a1≠a2, a1,a2∈A,且γa1≡γa2≡1(mod p),因,γa1,γa2∈B,而B中的元素关于mod p不同余,可见a1≠a2,则γ1≠γ2。

依次取a为2,3,...,(p-1)/2;使γa≡1(mod p)的数γ分别为(p-1)/2+1,(p-1)/2+2,...,(p-1)/2,

即2*【(p-1)/2+1】≡3*【(p-1)/2+2】≡4*【(p-1)/2+3】≡...【(p-1)/2】*(p-2)≡1(mod p)

从而2*【(p-1)/2+1】*3*【(p-1)/2+2】*4*【(p-1)/2+3】*...*【(p-1)/2】*(p-2)≡1(mod p)

2*3*4*5*6*...*(p-2)≡1(mod p)

又p-1≡-1(mod p),则

(p-1)!=1*2*3*4*5*...*(p-2)*(p-1)≡-1(mod p)

从而p可整除(p-1)!+1

参考来源

  1. 威尔逊定理,博客园,