数论入门:四大定理之威尔逊定理

数论四大定理

Ⅰ.威尔逊定理

Ⅱ.欧拉定理

Ⅲ.孙子剩余定理

Ⅳ.费马小定理

威尔逊定理

内容

若一个数p为素数的充要条件为:p可以整除$(p+1)!+1$

证明

充分性

证明定理的充分性，则只要证明当p可以整除$(p+1)!+1$时，p为素数。

考虑到从正面直接证明不太好证明，则考虑使用反正法，也就是证明该命题的逆否命题，p为合数时，p不能整除$(p+1)!+1$

进一步把命题公式化，也就是:

若p为合数，则$(p-1)!+1≡0(\mod p)不成立$

也就是p为素数，则$(p-1)!≡-1(\mod p)不成立$

原因很简单，因为$(p-1)!+1≡0(\mod p)$，则$(p-1)!+1=p\times x+0$
移项得
$(p-1)!=p\times x-1$
于是初步把这个式子定为$(p-1)!≡-1(\mod p)$

那么当p为素数时，有$p=a\times b$ $(1 < a < p-1,1 < b < p-1)$，

a，b有以下两种情况

①.$a\neq b$

②.$a=b$

①

当$a\neq b$时，
因为$1 < a < p-1,1 < b < p-1$

$(p-1)!=1 \times 2 \times …\times a \times …\times b \times… \times (p-1)$,

所以$(p-1)!≡ 0 (\mod a*b)$，
即 $(p-1)!≡ 0 (\mod p)$

与( p -1 )! ≡ -1 ( mod p ) 矛盾

②

因为方程$a^2 > 2a$在非负数域的解为$a > 2$,则当a>2时有如下等式
$(p-1)!=1 \times 2 \times … \times a \times …\times 2a \times … \times (p-1)$.

所以可得((p-1)!≡ 0 (mod a*a) ，即 $(p-1)!≡ 0 (mod p)$
与$(p -1 )! ≡ -1 ( mod p )$ 矛盾

当$p=4$，也就是a=2时，$(p-1)!≡ 3 (mod p)$与$(p -1 )! ≡ -1 ( mod p )$ 矛盾

因此定理的充分性得证。

必要性

证明必要性，也就是证明命题:

若p为素数则$(p-1)!≡-1(\mod p)$

要证此命题只要证明:

$(p-1)!≡p-1(\mod p)$
也就是证明：

$(p-2)!≡1(\mod p)$

于是先对特殊情况进行讨论：

当p为2，$( p -1 )! ≡ -1 ( \mod p )$ 显然成立

当p为3，$( p -1 )! ≡ -1 ( \mod p ) $显然成立

接下来我们情况进行讨论：

证明$(p-2)!≡1(\mod p)$，也就是证明在$[1,p-1)$中，除1以外的任意一元素a都能找到唯一一个元素b，使得$a\times b≡ 1 (\mod p)$

下面证明唯一性:

证明唯一性也就是证明任意一个元素，无法找到某两个元素t1,t2，使得

$a\times t1≡a\times t2(\mod p)$

对于$p\geq 5$，令$M={2,3,4,…,p-2}$.

对于$a\in M$，令$N={a,2\times a,3\times a,4\times a,….(p-2)\times a,(p-1)\times a}$

令$1 \leq t1 \leq p-1 ,1 \leq t2 \leq p-1,t1 ≠ t2$

那么$t1\times a\in N，t2\times a\in N$。

若$t1\times a≡t2\times a (\mod p)$ ，那么$|t1-t2|\times a ≡ 0 (\mod p)$。

因为$|t1-t2|\times a\in N$，与N中元素不能被p除尽矛盾。

所以$t1\times a≡t2\times a(\mod p)$不成立,唯一性得证。

下面证明存在性：

证明存在性也就是证明对于任意一个元素$a\in M$，存在一个元素$b\in M$使得$a\times b≡0(\mod p)$。

设$x\in [1,p),且 x\times a ≡ 1 (\mod p)$。

当$x=1$时,$x\times a=a$,对p取模为a，所以不成立。

当$x=p-1$时,$(p-1)\times a=p\times a-a$, 对p取模为-a，所以不成立。

当$x=a$时，$a\times a≡1 (mod p)$，可得$(a+1)\times (a-1)≡ 0 (mod p),a=1或a=p-1$，所以不成立。

综上所述，x,a∈M，并且当a改变时，x随之改变,所以存在性得证。

所以，M集合中每一个元素a都能够找到一个与之配对的x，使得x*a ≡ 1 (mod p).

$(p-1)!=1\times 2 \times 3 \times … (p-1)=1 \times (2 \times x_2) \times (3 \times x_3)_…\times (p-1)$

所以，$(p-1)!≡1*(p-1)(\mod p)$

即，$(p-1)!≡-1(\mod p)$

证明完毕

参考链接

Ⅰ.百度百科

Ⅱ.BNUOJ 1093 YAPTCHA题解