数论四大定理之威尔逊定理

威尔逊定理

p 为质数\Longleftrightarrow(p-1)!\equiv -1(\mod p)

证明：

  1. 必要性：
    (p-1)!\equiv -1(\mod p)\Longleftrightarrow p|(p-1)!+1
    假设 p 不是质数，且 a 是 p 的质因子。
    易知a|(p-1)!，则a\nmid(p-1)!+1
    而p|(p-1)!+1\Longrightarrow a|(p-1)!+1，前后矛盾！
    故 p 一定为质数。
  2. 充分性：
    当 p = 2 时，(p-1)!\equiv -1(\mod p)显然成立。
    当 p = 3 时，(p-1)!\equiv -1(\mod p)显然成立。
    当p\ge5时，令M=\{2,3,\cdots,p-2\},N=\{1,2,\cdots,p-1\} \forall a\in M，令S=a\cdot N=\{a,2a,\cdots,(p-1)a\} 注意\forall t\in S,p\nmid t
    \therefore\forall t_1,t_2\in S,t_1<t_2\Longrightarrow t_2-t_1\in S\Longrightarrow p\nmid(t_2-t_1)
    根据同余的定义可知，S中所有元素模p都不同余
    \therefore S\mod p=N
    也就是说\forall a\in M,\exists x\in N，一定有ax\equiv1(\mod p)
    若x=1，则ax\%p=a\%p=a,\therefore x\ne1
    若x=p-1，则
    ax\%p=(ap-a)\%p=[(a-1)p+p-a]\%p=p-a,\therefore x\ne p-1
    若x=a，则
    a^2\equiv1(\mod p)\Longrightarrow(a+1)(a-1)\equiv0(\mod p) \Longrightarrow a=1或a=p-1\therefore x\ne a
    综上所述，\forall a\in M,\exists x\in M,且a\ne x,有ax\equiv1(\mod p)
    所以(p-1)!\equiv1\cdot(p-1)\equiv-1(\mod p)

证毕！

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 品味数学之美－RSA原理浅析
    学一点有趣的数论知识 在探究RSA算法的原理之前，我们先来学习一点有趣的数论知识（数学分支之一，主要研究整数的性质...
    24f464006eaf阅读 6,540评论 0赞 5
  • 记先生
    记先生毕寒 2016级6班 黄宝升 师者，学之集大成者...
    秋喜2018阅读 5,272评论 0赞 2
  • 初遇简书
    初遇简书 ，真的是及其偶然。记得那天我百度一个词语，有一个简书官网映入眼帘。我首先想到这是一个专门研究古代竹简的网...
    羽筱筱阅读 2,905评论 0赞 0