精华内容
下载资源
问答
  • Wilson定理推论

    2018-10-23 01:44:47
    Wilson定理: 设 ppp 是一个素数,则 (p−1)!≡−1(mod  p).(p-1)!\equiv-1(mod\;p).(p−1)!≡−1(modp).     此定理的证明一般不难找到,此处不作赘述。下面介绍一下...
    • Wilson定理: 设 pp 是一个素数,则
    (p1)!1(mod  p).(p-1)!\equiv-1(mod\;p).

        此定理的证明一般不难找到,此处不作赘述。下面介绍一下相关的推论以及证明(选自《信息安全数学基础(第二版)第2章习题》)
     

    • 推论1: 如果 pp 是奇素数,那么
    1232  (p4)2(p2)2(1)p+12(mod  p)1^2\cdot3^2\cdot\,\cdots\,\cdot(p-4)^2\cdot(p-2)^2\equiv(-1)^{\frac{p+1}{2}}(mod\;p)

    证明:
    (p1)!=1234  (p4)(p3)(p2)(p1)=1[p(p2)]3[p(p4)]  (p4)(p3)(p2)(p1)=1(p1)3(p3)  (p4)[p(p4)][p(p2)]1232  (p4)2(p2)2(1)p12(mod  p)  p\begin{aligned} (p-1)!&=1\cdot2\cdot3\cdot4\cdot\,\cdots\,\cdot(p-4)(p-3)(p-2)(p-1)\\ &=1\cdot[p-(p-2)]\cdot3\cdot[p-(p-4)]\cdot\,\cdots\,\cdot(p-4)(p-3)(p-2)(p-1)\\ &=1\cdot(p-1)\cdot3\cdot(p-3)\cdot\,\cdots\,\cdot(p-4)[p-(p-4)][p-(p-2)]\\ &\equiv1^2\cdot3^2\cdot\,\cdots\,\cdot(p-4)^2(p-2)^2(-1)^{\frac{p-1}{2}}(mod\;p)\;(p为奇数) \end{aligned}
    Wilsonp(p1)!1(mod  p).由Wilson定理可知,若p为素数,则(p-1)!\equiv-1(mod\;p).
    所以
      1232  (p4)2(p2)2(1)p121(mod  p)1232  (p4)2(p2)2(1)p1(1)p+12(mod  p)1232  (p4)2(p2)2(1)p+12(mod  p)\begin{aligned} &\quad\ \ 1^2\cdot3^2\cdot\,\cdots\,\cdot(p-4)^2(p-2)^2(-1)^{\frac{p-1}{2}}\equiv-1(mod\;p)\\ &\Rightarrow1^2\cdot3^2\cdot\,\cdots\,\cdot(p-4)^2(p-2)^2(-1)^{p-1}\equiv(-1)^{\frac{p+1}{2}}(mod\;p)\\ &\Rightarrow1^2\cdot3^2\cdot\,\cdots\,\cdot(p-4)^2(p-2)^2\equiv(-1)^{\frac{p+1}{2}}(mod\;p)\\ \end{aligned}
     

    • 推论2: 如果 pp 是素数,并且p3(mod  4)p\equiv3(mod\;4),那么
    (p12)!±1(mod  p).(\frac{p-1}{2})!\equiv\pm1(mod\;p).

    证明:
    p3(mod  4)p=4m+3mZ因为p\equiv3(mod\;4),所以p=4m+3(m\in \mathbb{Z})
    (4m+2)!=12  (2m+1)(2m+2)  (4m+1)(4m+2)=12  (2m+1)[p(2m+1)]  (p2)(p1)=[(2m+1)!]2(1)2m+1.\begin{aligned} (4m+2)!&=1\cdot2\cdot\,\cdots\,\cdot(2m+1)(2m+2)\cdot\,\cdots\,\cdot(4m+1)(4m+2)\\ &=1\cdot2\cdot\,\cdots\,\cdot(2m+1)[p-(2m+1)]\cdot\,\cdots\,\cdot(p-2)(p-1)\\ &=[(2m+1)!]^2(-1)^{2m+1}.\\ \end{aligned}
    Wilsonp(p1)!1(mod  p).由Wilson定理可知,若p为素数,则(p-1)!\equiv-1(mod\;p).
    所以
      [(2m+1)!]2(1)2m+11(mod  p)[(2m+1)!]2(1)2(2m+1)(1)2m+2(mod  p)[(2m+1)!]21(mod  p)[(2m+1)!]210(mod  p)[(2m+1)!+1][(2m+1)!1]0(mod  p)\begin{aligned} &\quad\ \ [(2m+1)!]^2(-1)^{2m+1}\equiv-1(mod\;p)\\ &\Rightarrow[(2m+1)!]^2(-1)^{2(2m+1)}\equiv(-1)^{2m+2}(mod\;p)\\ &\Rightarrow[(2m+1)!]^2\equiv1(mod\;p)\\ &\Rightarrow[(2m+1)!]^2-1\equiv0(mod\;p)\\ &\Rightarrow[(2m+1)!+1][(2m+1)!-1]\equiv0(mod\;p) \end{aligned}
     p 因为\,p\,为素数,
    (2m+1)!+10(mod  p)(2m+1)!10(mod  p)所以必有(2m+1)!+1\equiv0(mod\;p)或(2m+1)!-1\equiv0(mod\;p)
    (2m+1)!±1(mod  p)(p12)!±1(mod  p).即(2m+1)!\equiv\pm1(mod\;p)\Rightarrow(\frac{p-1}{2})!\equiv\pm1(mod\;p).
     

    • 推论3:如果 pp 是素数,并且0<k<p0<k<p,那么
    (pk)!(k1)!(1)k(mod  p).(p-k)!(k-1)!\equiv(-1)^k(mod\;p).

    证明:
    (p1)!=12  (pk)(pk+1)  (p2)(p1)=12  (pk)[p(k1)]  (p2)(p1)=(pk)!(k1)!(1)k10<k<p\begin{aligned} (p-1)!&=1\cdot2\cdot\,\cdots\,\cdot(p-k)(p-k+1)\cdot\,\cdots\,\cdot(p-2)(p-1)\\ &=1\cdot2\cdot\,\cdots\,\cdot(p-k)[p-(k-1)]\cdot\,\cdots\,\cdot(p-2)(p-1)\\ &=(p-k)!(k-1)!(-1)^{k-1}(0<k<p) \end{aligned}
    Wilsonp(p1)!1(mod  p).由Wilson定理可知,若p为素数,则(p-1)!\equiv-1(mod\;p).
    所以
      (pk)!(k1)!(1)k11(mod  p)(pk)!(k1)!(1)2(k1)(1)k(mod  p)(pk)!(k1)!(1)k(mod  p)\begin{aligned} &\quad\ \ (p-k)!(k-1)!(-1)^{k-1}\equiv-1(mod\;p)\\ &\Rightarrow(p-k)!(k-1)!(-1)^{2(k-1)}\equiv(-1)^k(mod\;p)\\ &\Rightarrow(p-k)!(k-1)!\equiv(-1)^k(mod\;p)\\ \end{aligned}
     
     
    参考文献
    [1] 殷堰工,Wilson定理的若干探讨,苏州教育学院学报,第17卷第3期,2000年9月。
    [2] 叶寿坤,威尔逊定理的两个推论及应用,龙岩师专学报,第11卷第3期,1993年8月。

    展开全文
  • 给出了数论中著名的Wilson定理的一个新推广.并且推广了Adelberg的一个同余式,
  • 欧拉函数欧拉定理Fermat费马小定理Wilson定理
    • 欧拉函数





    • 欧拉定理

    • Fermat费马小定理

    • Wilson定理

    展开全文
  • 这篇短文给出了在一个唯一分解环中对于有原根存在的模的一个定理,即wilson定理的个推广。这说明在一个唯一分解环中研究原根存在的条件是有意义的工作。
  • Wilson定理证明

    2015-09-11 17:40:00
    Wilson定理证明 就是那个\((p-1)! \equiv -1 \pmod{p}\),\(p\)是一个素数. Lemma A \(\mathbb{Z}_p\)可以去掉一个零元变成一个群. 即\(\forall a\in \mathbb{Z}_ {p},a\not= \overline{0}, \exists b \in \mathbb{Z}...

    Wilson定理证明

    就是那个\((p-1)! \equiv -1 \pmod{p}\),\(p\)是一个素数.

    Lemma A

    \(\mathbb{Z}_p\)可以去掉一个零元变成一个群.

    \(\forall a\in \mathbb{Z}_ {p},a\not= \overline{0}, \exists b \in \mathbb{Z}_p,ab=\overline{1}\)也就是存在逆元.

    Lemma B

    \(\forall a\in \mathbb{Z}_p,a\not=\overline{p-1},a^2\not\equiv 1 \pmod{p}\)

    证明

    设存在\(x^2\equiv 1 \pmod{p}, x<p-1\)\(x^2=np+1\~\~ n\in \mathbb{Z}\),则\(np=(x+1)(x-1)\),则\(p\mid x-1 或 p\mid x+1\).显然,当\(p=x+1\)\((x+1)(x-1)\)达到最小,而此刻\(x=p-1\),与\(x<p-1\)矛盾.

    证明

    通过Lemma A与Lemma B可知\(2\dots p-2\)的逆元都不等于它们本身,且都在\(2\dots p-2\)间.那我们对它们配对即可得\((p-2)! \equiv 1 \pmod{p}\),乘上\(p-1\)即得到\((p-1)! \equiv -1 \pmod{p}\)

    转载于:https://www.cnblogs.com/tmzbot/p/4801570.html

    展开全文
  • 序言 ... 但你以为判断一个素数只能用O(n)O(\sqrt n)O(n​)的时间复杂度吗?...在这一篇文章,我就要提到一个十分神奇的定理,Wilson定理Wilson定理 p为质数⇔(p−1)!≡−1(mod&ThinSpace;&Th...

    序言

    Wilson定理

    p(p1)!1(mod&ThinSpace;&ThinSpace;p)p为质数\Leftrightarrow(p-1)! \equiv -1(\mod p)

    证明

    • 既然是要证明两个条件等价,肯定要分成两个部分证明:

    1.若(p1)!1(mod&ThinSpace;&ThinSpace;p)(p-1)! \equiv -1(\mod p),则p为质数。(必要性)
    2.若p为质数,则(p1)!1(mod&ThinSpace;&ThinSpace;p)(p-1)! \equiv -1(\mod p)。(充分性)

    必要性证明

    • (p1)!=kp1(p-1)!=kp-1,由于相邻的2个数aaa+1a+1一定互质,所以可得(p1)!(p-1)!kpkp一定互质。
    • 又可以显然地得出(p1)!(p-1)!pp一定互质。
    • 因为(p1)!=123...(p1)(p-1)!=1*2*3*...*(p-1)
    • 所以[1,p1][1,p-1]中的每一个数都与pp互质,所以pp为质数。
    • (是不是很简单呢?)

    充分性证明

    • p=2p=2p=3p=3时,证明显然。
    • 下面考虑p&gt;3p&gt;3的情况:
    • 发现p11(mod&ThinSpace;&ThinSpace;p)p-1 \equiv -1(\mod p)11(mod&ThinSpace;&ThinSpace;p)1 \equiv 1 (\mod p),所以只需证明23...(p2)1(mod&ThinSpace;&ThinSpace;p)2*3*...*(p-2) \equiv 1(\mod p)即可。
    • 接下来的分析就需要一点脑回路了…
    • 对于[2,p2][2,p-2]中的一个数aa,由于gcd(a,p)=1gcd(a,p)=1,所以同余方程ax1(mod&ThinSpace;&ThinSpace;p)a*x \equiv1(\mod p)x[1,p1]x \in [1,p-1]一定有解。
    • x=ax=a,则aa1(mod&ThinSpace;&ThinSpace;p)a*a \equiv 1(\mod p),所以(a1)(a+1)0(mod&ThinSpace;&ThinSpace;p)(a-1)(a+1) \equiv 0(\mod p)
    • 所以(a1)p(a-1)|p(a+1)p(a+1)|p
    • 但因为a[2,p2]a \in [2,p-2],所以显然(a1)p(a-1) \nmid p(a+1)p(a+1) \nmid p
    • 所以xax \neq a
    • x=1x=1,则显然a=1a=1,因为a[2,p2]a \in [2,p-2],所以x1x \neq 1
    • x=p1x=p-1,则显然a=p1a=p-1,因为a[2,p2]a \in [2,p-2],所以xp1x \neq p-1
    • 因为x[1,p1]x \in [1,p-1],所以x[2,p2]x \in [2,p-2]
    • 所以在[2,p2][2,p-2]中,我们总能找到两两配对的数aabb使得ab1(mod&ThinSpace;&ThinSpace;p)a*b \equiv 1(\mod p),然后我们分别把它们乘起来,最后得到的结果便是11
    • p=7p=7为例。
    • [2,p2][2,p-2]中有2,3,4,52,3,4,5
    • 我们进行分组(2,4)(2,4)(3,5)(3,5),然后2345(24)(35)1112*3*4*5 \equiv (2*4)*(3*5) \equiv 1*1 \equiv 1
    • 由于p&gt;3p&gt;3pp为素数,所以pp必为奇数。所以[2,p2][2,p-2]中一定有偶数个数,所以不会出现两两配对后余下一个的情况。
    • 因此得出23...(p2)1(mod&ThinSpace;&ThinSpace;p)2*3*...*(p-2) \equiv 1(\mod p)
    • 所以(p1)!1(mod&ThinSpace;&ThinSpace;p)(p-1)! \equiv -1 (\mod p),得证。

    应用

    • 证明了Wilson定理以后,你一定会发现这个东西既复杂又奇妙。
    • 紧接着,一个十分实际的问题挡在了你的面前:
    • “这个有什么应用呢?”
    • 显然,Wilson定理的一大用处就是用(p1)!1(mod&ThinSpace;&ThinSpace;p)(p-1)! \equiv -1 (\mod p)来判断素数。当然有时会还会反过来用。
    • 不过你会发现,求阶乘的时间复杂度不是O(n)O(n)的吗?说了这么一大堆结果连个暴力都跟它差不多吗?
    • 确实,阶乘是一个非常麻烦的东西。但其实我们有阶乘的快速求法,时间复杂度达到O(log22n)O(log_2^2n)甚至O(log2n)O(log_2n),可以爆踩之前的普通方法。
    • 但至于怎么快速求阶乘…等以后再说吧,毕竟这种东西用的也比较少!

    总结

    • 不会快速求阶乘?
    • 还有更好的方法!
    • (未完待续)
    展开全文
  • Miller_Rabin素数测试[Fermat小定理][二次探测定理][同余式][Wilson定理] 分类: 各种数学2013-08-14 19:06 444人阅读 评论(0) 收藏 举报 目录(?)[+] 部分引用自: ...
  • 最大公因数基本定理 最大公因数表示 算术基本定理 设p是素数,a1,a2,…an为整数,其中n≥2,n∈Z,如果p∣∏k=1nak,则必有∃i,1≤i≤n,使p∣ai。设p是素数,a_{1},a_{2},…a_{n}为整数,其中n\ge 2,n\in Z,如果p|\...
  • 第一章的习题难度适中,这里抽出第35题来,这题是证明Wilson定理Wilson定理: N是一个素数当且仅当: (N-1)! ≡ -1(mod N) 证明: 首先我们证明若N是素数,那么等式成立,对于N=2,这是很明显的。以下证明N...
  • Wilson定理;对于一个任意整数n>1,当且仅当n是一个素数时,(n-1)!+1能够被n整除。 算法如下: function Wilson(n) {//当且仅当n>1且n是素数时,返回true if((n-1)!+1) mode n==0 then return true else return ...
  • Wilson(威尔逊)定理

    2019-11-20 19:39:49
    Wilson定理 首先,设p为素数,r1,r2…,rp-1是模p的既约剩余系 故我们有∏r mod p ′r≡ r1…rp−1≡−1(mod p). \prod_{r~mod~p} ~'r\equiv~r_1…r_{p-1}\equiv-1(mod~p).r mod ...
  • 威尔生定理在初等数论中是很重要的,而且是很有用的.本文给出可由威尔生定理推导出的三个判定质数的必要充分条件。
  • 利用Wilson定理来判定一个Wilson数字是否为素数。Wilson数字的格式统一为(n)!+1。
  • 从群论的角度再次证明原根定理以及 Wilson定理,并给出了 Wilson定理的一个推广.
  • UVA1434--Wilson证明

    2019-01-21 22:46:33
    Wilson定理 我在这里给出证明: (数竞党必备) 多项式大法! 前置技能一:Fermat定理 p为素数,xp−1≡1(modp)x^{p-1}\equiv1(modp)xp−1≡1(modp) 用缩系易证 前置技能二:Lagrange定理 p为素数,f(x)=anxn+an−1...
  •  最近忙着迎新,很久没有... Wilson定理指出,对于任一个质数p,都有(p-1)! ≡ -1 (mod p),换句话说(p-1)! + 1能被p整除。为了证明这一点,让我们来考虑一个圆周上的p等分点。顺次连接这p个点我们可以得到一个正p
  • 利用群的定义探讨了群与向量空间的联系,并用群的理论去证明欧拉定理和wilson定理
  • Miller_Rabin素数测试

    2013-03-08 19:03:54
    在关于素数的研究中素数的测试是一个非常重要的问题.Wilson 定理给出了一个数是素数的重要条件.   Wilson 定理 对于给定的正整数 n,判定 n 是一个素数的充要条件是  (n-1)!≡ -1(mod n) Wilson 定理有很...
  • 广义F定理与ϵ展开

    2020-04-19 02:42:59
    我们还研究了Wilson-Fisher O(N)模型的特定示例,并在球面S 4− define上定义了CFT,并特别注意曲率系数项的beta函数。 这使我们能够展开F〜$$ \ tilde {F} $$的ϵ扩展直到阶5。 将这个系列的Padé外推至
  • 群论中的运用Wilson定理应用:习题题目描述参考思路 前言: \quad 本文为密码学的数学基础(王小云版)读书笔记,仅做了一些自认为重要些的笔记,如有错误,欢迎指正. 同余五大性质(重要) a和b关于正整数m同余等价于存在正...
  • 然后,我们通过研究Wilson回路的几何形状以及将nonabelian Stokes定理[2-4]推广到费米离子的情况,根据Wilson回路构造异质弦sigma模型的作用。 之后,我们以三个回路图和四个回路图为例,以说明ζ2和ζ3的sv是如何...
  • 图论中握手定理的详细解释

    千次阅读 2020-08-02 11:04:48
    Wilson Huang 2020/8/2 握手定理 前提定义1: G=(V,E)G=(V,E)G=(V,E) 表示图 GGG 由顶点的非空集 VVV 和边集 EEE 构成 前提定义2: 在无向图中,顶点的度是与该顶点相关联的边的数目,例外的情形是,顶点上的环为...
  • 借助于Wilson回路算子的非阿贝尔Stokes定理,我们提出了从限制域构造的合适的规范不变算子,以重现原始Wilson回路平均值的正确行为以获得更高的表示。 此外,我们使用拟议的算子执行晶格模拟以测量夸克的静态势。 ...
  • 阶乘,于是我们可以联想到wilson定理 即:当且仅当p为素数时:( p -1 )! ≡ -1 ( mod p ) 于是我们就可以通过invert函数,一步步将A推成B,这样就可以很快的解除p,q的值,得到flag 脚本如下 // python2 import gmpy...
  • 文章目录同余的基本概念和性质剩余类和完全剩余系简化剩余系与欧拉函数欧拉定理 费马小定理 Wilson定理模重复平方法 同余的基本概念和性质 讨论整数的同余性质来对整数进行恰当的分类。 (1.1)给定一个正整数m,...

空空如也

空空如也

1 2 3
收藏数 48
精华内容 19
关键字:

wilson定理