收集的威尔逊定理证明

在求解[BNUOJ 1093 YAPTCHA][1]时，用到了威尔逊定理。

在这里收集整理一下证明威尔逊定理的方法。

先说从题意出发吧。这道题是给定一个式子

再给若干个n，让你求出Sn的值。其中1<=n<=10^6

<!-- more -->

</img>

暴力肯定是不行的。所以考虑数论的方法。

    当3k+7不是素数时，可以得到((3k+6)!+1)/(3k+7)=(3k+6)!/(3k+7)，此时括号内的值为0.

    当3k+7是素数时，由威尔逊定理知(3k+6)! = -1 (mod 3k+7) ，可以得到((3k+6)!+1)/(3k+7)=[(3k+6)!/(3k+7)]+1，此时括号内的值为1.

所以解法就是筛出素数表，然后从0到10^6，判断素数，是素数就等于前一项的值+1，不是素数就直接等于前一项的值，答案保存到一个数组中即可。

威尔逊定理：当( p -1 )! ≡ -1 ( mod p ) 时，p为素数。

证明如下

充分性：

  当p不是素数，那么令p=a*b ，其中1 < a < p-1 ,1 < b < p-1.
(1)若a≠b,
    因为(p-1)!=1*2*...*a*...*b*...*p-1,
    所以(p-1)!≡ 0 (mod a)        
           (p-1)!≡ 0 (mod b)
    可得(p-1)!≡ 0 (mod a*b) ，
          即 (p-1)!≡ 0 (mod p)
    与( p -1 )! ≡ -1 ( mod p )  矛盾
(2)若a=b
    因为(p-1)!=1*2*...*a*...*2a*...*p-1.
    所以(p-1)!≡ 0 (mod a)          
           (p-1)!≡ 0 (mod 2a)
    可得(p-1)!≡ 0 (mod a*2a) => (p-1)!≡ 0 (mod a*a) ，
      即 (p-1)!≡ 0 (mod p)
    与( p -1 )! ≡ -1 ( mod p )  矛盾
    因此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) 

---

证明完毕 [1]:http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=1093