class="markdown_views prism-github-gist">

回顾

---

在开始新的话题之前,先来回顾上一篇的欧拉定理和费马小定理:
$if gcd(a,m)=1,a^{varphi(m)}equiv 1pmod m\$
$if p为素数,a^pequiv apmod p\$
欧拉定理的证明,主要的点是在$gcd(a,m)=1$下$ax_i$遍历一个简化剩余系,所以$prod_{i=1}^{varphi(m)} x_iequiv prod_{i=1}^{varphi(m)} ax_ipmod m$
两边同除连乘,得$a^varphi(m)equiv 1pmod m$. 费马定理的证明,主要是:

1. $gcd(a,p)=1$下应用欧拉定理到$a^{p-1}equiv 1pmod p$,然后两边同乘一个对p互质的$a$,Q.E.D.
2. $gcd(a,p)= ot 1$下,只有$p|a$.就没什么好说的了.

---

下面是一个初步的应用.
$quesition: 2^{20170226}pmod 7$
${solution:}\ varphi(7)=6,由欧拉定理,2^6equiv 1pmod 7\ 则 2^{6k}equiv 1pmod 7\ 由 20170226pmod 6=2,有2^{20170226}=2^{6k}cdot 2^2\ herefore 2^{20170226}equiv4pmod 7\ 注意是1cdot4=4而不是1+4=5!$
由上一题可见,运用欧拉定理的前提是求出$varphi(m)$,所以接下来的几个定理将提出大数情况下$varphi(m)$的求法.

---

大数$varphi(m)$的求解

---

${Theorem:}\ if gcd(m,n)=1 ightarrow varphi(mn)=varphi(m) imesvarphi(n)$
解释:
由定理$x遍历n的一个简化剩余系,y遍历m的一个简化剩余系时,mx+ny遍历mn的简化剩余系$(简化剩余系的交叉联合遍历) ,${x_i}$有$varphi(n)$个,${y_i}$有$varphi(m)$个,于是对于mn的简化剩余类的每一个元素$f(x,y)$,有$f(x,y)=mx+ny$唯一对应.那么对于$f(x)$,有$varphi(m) imesvarphi(n)$个方案(x有$varphi(n)$个,y有$varphi(m)$个,别反了).于是$f(x)$有$varphi(m) imesvarphi(n)$个,即$varphi(mn)=varphi(m) imesvarphi(n)$.

---

${Theorem:}\ if p为素数,e为正整数,varphi(p^e)=p^e-p^{e-1}$
解释:
对于素数p,没有除了1,p以外的其他因数,对于$p^e$,存在且仅存在的因数只有:
${p^i imes p}(iin mathbb{z}且iin [1,p^{e-1}],和1).$