威尔逊定理证明

威尔逊定理：当且仅当n为质数时，n能整除(n-1)!+1。 证明：

⭐️必要性：若n能整除(n-1)!+1,但n不是质数。则n一定可以分解为2个以上质因数乘积。假设a是其中一个质因数则a能整除(n-1)!+1；但是a能整除(n-1)!，且a不能整除1，所以a不能整除(n-1)!+1。与前述矛盾所以n一定是质数。

⭐️充分性：若n为质数p，则任意整数除以p的余数都在集合{1,2,3,...,p-1}中。首先任意两个数的乘积除以p的余数等于分别除以p的余数之积。我们只要证明(p-1)!=-1(mod p)。以7为例，若p=7则在1，2，3，4，5，6中2*4=8，3*5=15二者除以7都余1，剩下1*6=6除以7余-1.所以6！=-1(mod 7).那么如果对于任何素数p，在{2,3,4,...,p-2}中都能两两配对，使得乘积除以7余1，那么问题就解决了。

设A={2,3,4,...,p-2}，从中任取一个元素a，要证明A中还存在元素b使得ab=1(mod p)。这个b必须不等于1或者p-1或者a本身，而且对于不同的a这个b也要不一样，我们先证明这样的b是存在的。不如让a去乘以所有 A的元素(加上另外两个也就是1和p-1)形成一个新的集合B={a,2a,3a,...,(p-1)a}这个集合内的数除以p的余数都是不相同的，因为p是质数且a

假如b=1那么ab=a除以p后余a而a是A 中的元素即a不等于1，故b不等于1；假如b=p-1，则ab=(p-1)a=pa-a,除以p后余a，同样由于a不等于1，所以b不能等于p-1；假如b=a，则ab=a^2，若a^2除以p余1的话那么a^2-1能被p整除，a^2-1=(a+1)(a-1)由于a是A中的元素，所以a-1也是a中的元素(a不等于1)所以a-1和p互质最小公倍数为(a-1)p，而1<(a-1)p所以不能被p整除，与前述矛盾，所以b不等于a。综上b是A中不同于a的元素

假如有两个A中的元素a1，a2不相同，却有相同的b使得ba1和ba2除以p后余数都为1，那么|a1-a2|b能被 p整除，但是与上面同理|a1-a2|b

综上所述对于任意质数p，{2,3,4,...,p-2}中的数都可以两两配对乘积使得除以p后的余数等于1，所以2*3*4*...*（p-2）的除以p的余数为1，而1*（p-1）除以p的余数为-1，所以(p-1)!除以p的余数为-1。所以(p-1)!+1能被p整除。