三个重要的同余式——威尔逊定理，费马小定理，欧拉定理（扩展）

　

欧拉定理

鸣谢synapse7大大

威尔逊定理

(p−1)!≡p−1≡−1   (mod p) (p is a prime)" role="presentation" style="position: relative;">(p−1)!≡p−1≡−1(modp)(pisaprime)$(p-1)!\equiv p-1\equiv -1(modp)(pisaprime)$

由于(p−1)!" role="presentation" style="position: relative;">(p−1)!$(p-1)!$较大，实际应用不是很广泛

简单的证明

费马小定理

假如p" role="presentation" style="position: relative;">p$p$是质数，且gcd(a,p)=1" role="presentation" style="position: relative;">gcd(a,p)=1$gcd(a,p)=1$，那么a(p−1)≡1" role="presentation" style="position: relative;">a(p−1)≡1$a^{(p-1)}\equiv 1$（mod p）

简单的证明

欧拉定理

直到今天我才认清这三个人

A.欧拉(欧拉定理)     B.高斯(高斯消元)     C.欧几里得(欧几里得算法)" role="presentation" style="position: relative;">A.欧拉(欧拉定理)B.高斯(高斯消元)C.欧几里得(欧几里得算法)$A.欧拉(欧拉定理)B.高斯(高斯消元)C.欧几里得(欧几里得算法)$

下面就是ta的故事了：

在计算乘法逆元的时候，我们经常使用的（也是最简单的）就是费马小定理：

假如p" role="presentation" style="position: relative;">p$p$是质数，且gcd(a,p)=1" role="presentation" style="position: relative;">gcd(a,p)=1$gcd(a,p)=1$，那么a(p−1)≡1" role="presentation" style="position: relative;">a(p−1)≡1$a^{(p-1)}\equiv 1$（mod p）

实际上费马小定理是欧拉定理的特殊情况+应用

若n,a" role="presentation" style="position: relative;">n,a$n,a$为正整数，且n,a" role="presentation" style="position: relative;">n,a$n,a$互质，则aϕ(n)≡1" role="presentation" style="position: relative;">aϕ(n)≡1$a^{\varphi (n)}\equiv 1$（mod p）

由此，我们在计算幂的时候（底数与模数互质）则有

ab=ab mod ϕ(p)     (mod p) (gcd(a,p)=1)" role="presentation">ab=abmodϕ(p)(modp)(gcd(a,p)=1)$$a^b=a^{bmod\varphi (p)}(modp)(gcd(a,p)=1)$$

简单的证明

---

然而当底数与模数不互质的时候怎么办呢

我们需要欧拉定理的扩展包：

方便起见，我们可以合并一下：

注意：扩展欧拉定理只影响取模方式，并不影响模数

简单的证明

• 在a" role="presentation" style="position: relative;">a$a$的0" role="presentation" style="position: relative;">0$0$次,1" role="presentation" style="position: relative;">,1$,1$次,...,b" role="presentation" style="position: relative;">,...,b$,...,b$次幂模m" role="presentation" style="position: relative;">m$m$的序列中，前r" role="presentation" style="position: relative;">r$r$个数(a0到ar−1)" role="presentation" style="position: relative;">(a0到ar−1)$(a^0到a^{r-1})$互不相同，从第r" role="presentation" style="position: relative;">r$r$个数开始，每s" role="presentation" style="position: relative;">s$s$个数就循环一次

  证明：由鸽巢定理易证

  我们把r" role="presentation" style="position: relative;">r$r$称为a" role="presentation" style="position: relative;">a$a$幂次模m" role="presentation" style="position: relative;">m$m$的循环起始点，s" role="presentation" style="position: relative;">s$s$称为循环长度。（注意：r" role="presentation" style="position: relative;">r$r$可以为0）

  用公式表述为：ar≡ar+s   (mod m)" role="presentation" style="position: relative;">ar≡ar+s(modm)$a^r\equiv a^{r+s}(modm)$

• a" role="presentation" style="position: relative;">a$a$为素数的情况

  令m=(pr)m′" role="presentation" style="position: relative;">m=(pr)m′$m=(p^r)m^{\prime }$，则gcd(p,m′)=1" role="presentation" style="position: relative;">gcd(p,m′)=1$gcd(p,m^{\prime })=1$，所以pφ(m′)≡1(mod m′)" role="presentation" style="position: relative;">pφ(m′)≡1(modm′)$p^{\phi (m^{\prime })}\equiv 1(mod{m}^{\prime })$

  又由于gcd(pr,m′)=1" role="presentation" style="position: relative;">gcd(pr,m′)=1$gcd(p^r,m^{\prime })=1$，所以φ(m′)|φ(m)" role="presentation" style="position: relative;">φ(m′)|φ(m)$\phi (m^{\prime })|\phi (m)$，所以pφ(m)≡1(mod m′)" role="presentation" style="position: relative;">pφ(m)≡1(modm′)$p^{\phi (m)}\equiv 1(mod{m}^{\prime })$，

  即pφ(m)=km′+1" role="presentation" style="position: relative;">pφ(m)=km′+1$p^{\phi (m)}=k{m}^{\prime }+1$，两边同时乘以pr" role="presentation" style="position: relative;">pr$p^r$，得pr+φ(m)=km+pr（因为m=(pr)m′)" role="presentation" style="position: relative;">pr+φ(m)=km+pr（因为m=(pr)m′)$p^{r+\phi (m)}=km+p^r（因为m=(p^r)m^{\prime })$

  所以pr≡pr+s(mod m)" role="presentation" style="position: relative;">pr≡pr+s(modm)$p^r\equiv p^{r+s}(modm)$，这里s=φ(m)" role="presentation" style="position: relative;">s=φ(m)$s=\phi (m)$

  • 推论：pb≡pr+(b−r) % φ(m)(mod m)" role="presentation" style="position: relative;">pb≡pr+(b−r)%φ(m)(modm)$p^b\equiv p^{r+(b-r)\mathrm{\%}\phi (m)}(modm)$

  • 又由于m=(pr)m′" role="presentation" style="position: relative;">m=(pr)m′$m=(p^r)m^{\prime }$，所以φ(m)≥φ(pr)=pr−1(p−1)≥r" role="presentation" style="position: relative;">φ(m)≥φ(pr)=pr−1(p−1)≥r$\phi (m)\ge \phi (p^r)=p^{r-1}(p-1)\ge r$

    所以pr≡pr+φ(m)≡pr % φ(m)+φ(m)(mod m)" role="presentation" style="position: relative;">pr≡pr+φ(m)≡pr%φ(m)+φ(m)(modm)$p^r\equiv p^{r+\phi (m)}\equiv p^{r\mathrm{\%}\phi (m)+\phi (m)}(modm)$

    所以pb≡pr+(b−r) % φ(m)≡pr % φ(m)+φ(m)+(b−r) % φ(m)≡pφ(m)+b % φ(m)(mod m)" role="presentation" style="position: relative;">pb≡pr+(b−r)%φ(m)≡pr%φ(m)+φ(m)+(b−r)%φ(m)≡pφ(m)+b%φ(m)(modm)$p^b\equiv p^{r+(b-r)\mathrm{\%}\phi (m)}\equiv p^{r\mathrm{\%}\phi (m)+\phi (m)+(b-r)\mathrm{\%}\phi (m)}\equiv p^{\phi (m)+b\mathrm{\%}\phi (m)}(modm)$

    即pb≡pb % φ(m)+φ(m)(mod m)" role="presentation" style="position: relative;">pb≡pb%φ(m)+φ(m)(modm)$p^b\equiv p^{b\mathrm{\%}\phi (m)+\phi (m)}(modm)$

• a" role="presentation" style="position: relative;">a$a$为素数的幂的情况

  是否依然有ar′≡ar′+s′(mod m)" role="presentation" style="position: relative;">ar′≡ar′+s′(modm)$a^{r^{\prime }}\equiv a^{r^{\prime }+s^{\prime }}(modm)$(其中s′=φ(m)，a=pk" role="presentation" style="position: relative;">s′=φ(m)，a=pk$s^{\prime }=\phi (m)，a=p^k$)

  答案是肯定的，由2知ps&#x2261;1(mod&#xA0;m&#x2032;)" role="presentation" style="position: relative;">ps≡1(modm′)$p^s\equiv 1(mod{m}^{\prime })$，所以p(s&#x2217;(k/gcd(s,k))&#x2261;1(mod&#xA0;m&#x2032;)" role="presentation" style="position: relative;">p(s∗(k/gcd(s,k))≡1(modm′)$p^{(}s\ast (k/gcd(s,k))\equiv 1(mod{m}^{\prime })$，所以当s&#x2032;=s/gcd(s,k)" role="presentation" style="position: relative;">s′=s/gcd(s,k)$s^{\prime }=s/gcd(s,k)$时才能有ps&#x2032;k&#x2261;1(mod&#xA0;m&#x2032;)" role="presentation" style="position: relative;">ps′k≡1(modm′)$p^{s^{\prime }k}\equiv 1(mod{m}^{\prime })$，此时s&#x2032;|s|&#x3C6;(m)" role="presentation" style="position: relative;">s′|s|φ(m)$s^{\prime }|s|\phi (m)$，且r&#x2032;=ceil(r/k)&lt;=r&lt;=&#x3C6;(m)" role="presentation" style="position: relative;">r′=ceil(r/k)<=r<=φ(m)$r^{\prime }=ceil(r/k)<=r<=\phi (m)$

  由r&#x2032;&#xFF0C;s&#x2032;" role="presentation" style="position: relative;">r′，s′$r^{\prime }，s^{\prime }$与&#x3C6;(m)" role="presentation" style="position: relative;">φ(m)$\phi (m)$的关系，依然可以得到ab&#x2261;ab&#xA0;&#x0025;&#xA0;&#x3C6;(m)+&#x3C6;(m)&#xA0;(mod&#xA0;m)" role="presentation" style="position: relative;">ab≡ab%φ(m)+φ(m)(modm)$a^b\equiv a^{b\mathrm{\%}\phi (m)+\phi (m)}(modm)$

• a" role="presentation" style="position: relative;">a$a$为合数的情况

  只证a" role="presentation" style="position: relative;">a$a$拆成两个素数的幂的情况，大于两个的用数学归纳法可证

  设a=a1a2,ai=piki,ai" role="presentation" style="position: relative;">a=a1a2,ai=pkii,ai$a=a_1{a}_2,a_i=p_i^{k_i},a_i$的循环长度为si" role="presentation" style="position: relative;">si$s_i$

  则s|lcm(s1,s2)" role="presentation" style="position: relative;">s|lcm(s1,s2)$s|lcm(s_1,s_2)$，由于s1|&#x3C6;(m),s2|&#x3C6;(m)" role="presentation" style="position: relative;">s1|φ(m),s2|φ(m)$s1|\phi (m),s2|\phi (m)$，那么lcm(s1,s2)|&#x3C6;(m)" role="presentation" style="position: relative;">lcm(s1,s2)|φ(m)$lcm(s1,s2)|\phi (m)$，所以s|&#x3C6;(m)" role="presentation" style="position: relative;">s|φ(m)$s|\phi (m)$

  r=max{ceil(ri/ki)}&lt;=max{ri}&lt;=&#x3C6;(m)" role="presentation" style="position: relative;">r=max{ceil(ri/ki)}<=max{ri}<=φ(m)$r=max\{ceil(ri/ki)\}<=max\{ri\}<=\phi (m)$

  由r,s" role="presentation" style="position: relative;">r,s$r,s$与&#x3C6;(m)" role="presentation" style="position: relative;">φ(m)$\phi (m)$的关系，依然可以得到ab&#x2261;ab&#xA0;&#x0025;&#xA0;&#x3C6;(m)+&#x3C6;(m)&#xA0;(mod&#xA0;m)" role="presentation" style="position: relative;">ab≡ab%φ(m)+φ(m)(modm)$a^b\equiv a^{b\mathrm{\%}\phi (m)+\phi (m)}(modm)$

证毕

相关阅读

区间套定理

闭区间列{[an,bn]}\{[a_n,b_n]\}{[an​,bn​]}有性质： [an+1,bn+1]⊂[an,bn][a_{n+1},b_{n+1}]\subset[a_n,b_n][an+1​,bn+1

欧拉角 图解释

定义 先引wiki上的定义 欧拉角：由三个角度组成，在特定坐标系下用于描述刚体的orientation.简单来说，就是绕一个三维坐标系统下的三个

香农三大定理

香农三大定理是信息论的基础理论。香农三大定理是存在性定理，虽然并没有提供具体的编码实现方法，但为通信信息的研究指明了方向。香

素数分布 2：素数定理

素数分布：素数定理研究素数素数的个数问题，π(x)\pi(x)π(x)表示不超过xxx的素数的个数。 从 到 素数个数 从 到 素数个数

卢卡斯定理（十分钟带你看懂）

在开始之前我们先介绍3个定理： 1.乘法逆元 如果ax≡1 (mod p),且gcd(a,p)=1（a与p互质），则称a关于模p的乘法逆元为x。 2.费马小定理： 3