『算法-ACM 竞赛-数学-数论』四大定理之威尔逊定理

威尔逊定理
当 $(p−1)!≡−1(modp)$时，$p$为素数。
$p∣(p−1)!+1$
即$(p−1)!≡(p−1)≡−1(mod p)$
证明（静下心看）：
充分性：
$(p−1)!≡−1(modp)⟺p∣(p−1)!+1$
假设$p$ 不是质数，且 $a$是 $p$ 的质因子。
易知$a∣(p−1)!$，则$a∤(p−1)!+1$
而$p∣(p−1)!+1⟹a∣(p−1)!+1$，前后矛盾！
故 $p$ 一定为质数。
必要性：
必要性：

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

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

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

    对于a∈M，令N={a,2*a,3*a,4*a,....(p-2)*a,(p-1)*a}

    令1 <= t1 <= p-1 ,1 <= t2 <= p-1,t1 ≠ t2

    那么t1*a∈N，t2*a∈N。

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

    因为|t1-t2|*a∈N，与N中元素不能被p除尽矛盾。

    所以t1*a≡t2*a不成立。

    那么N中元素对p取模后形成的集合为{1,2,3,4,...,p-1}.

    设x*a ≡ 1 (mod p)。

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

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

            当x=a时，a*a≡1 (mod p)，可得(a+1)*(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*2*3*...p-1

              =1*(2*x1)*(3*x3)*...*(p-1)

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

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

   证明完毕