【学习笔记】欧拉函数
NCC79601
2019-10-03 12:23:59
# 定义
欧拉函数$\varphi(n)$：表示$[1,n)$内与$n$互质的数的个数。
# 性质
## 性质1
对于素数，很明显有
$$\varphi(n)=n-1$$
## 性质2
$$\varphi(p^k)=p^k-p^{k-1}\;\;(p\text{为质数})$$
**证明：** 由于$p$是质数，所以只要一个数的因数不含$p$，那么这个数就和$p$互质。在$[1,p^k)$内，这样的数也就是$p^1,p^2,\cdots,p^{k-1},$总共有$p^{k-1}$个。因此只要将这些数去除，剩下的数都和$p^k$互质。
## 性质3
若$n=p_1\cdot p_2\;\;(p_1,p_2\text{为质数})$，则有：
$$\varphi(n)=\varphi(p_1)\cdot\varphi(p_2)$$
**证明：** 由于$p_1,p_2$是质数，所以在$[1,n)$中，只有$p_1$和$p_2$的倍数与$n$非互质。而$p_1$的倍数共有$p_2-1$个，$p_2$的倍数共有$p_1-1$个，所以有：
$$\varphi(n)=p_1\cdot p_2-1-(p_1-1)-(p_2-1)$$
$$=p_1\cdot p_2-p_1-p_2+1=(p_1-1)\cdot(p_2-1)$$
由性质1可得：
$$\varphi(n)=\varphi(p_1)\cdot\varphi(p_2)$$
## 性质4
设$n=p_1^{k_1}\cdot p_2^{k_2}\cdot \cdots\cdot p_s^{k_s}$，则
$$\varphi(n)=n\cdot\prod_{i=1}^s(1-\frac 1{p_i})$$
**证明：** 首先将性质2改写成：
$$\varphi(p^k)=p^k(1-\frac 1p)$$
然后用性质3将$\varphi(n)$展开，可得：
$$\varphi(n)=\prod_{i=1}^s \varphi(p_i^{k_i})=\prod_{i=1}^s p_i^{k_i}\cdot \prod_{i=1}^s (1-\frac 1{p_i})=n\cdot\prod_{i=1}^s (1-\frac 1{p_i})$$
## 性质5
若$n$为奇数，则有：
$$\varphi(2n)=\varphi(n)$$
**证明：** 运用性质3展开即可。
## 性质6
当$a,n\;(n>2)$互质，有：
$$a^{\varphi(n)}\equiv1\,(\mod n)$$
**证明：** 我不知道，背结论就好。
### 拓展
当$n=p$且$p$为质数，有：
$$a^{\varphi(p)}=a^{p-1}\equiv1\,(\mod p)$$
该式即**费马小定理**。
# 求法
## 单个数的求法
枚举质因数即可，复杂度$O(\sqrt{n})$，代码略。
## 递推求法
运用性质4，以及欧拉筛的思路进行递推。
```cpp
void euler() {
for (int i = 2; i < MAXN; i++)
if (!phi[i])
for (int j = i; j < MAXN; j += i) {
if(!phi[j])
phi[j] = j;
phi[j] = phi[j] / i * (i - 1);
}
}
```