证明威尔逊定理的逆定理_威尔德定理

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

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

（即：p是质数，则(p-1)! ≡ p-1 ≡ -1(mod p)）

综合来说，就是：( p -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) 

       证明完毕