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

证明威尔逊定理的逆定理_威尔德定理威尔逊定理:当( p-1)!≡-1(modp) 时,p为素数。证明如下充分性:当p不是素数,那么令p=a*b,其中1  (1)若a≠b,    因为(p-1)!=1*2*…*a*…*b*…*p-1,    所以(p-1)!≡0(moda)            (

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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) 

       证明完毕

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/234348.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 大疆测评攻略

    他说大疆测评也刷人比例还很高总结来网上的有关注意事项都是各方面搬一点,总结一下测评的题主要为:性格测试,逻辑测试,计算题,场景题。这类的题⽬我能给你们的建议只是针对性格测试和场景题这类的主观性题。DJI大疆2019在线测评-知乎https://zhuanlan.zhihu.com/p/76053124大疆招聘网申测评测试笔试题https://zhuanlan.zhihu.com/p/157371591大疆在线测试三段论https://bbs.yingjiesheng.com/thr

  • 搞定Android开发环境部署——非常详细的Android开发环境搭建教程[通俗易懂]

    搞定Android开发环境部署——非常详细的Android开发环境搭建教程[通俗易懂]引言在windows安装Android的开发环境不简单也说不上算复杂,本文写给第一次想在自己Windows上建立Android开发环境投入Android浪潮的朋友们,为了确保大家能顺利完成开发环境的搭建,文章写的尽量详细,希望对准备进入Android开发的朋友有帮助。 Android开发环境搭建分为以下四步:第一步、安装JDK;第二步、安装Eclipse;第三步、下载并

  • C#编写单片机上位机软件-串口通讯(BMS汽车动力电池管理系统)

    C#编写单片机上位机软件-串口通讯(BMS汽车动力电池管理系统)上位机软件做了有一段时间,本人呕心沥血的作品。之前用python+pyQT5做,主线程特别特别容易闪退,数据重叠等问题,走了很多弯路;后来用VS的C#做,只能说上手很快,调试效果也不错,而且关键是非常非常简单易读,只希望大家不要像我一样,走这么多弯路–想要源码的小伙伴们,欢迎关注点赞三连+留言邮箱哦~华丽的分割线——————————————————————————————–

  • 用什么软件写html语言,写html代码用什么软件

    用什么软件写html语言,写html代码用什么软件写html代码的软件:1、SublimeText;2、Dreamweaver;3、WebStorm;4、HBuilder;5、Notepad;6、VSCode;7、Vim;8、AptanaStudio;9、IntelliJIDEA。本教程操作环境:windows7系统、HTML5版、DellG3电脑。1、SublimeTextSublimeText是一个跨平台的代码编辑器,同时支持W…

  • python fabric实现远程操作和部署

    python fabric实现远程操作和部署

  • 移动三国己然鼎立,普​通开发者如何选择开发​平台?

    移动三国己然鼎立,普​通开发者如何选择开发​平台?

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号