数论四大定理
Ⅰ.威尔逊定理
Ⅱ.欧拉定理
Ⅲ.孙子剩余定理
Ⅳ.费马小定理
威尔逊定理
内容
若一个数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)$
证明完毕
